구간 칠하기

최대로 겹치는 구간

최대로 겹치는 구간

이 문제에서 기억해둘 발상은 2가지이다.

3
1 5 
4 6
2 4

이런 입력 값이 주어졌을 때, 2차원 배열로 보관할지 고민했었다.

나는 그냥 입력값이 주어졌을 때, 바로바로 처리하는 식으로 접근했는데, 이 문제 해답에서 흥미로운 저장 방식이라서 참고할 만한 것 같다.

for(int i = 0; i < n; i++) {
            x1[i] = sc.nextInt();
            x2[i] = sc.nextInt();

            // OFFSET을 더해줍니다.
            x1[i] += OFFSET;
            x2[i] += OFFSET;
        }

이런 식으로 배열을 두 개 만들어서 같은 인덱스에 다른 값들을 저장하는 방식이다.

나중에 써먹을 만한 방식인 것 같다.

그리고 배열의 인덱스로는 음수를 표현할 수 없으니까 미리 OFFSET을 더해서 접근하는 발상도 흥미롭다.(어차피 상대적 위치값이 중요하니까)

왔다 갔던 구역 2

왔다 갔던 구역 2

문제의 핵심은 왼쪽, 오른쪽으로 이동하면서 겹치는 영역의 크기를 구하는 문제이다.

여기서 문제에 2가지 포인트가 있다.

먼저 겹치는 영역의 크기를 구하기 위해서 배열에 좌표의 자취를 카운팅하는 게 핵심이다.

그리고 구간의 길이를 알아내기 위해 인덱스마다 배열에 x1, x2로 전체 선분을 기억해두는 게 포인트다.(이 부분 때문에 못 풀었다..)

그냥 겹치는 선분 길이 찾기 문제 유형으로 기억해두어도 좋을 것 같다.

아 그리고 다 풀고나서 내 풀이랑 비교하면서 상수 컨벤션이나 깔끔한 풀이 등도 배울 수 있어서 좋았다.

import java.util.*;
public class Main {
    public static final int OFFSET = 1000;
    public static final int MAX_R = 2000;
    public static final int MAX_N = 100;

    public static int n;
    public static int[] x1 = new int[MAX_N];
    public static int[] x2 = new int[MAX_N];

    public static int[] checked = new int[MAX_R + 1];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int cur = 0;
        for(int i=0; i<n; i++){
            int distance = sc.nextInt();
            char direction = sc.next().charAt(0);
            if(direction == 'L'){
                x1[i] = cur - distance;
                x2[i] = cur;
                cur -= distance;
            }else{
                x1[i] = cur;
                x2[i] = cur + distance;
                cur += distance;
            }
        }
        for(int i=0; i<n; i++){
            for(int j = x1[i]+OFFSET; j < x2[i]+OFFSET; j++)
                checked[j]++;
        }
        int cnt = 0;
        for(int i = 0; i <= MAX_R; i++)
            if(checked[i] >= 2)
                cnt++;

        System.out.print(cnt);
    }
}