BOJ 백준 2336 굉장한 학생

문제 : https://www.acmicpc.net/problem/2336

 

[ 문제 요약 ]

• A가 B보다 3가지 성적이 모두 좋다면 A는 대단한 것이고, 이 A보다 대단한 학생이 없으면 A를 굉장하다고 합니다. 여기서 굉장한 학생의 수를 구하는 것입니다.

[ 테스트 케이스 설명 ]

10 // 학생 수 1<=500,000
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 // 각 랭크별 학생 번호

 

[ 문제 해설 ]

 

문제를 간단하게 말해서 3개 과목 모두 나보다 순위가 작은 사람이 없으면 나는 굉장한 학생이 되는 것입니다.

 

그래서 입력이 3줄로 들어올 때, 한 학생의 3가지 과목 순위를 담을 객체를 만들어, 각 학생마다 순위들을 몰아서 하나의 객체에 저장해 놓습니다.

 

그럼 하나의 객체에는 과목(1), 과목(2), 과목(3)의 순위가 각각 들어가 있을 텐데, 이를 과목(1)의 순위 기준으로 오름차순 정렬합니다.

 

정렬한 후 첫 번째 객체는 무조건 굉장한 학생일 것입니다. 그 이유는 내 첫 번째 과목의 순위가 1등이기 때문에 당연히 나보다 3과목의 순위가 모두 작은 학생이 없을 것이기 때문입니다.

 

정렬된 배열의 두 번째 객체부터는 확인을 해봐야 합니다.

 

두 번째 객체는 과목(1)의 순위가 두 번째이기 때문에, 과목(2)와 과목(3)의 순위가 어떤지 파악해야 합니다. 파악을 하는 기준은,

 

내 왼편에 있는, 즉 이미 탐색한 객체들의 과목(2), 과목(3)의 순위들만 확인하면 됩니다.

 

이미 과목(1) 기준으로 정렬했기 때문에 내 왼편의 객체들은 과목(1)이 나보다 작다는 것이 확인되었으니,

 

그들의 과목(2)와 과목(3)의 순위가 내 과목(2)와 내 과목(3)보다 모두 작은 게 있다면 나는 굉장한 학생이 아닐 것입니다.

 

모두 작은 게 없다면 나는 굉장한 학생이 됩니다.

 

그럼 내 왼편의 객체들의 과목(2)와 과목(3)의 순위를 어떻게 빠르게 탐색할 수 있을까요?

 

방법은 세그먼트 트리를 이용하며, 세그먼트 트리의 index는 과목(2)의 값을,

 

인덱스의 저장하는 value는 과목(3)의 값으로 하고, 최솟값을 구하는 세그먼트 트리를 만들어 해결할 수 있습니다.

 

[ 정답 코드 ]

 

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

class Main{
	
	static final int MAX = 1<<30;
	static int[] tree;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N		= Integer.parseInt(br.readLine());	// 1 ≤ N ≤ 500,000
		Node[] node = new Node[N];
		tree		= new int[N * 4];
		
		for(int i=0; i<N; i++)
			node[i] = new Node(0,0,0);
		
		for(int i=0; i<3; i++)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int rnk=1; rnk<=N; rnk++)
			{
				int index = Integer.parseInt(st.nextToken()) - 1;// 해당 학생의 번호

				if(i == 0)
					node[index].rank1 = rnk;
				else if(i == 1)
					node[index].rank2 = rnk;
				else
					node[index].rank3 = rnk;
			}
		}
		
		Arrays.fill(tree, MAX);
		Arrays.sort(node);
		
		int ans = 0;
		
		for(Node now : node)
		{
			int min = query( 1, 1, N, 1, now.rank2 );
			
			if(min > now.rank3)
				++ans;
			
			update( 1, 1, N, now.rank2, now.rank3 );
		}
		
		System.out.print(ans);
	}
	public static void update(int treeNode, int s, int e, int targetIdx, int value) {
		if(e < targetIdx || targetIdx < s)
			return;
		
		if(s == e)
		{
			tree[treeNode] = value;
			return;
		}
		
		int mid = (s + e) >> 1;
		
		update(treeNode << 1, s, mid, targetIdx, value);
		update(treeNode << 1 | 1, mid + 1, e, targetIdx, value);
		
		tree[treeNode] = Math.min(tree[treeNode << 1], tree[treeNode << 1 | 1]);
	}
	public static int query(int treeNode, int s, int e, int left, int right) {
		if(e < left || right < s)
			return MAX;
		
		if(left<=s && e<=right)
			return tree[treeNode];
		
		int mid = (s + e) >> 1;
		int l	= query(treeNode << 1, s, mid, left, right);
		int r	= query(treeNode << 1 | 1, mid + 1, e, left, right);
		
		return Math.min(l, r);
	}
}

class Node implements Comparable<Node>{
	int rank1, rank2, rank3;
	Node(int r1, int r2, int r3){
		rank1 = r1;
		rank2 = r2;
		rank3 = r3;
	}
	@Override
	public int compareTo(Node o) {
		return rank1 - o.rank1;
	}
}