백준 1946 - 신입 사원 (Java)

 

문제 개요

 

문제 개요

 

예제 입출력

 

---

 

풀이

 

문제에서 원하는 바를 한 줄로 요약하자면, 입사 지원자들을 평가하기 위한 두 종목의 점수가 주어질 때 지원자의 점수를 모두와 비교해서 전체적으로 적어도 한 개 이상의 점수가 높은 사람의 수를 구해야 한다.

 

사실 브루트 포스 방식으로 문제를 풀면 로직을 작성하는 것은 간단한 일인 것일지 모른다.

 

만약 브루트 포스로 접근한다면, 

1. 각 과목을 의미하는 배열 2개를 만들고(혹은 2차원 배열) 입력받은 값들을 저장한다.
2. 2 중첩 for문을 사용해서 각 지원자의 등수와 다른 모든 지원자의 등수를 비교한다. (1:n)
   • 한 지원자를 기준으로 다른 모두와 비교해야 하고, 이를 전체 지원자를 대상으로 실시해야 하기 때문에 시간 복잡도가 n²가 된다.
3. 루프를 돌면서 만약 비교하려는 상대가 자신보다 두 과목의 등수 모두 높은 경우에 해당 루프를 break 한다.
4. 루프를 모두 돌았음에도 불구하고 break 되지 않았다면 출력할 값에 +1 한다.

 

하지만 이런 식으로 코드를 작성해서 제출했더니 시간 초과라는 결과를 마주하게 되었다.

 

즉, 더 효율적인 코드를 작성하라는 것이었다.

 

그렇다면 어떻게 접근해야 할까?

 

n² 보다 효율적이어야 한다는 것은 for문을 중첩하여 반복하지 말라는 것과 같다. 즉, n의 시간 복잡도를 가지도록 for문을 한 번만 돌려서 답을 이끌어야 한다는 것과 같은 것이다.

 

이 부분에서 개인적으로 고민이 많았다. 왜냐면 for문을 한 번만 돌리면서 답을 이끌어내려면 비교하기 쉬운 상태가 되어야 하기 때문이다. 때문에 정렬을 해놓고 반복을 해볼까 생각도 했지만, 정렬을 하는 것 자체가 시간 복잡도로 인해 시간 초과를 불러올 것 같았다. 또한 Map을 사용해서 각 사람들에 대한 인덱스를 저장한다고 하더라도 정렬을 해야 했다.

 

솔직히 시간이 너무 걸려서 다른 사람들은 어떻게 풀었나 찾아봤다.

 

아마 대부분의 답은 아래와 같은 방법으로 입력 값을 받았다.

 

1. 입력을 받을 배열 하나를 선언한다.
2. 본격적으로 입력을 받을 때 첫 과목의 등수를 인덱스에, 두 번째 과목의 등수를 값에 저장한다.

 

사실 나는 위의 방식으로 작성된 코드를 보고도 몇 초간은 '이왜됨?' 이런 느낌이었지만, 어찌어찌 이해는 가능했다.

 

이 방법이 가능한 이유는 어차피 등수는 1부터 시작하고 중간에 빈 등수가 없는 것이 일반적이다. 또한, 문제에서 전제 조건으로 1부터 100000까지의 수가 등수가 될 수 있다고 했다.

 

결정적으로 동석차 등수가 없기 때문에 인덱스에 등수를 저장하는 방식이 결과적으로 과목 하나를 정렬하는 방법인 셈이다.

 

여기까지 보고 문제에서 원하는 답을 이끌어내기 위해 아래와 같은 과정의 알고리즘을 생각했다.

 

1. 입력받을 배열 하나를 선언한다.
2. 입력 값을 저장할 때 과목 중 하나는 인덱스에, 다른 하나는 값에 저장한다.
   
   • 따로 정렬을 하진 않았지만, 인덱스로 저장된 과목이 정렬된 것과 같은 효과를 볼 수 있다.
3. 반복문을 만들어 배열의 첫 번째 값을 기준으로 루프를 돌면서 기준 값보다 높은 등수라면 카운팅하고 기준 값을 교체한다.
   • 배열을 처음부터 루프로 돌 경우 사실상 인덱스로 설정한 과목에 대해서는 순서대로 루프를 도는 것과 같다.
   • 때문에 만약 특정 루프에서 기준 값보다 높은 등수가 발생해서 카운팅을 한 경우에 제대로 기준 값을 변경해주지 않는다면, 반례가 발생할 수 있다.
   • 여기서 반례란 예를 들어 (1/3), (2/1), (3,2)와 같은 테스트 케이스가 존재하고 기준 값을 변경하지 않은 경우에 답이 3이 나온다. 하지만 3 번째 지원자는 2 번째 지원자보다 모든 과목이 부족하므로 반례가 발생하는 것이다.
   • 위 반례를 해결하기 위해 첫 기준 값이었던 3에서 두 번째 루프를 돌 때 기준 값을 1로 변경해준다면 반례가 발생하는 것을 막을 수 있다.
4. 반복문이 종료되었을 때 카운팅 된 변수를 출력해준다.

 

---

 

코드

 

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCount = Integer.parseInt(br.readLine());

        for (int i=0 ; i<testCount ; i++) {
            int itemCount = Integer.parseInt(br.readLine());
            int[] arr = new int[itemCount+1];

            for (int n=0 ; n<itemCount ; n++) {
                String[] items = br.readLine().split(" ");
                arr[Integer.parseInt(items[0])] = Integer.parseInt(items[1]);
            }

            int count = 0;
            int min = arr[1];
            for (int n=1 ; n<=itemCount ; n++) {
                if (arr[n] > min)
                    continue;

                min=arr[n];
                count++;
            }
            System.out.println(count);
        }
    }
}

 

코드 리뷰

 

1. int형 변수 testCount에 입력받은 테스트 케이스의 개수를 저장한다.
2. for문으로 테스트 케이스의 개수만큼 반복문을 만든다.
3. 각 테스트에서 입력받을 지원자의 수를 int형 변수 itemCount에 저장한다.
4. 지원자들의 등수를 저장할 배열 arr를 선언한다.
   • 배열의 크기를 +1 해주는 이유는 등수는 1부터 시작하지만 배열의 인덱스는 0부터 시작하기 때문이다.
   • 값을 저장할 때 -1 연산 후 저장하는 방법도 있지만, 인덱스와 값의 두 군데 연산을 해야 한다.
   • 위에서 배열 크기만 +1 해줌으로써 불필요한 연산을 줄이도록 했다.
5. 등수를 입력받을 때 String.split(" ")을 사용해서 과목 별 등수를 받았고, int로 형변환 후 배열에 저장한다.
6. 입사 가능자를 의미하는 int형 변수 count를 선언한다.
7. int형 변수 min에 첫 번째 지원자 = 첫 과목에서 1등을 한 지원자의 두 번째 과목 등수를 의미하는 arr[1]를 저장한다.
8. 등수가 높다는 의미는 수치적으로 등수가 낮다는 것이기 때문에 현재 루프 지원자의 두 번째 등수가 기준 값보다 수치적으로 높다면 continue
   • 카운팅 하지 않겠다는 의미이다.
9. continue 되지 않았다는 의미는 기준 등수보다 수치적으로 작은 값, 즉 높은 등수를 의미하므로 min에 현재 루프 지원자의 두 번째 등수(arr[n])를 저장하고 count++로 카운팅 한다.
10. 반복문이 종료된 후 카운팅 된 값을 출력한다.

 

---

 

제출 결과

 

 

뭔가 오랜만에 풀면서 많이 헤맨 것 같다. 하지만 문제 접근 방법에 대한 새로운 레퍼토리를 얻은 것 같아 좋았다.