[코드트리/NOVICE MID] 왔다 갔던 구역 2 (JAVA)

🔺 문제

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

 

 

🔺 코드

- 정답1) 1차원 배열 한 번만 사용

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, answer;
    static int[] arr;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        arr = new int[2001];
 
        int now = 1000; // 시작점을 아예 1000으로
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            char dir = st.nextToken().charAt(0);
 
            if (dir == 'L') {
                // 왼쪽 이동 시 색칠 구간 : [현재 위치 - 1, 현재 위치 - 이동 크기]
                for (int i = now - 1 ; i >= now - x ; i--) {
                    arr[i] += 1;
                }
                now -= x;   // 현재 위치 업데이트
            }
            else {
                // 오른쪽 이동 시 색칠 구간 : [현재 위치, 현재 위치 + 이동 크기 - 1]
                for (int i = now; i < now + x; i++) {
                    arr[i] += 1;
                }
                now += x;   // 현재 위치 업데이트
            }
        }
 
        // 2번 이상 지나간 구간 구하기
        answer = 0;
        for(int i = 0 ; i < arr.length ; i++) {
             if(arr[i] >= 2) {
                 answer++;
             }
        }
        System.out.println(answer);
    }
}

- 왼쪽 이동 시 색칠 구간      : [현재 위치 - 1, 현재 위치 - 이동 크기] ([현재 위치, 현재 위치 - 이동 크기 + 1]만큼 해도 됨)

- 오른쪽 이동 시 색칠 구간 : [현재 위치, 현재 위치 + 이동 크기 - 1]

 

 

 

- 정답2) 1차원 배열 두 번 사용

import java.io.*;
import java.util.*;
 
public class Main {
    static final int OFFSET = 1000; // 최소값이 -1000이므로
    
    static int N, answer;
    static int[] x1 = new int[100]; // 시작점 배열
    static int[] x2 = new int[100]; // 도착점 배열
    
    static int[] arr = new int[2001];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        arr = new int[2001];
 
        int now = 0;
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            char dir = st.nextToken().charAt(0);
 
            if (dir == 'L') {
                x1[i] = now - x;
                x2[i] = now;
                now -= x;
            }
            else {
                x1[i] = now;
                x2[i] = now + x;
                now += x;
            }
        }
 
        // 🔔 구간 칠하기 (x2에 등호 안 들어가게!)
        for (int i = 0; i < N ; i++) {
            for(int j = x1[i] + OFFSET ; j < x2[i] + OFFSET ; j++) { // OFFSET 값 더하기 ! (음수 좌표 고려)
                arr[j]++;
            }
        }
 
        // 2번 이상 지나간 영역 크기 구하기        
        answer = 0;
        for(int i = 0 ; i <= 2000 ; i++) {
            if(arr[i] >= 2) answer++;
        }
 
        System.out.println(answer);
    }
}
 

• 겹치는 구간 찾기 문제이므로, x1 ~ x2 - 1까지임!!!! (등호 조심)

• 음수 좌표에 대해, OFFSET 값 더한 후, 시뮬레이션 해야 함. (+1000)

 

 

 

💥 유의사항

• "겹치는 구간 구하기" ⇨ x2 범위에 등호 안 들어가야 함

 

---

💬 느낀 점

쉬워보이지만 만만하지 않은 겹치는 구간 칠하기....

자꾸 값이 1씩 차이 나서 어디를 고쳐야 하나 ..했는데

역시나 구간을 잘 생각하고 설정해줘야하는 것 같다...

 

 

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

---

(참고)

[코드트리 챌린지] 구간 칠하기