글 읽기 - 굉장한 학생.. 반례가 무엇일까요?

tna1595 5년 전 0

22%에서 틀렸습니다가 뜨네요..

알고리즘 자체에 문제가 있는걸까요?

1번째 시험과 2번째 시험에 대해서 각각의 학생이 받은 등수를 rank 배열에 저장을 한 뒤에,

세번째 시험의 등수를 기준으로 계산을 해봤습니다.

예를 들어,

10

2 5 3 8 10 7 1 6 9 4

1 2 3 4 5 6 7 8 9 10

3 8 7 10 5 4 1 2 6 9

이라면,

rank1 : 7 1 3 10 2 8 6 4 9 5

rank2 : 1 2 3 4 5 6 7 8 9 10

1번 학생이 시험 1번에서 받은 등수는 rank1[1], 2번 학생이 시험 1번에서 받은 등수는 rank1[2]

이런 식으로 순위를 알 수 있게끔 입력을 받았습니다.

그 뒤 시험 1, 2에 관하여 tree1, tree2 를 펜윅트리로 만들었습니다.

세 번째 시험을 기준으로 첫 번째로 3이 들어오고, rank1[3] = 7, rank2[3] = 3 이기에,

현재 1번시험에서 7등 이전으로 들어온 것이 있는지를 확인하기 위해 1~7 까지의 구간합을 구하고,

2번시험에서는 3등 이전으로 들어온 것이 있는지를 확인하기 위해 1~3 까지의 구간합을 구합니다.

만약 두 개의 구간합 중 하나라도 0이라면, 현재 이 학생은 대단한 학생이라는 뜻입니다.

그 뒤 tree1 의 7을 1로 업데이트, tree2의 3을 1로 업데이트합니다.

위 차례를 반복하면서 대단학 학생의 수를 구하게끔 했습니다.

이 알고리즘에 반례가 있을까요?..

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

public class Main {
    static int tree1[];
    static int tree2[];
    static int N;

    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;

        N = Integer.parseInt(br.readLine());
        int rank1[] = new int[N + 1];
        int rank2[] = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int n = 1; n <= N; ++n) {
            rank1[Integer.parseInt(st.nextToken())] = n;
        }
        st = new StringTokenizer(br.readLine());
        for (int n = 1; n <= N; ++n) {
            rank2[Integer.parseInt(st.nextToken())] = n;
        } // 시험 1, 2에 관하여 rank 배열에 각 학생의 순위를 저장합니다.
        tree1 = new int[N + 1];
        tree2 = new int[N + 1];
        int result = 0; 
        st = new StringTokenizer(br.readLine());
        for (int n = 0; n < N; ++n) {
            int value = Integer.parseInt(st.nextToken());
            boolean isGreat = false;
            int rank1Value = rank1[value];
            int rank2Value = rank2[value];
            if (getSegment(rank1Value, 1) == 0 || getSegment(rank2Value, 2) == 0) isGreat = true;
            if (isGreat) result++; // 구간합이 하나라도 0인 게 있다면, 대단한 학생입니다.
            update(rank1Value, rank2Value); // tree를 업데이트합니다.
        }
        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
    }

    static void update(int rank1Value, int rank2Value) {
        int index = rank1Value;
        while (index <= N) {
            tree1[index]++;
            index += (index & -index);
        }
        index = rank2Value;
        while(index <= N){
            tree2[index]++;
            index += (index & -index);
        }
    }

    static int getSegment(int index, int treeIndex) {
        int sum = 0;
        while (index > 0) {
            sum += (treeIndex == 1) ? tree1[index] : tree2[index];
            index -= (index & -index);
        }
        return sum;
    }
}

tna1595 5년 전 3

6

1 5 3 4 2 6

1 2 6 4 3 5

5 2 3 4 1 6

이란 예외가 있었네요. 저 알고리즘은 위의 반례를 체크하지 못했습니다.

그래서 3이 나오고 원래 정답은 5입니다.

댓글을 작성하려면 로그인해야 합니다.