[백준 18248번 / java] 제야의 종

문제

18248번: 제야의 종

풀이1

모든 사람(1~4)은 자리가 고정되어있고, 타종이 시행될 때마다 종 소리가 도달하는 거리는 다르다.

따라서 들은 사람(1)과 못 들은 사람(0)이 생긴다.

 

첫 번째 타종이 수행됐을 때, 사람 1은 들었는데 사람 2는 못 들었다면 종으로부터의 거리는 (사람1 < 사람2)이다.

두 번째 타종이 수행됐을 때, 사람 2는 들었는데 사람 1은 못 들었다면 종으로부터의 거리는 (사람1 > 사람2)이다.

 

이 두 상황은 모순이다.

따라서 각각의 타종이 울렸을 때를 비교해서 모순되는 경우를 찾으면 된다.

 

예제)

	타종 M번
사람 N명		1	2	3	4
	1	0	0	0	1
	2	0	0	0	0
	3	0	0	0	0
	4	1	1	1	0

 

예제의 경우, 세 번째 타종에서 사람 1은 못 들었고(0) 사람 4는 들었다(1).

네 번째 타종에서 사람 1은 들었고(1) 사람 4는 못 들었다(0).

-> 모순이므로 NO 출력 (모든 경우를 탐색했지만 모순이 없다면 YES 출력)

 

• isPossible() 메서드

결론적으로

(1 0)

(0 1)

형태가 있으면 모순이라고 볼 수 있다.

따라서 arr[][]에서 모든 열을 1:1로 비교하면서 모순이 있는지 찾는다.

static boolean isPossible(){
        for(int i1=0; i1<M-1; i1++){ //기준
            for(int i2=i1+1; i2<M; i2++){ //비교 대상
                int cnt1 = 0;
                int cnt2 = 0;
                int cnt3 = 0;
                for(int j=0; j<N; j++){
                    if(arr[j][i1]<arr[j][i2])
                        cnt1++;
                    else if(arr[j][i1]==arr[j][i2])
                        cnt2++;
                    else
                        cnt3++;
                }
                if(cnt1+cnt2!=N && cnt3+cnt2!=N)
                    return false;
            }
        }
        return true;
    }

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_18248 {
    static int N, M;
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        //입력값 저장
        arr = new int[N][M];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        if(isPossible()) System.out.println("YES");
        else System.out.println("NO");
    }

    static boolean isPossible(){
        for(int i1=0; i1<M-1; i1++){ //기준
            for(int i2=i1+1; i2<M; i2++){ //비교 대상
                int cnt1 = 0;
                int cnt2 = 0;
                int cnt3 = 0;
                for(int j=0; j<N; j++){
                    if(arr[j][i1]<arr[j][i2])
                        cnt1++;
                    else if(arr[j][i1]==arr[j][i2])
                        cnt2++;
                    else
                        cnt3++;
                }
                if(cnt1+cnt2!=N && cnt3+cnt2!=N)
                    return false;
            }
        }
        return true;
    }
}

 

풀이 2

두 번째는 정렬로 푸는 방법이다. 대부분 이 방법으로 풀던데 나는 전혀 생각 못 한 방법이다.

 

1. 한 사람이 몇 개의 종소리를 들었는지 합을 구함

2. 가장 많이 들은 사람 순으로 정렬 -> 가장 많이 들은 사람이 종과 가까운사람

3. 어떤 한 사람이 들었는데(1) 그보다 뒤에 있는 사람이 못 들은 경우(0) 모순

4. 모순을 찾으면 NO를 출력, 못 찾으면 YES를 출력

 

	타종 M번
사람 N명		1	2	3	4
	1	0	0	0	1
	2	0	0	0	0
	3	0	0	0	0
	4	1	1	1	0

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class boj_18248 {
    static StringTokenizer st;
    static int N, M;
    static String[] sound;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        sound = new String[N];

        if (N == 1) {
            System.out.println("YES");
            return;
        }

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < M; j++) {
                sb.append(st.nextToken());
            }
            sound[i] = sb.toString();
        }
		
        //사람을 종과 가까운 순서로 정렬
        Arrays.sort(sound, Collections.reverseOrder());
		
        for (int i = 0; i < M; i++) {
            char cur = sound[0].charAt(i);
            char prev = sound[1].charAt(i);
            for (int j = 1; j < N; j++) {
                cur = sound[j].charAt(i);
                prev = sound[j - 1].charAt(i);

                if (prev < cur) {
                    System.out.println("NO");
                    return;
                }
            }
        }
        System.out.println("YES");
    }
}

 

 

Note