[백준 14594번 / java] 동방 프로젝트 (small)

문제

14594번: 동방 프로젝트 (Small) (acmicpc.net)

풀이

첫 시도 

배열에 1~N의 숫자를 넣어두고, a부터 b까지의 숫자를 a로 모두 바꾸도록 했다.

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i] = i+1;
        }
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            for(int j=a-1; j<b; j++){ //첫 번째 위치에 저장되어있는 수로 모두 바꾸기
                arr[j] = arr[a-1];
            }
        }
        int t = arr[0];
        int ans = 1;
        for(int i=0; i<N; i++){
            if(t != arr[i]){
                ans++;
                t = arr[i];
            }
        }
        bw.write(ans+" ");
        bw.close();
    }
}

 

반례 :

8
6
5 8
6 7
4 7
5 6
1 3
1 5

 

a, b를 입력받을 때마다 arr값의 변화를 추적해보면 다음과 같다.

idx	1	2	3	4	5	6	7	8
(5, 8)	1	2	3	4	5	5	5	5
(6, 7)	1	2	3	4	5	5	5	5
(4, 7)	1	2	3	4	4	4	4	5
(5, 6)	1	2	3	4	4	4	4	5
(1, 3)	1	1	1	4	4	4	4	5
(1, 5)	1	1	1	1	1	4	4	5

 

a=5 b=8 이후에 a=4 b=7이 수행되면 인덱스 8이 다른 방으로 인식된다.

 

해결 방법

순서쌍 (a, b)를 모두 받아두고 a기준 오름차순 정렬 후 위 방식을 적용한다.

코드

import java.util.*;
import java.io.*;
public class boj_14594 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i] = i+1;
        }

        Pair[] pairs = new Pair[M];

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            pairs[i] = new Pair(a, b);
        }
        Arrays.sort(pairs);

        for(int i=0; i<pairs.length; i++){
            int a = pairs[i].a;
            int b = pairs[i].b;
            for(int j=a-1; j<b; j++){
                arr[j] = arr[a-1];
            }
        }

        int t = arr[0];
        int ans = 1;
        for(int i=0; i<N; i++){
            if(t != arr[i]){
                ans++;
                t = arr[i];
            }
        }
        bw.write(ans+" ");
        bw.close();
    }
}
class Pair implements Comparable<Pair>{
    int a, b;
    Pair(int a, int b){
        this.a = a;
        this.b = b;
    }
    public int compareTo(Pair p){
        return this.a - p.a;
    }
}

Memo

• 실버4에 정답률도 높은데 제한시간 내내 안 풀렸던 문제이다. 알고리즘 공부를 소홀히 한 대가로 느껴졌다.
• 이 문제를  union find로 푼 사람도 있었다.