[코드트리/NOVICE MID] 최대로 겹치는 구간 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, cnt;
    static int[] arr = new int[201];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
 
        while(N --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int x1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
 
            for(int i = x1 ; i < x2 ; i++) {
                arr[i + 100] += 1;  // OFFSET 필요
                cnt = Math.max(cnt, arr[i + 100]);
            }
        }
 
        System.out.println(cnt);
    }
}

 

 

🧩  해결 아이디어

• 시뮬레이션

- 겹치는 지점 범위 : x1 ~ x2
- 겹치는 구간 범위 : x1 ~ x2 - 1
- 음수 인덱스를 가질 수 없으므로, 모든 좌표에 대해 양수로 만드는 OFFSET 필요 (i + 100)

 

 

---

💬 느낀 점

겹치는 지점 구할 때 범위는 x1 ~ x2,

겹치는 구간 구할 때 범위는 x1 ~ x2-1임을 알았다.... 

문제에서 겹치는 지점을 원하는지, 구간을 원하는지 잘 봐야겠다!

 

그리고 OFFSET 필요한 것도!

 

어쩐지 이런 문제 그냥 풀려고 하면 어디선가 틀리더라니..!!

원인을 찾았당.

 

1회독	2회독	3회독	4회독	5회독
V