12월 11일 - 굉장한 학생[BOJ/2336]

문제 설명

N명의 학생들이 세 번의 시험을 치렀다. 각 시험에서는 같은 등수의 학생이 없도록 순위가 매겨졌으며, 세 번의 시험 결과를 바탕으로 다음 규칙에 따라 학생들을 평가한다:

• A 학생이 B 학생보다 세 번의 시험에서 모두 더 좋은 성적을 기록했다면, A는 B보다 '대단하다'고 한다.
• C 학생보다 '대단한' 학생이 한 명도 없으면, C를 '굉장하다'고 한다.

결국, 주어진 시험 결과에서 '굉장한' 학생의 수를 구하는 프로그램을 작성하는 것이 목표다.

Code

import java.io.*;
import java.util.*;

public class Main {

    static int[] tree;
    static int size;

    // 세그먼트 트리 업데이트
    static void update(int idx, int value) {
        idx += size;
        tree[idx] = value;
        while (idx > 1) {
            idx /= 2;
            tree[idx] = Math.min(tree[2 * idx], tree[2 * idx + 1]);
        }
    }

    // 세그먼트 트리 쿼리
    static int query(int left, int right) {
        left += size;
        right += size;
        int minValue = Integer.MAX_VALUE;

        while (left <= right) {
            if (left % 2 == 1) minValue = Math.min(minValue, tree[left++]);
            if (right % 2 == 0) minValue = Math.min(minValue, tree[right--]);
            left /= 2;
            right /= 2;
        }

        return minValue;
    }

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

        int[][] ranks = new int[N][3];
        for (int i = 0; i < 3; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int student = Integer.parseInt(st.nextToken());
                ranks[student - 1][i] = j + 1;
            }
        }

        // 학생들을 첫 번째 시험 순서대로 정렬
        Arrays.sort(ranks, Comparator.comparingInt(a -> a[0]));

        // 세그먼트 트리 초기화
        size = 1;
        while (size < N) size *= 2;
        tree = new int[2 * size];
        Arrays.fill(tree, Integer.MAX_VALUE);

        int result = N;
        for (int[] rank : ranks) {
            int rank1 = rank[0];
            int rank2 = rank[1];
            int rank3 = rank[2];

            if (query(0, rank2 - 1) < rank3) {
                result--;
            }
            update(rank2, rank3);
        }

        System.out.println(result);
    }
}

코드 설명

주요 로직

이 문제는 학생들의 시험 순위를 활용해 '굉장한' 학생을 효율적으로 찾아야 한다. 세그먼트 트리를 사용하여 각 학생에 대해 세 번의 시험 결과를 비교하면서 '굉장하다'는 조건을 만족하는 학생들을 필터링한다.

단계별 풀이 과정

1. 입력 처리 및 학생 순위 저장

int[][] ranks = new int[N][3];
for (int i = 0; i < 3; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int j = 0; j < N; j++) {
        int student = Integer.parseInt(st.nextToken());
        ranks[student - 1][i] = j + 1;
    }
}

• 입력으로 주어진 순위를 배열 ranks에 저장한다. 각 학생의 3번 시험 성적을 한 행에 저장하며, 인덱스는 학생 번호로 사용한다.

2. 첫 번째 시험 순위 기준 정렬

Arrays.sort(ranks, Comparator.comparingInt(a -> a[0]));

• 학생을 첫 번째 시험 순위를 기준으로 오름차순 정렬한다. 이후 순위 비교를 진행하면서 '굉장한' 학생을 판별한다.

3. 세그먼트 트리 초기화

size = 1;
while (size < N) size *= 2;
tree = new int[2 * size];
Arrays.fill(tree, Integer.MAX_VALUE);

• 세그먼트 트리를 사용해 두 번째 시험에서의 순위와 세 번째 시험에서의 순위를 효율적으로 관리한다. 초기값은 ∞로 설정한다.

4. 학생 순위 비교 및 결과 갱신

for (int[] rank : ranks) {
    int rank1 = rank[0];
    int rank2 = rank[1];
    int rank3 = rank[2];

    if (query(0, rank2 - 1) < rank3) {
        result--;
    }
    update(rank2, rank3);
}

• query(0, rank2 - 1)는 현재 학생보다 앞선 두 번째 시험 순위에서 최소 세 번째 시험 순위를 구한다.
• 이 값이 현재 학생의 세 번째 시험 순위보다 작으면 해당 학생은 '대단한' 학생이므로 '굉장한' 학생에서 제외된다.
• update(rank2, rank3)는 현재 학생의 두 번째 및 세 번째 시험 순위를 세그먼트 트리에 추가한다.

So...

이 문제는 세그먼트 트리와 정렬을 활용해 효율적으로 해결할 수 있었다. '굉장한' 학생의 조건을 판별하며 모든 학생을 순회하면서도 시간 복잡도를
𝑂(𝑁log⁡𝑁)으로 유지할 수 있었다. 이번 풀이를 통해 세그먼트 트리를 활용한 최적화 방법과 문제를 분해하는 사고 과정을 연습할 수 있었다.