개요

백준2336: 굉장한 학생

• 입력
  첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 세 개의 줄에는 각 시험에서 1등인 학생부터 N등인 학생이 순서대로 주어진다. 학생의 번호는 1부터 N까지 매겨져 있다.

• 출력
  첫째 줄에 '굉장한' 학생의 수를 출력한다.

접근 방식

1. 전혀 감이 안와서 찾아 봤더니, 기본적으로 세그먼트 트리를 이용한다.

2. 일단 크기 3의 벡터를 학생 수만큼 만들어주고, 벡터의 행 index엔
   학생의 번호, 열 index엔 몇번째 시험인지, value엔 성적을 입력해줬다.

   	//시험 번호 0~2
   	for (int i = 0; i < 3; i++) {
   		//등수
   		for (int j = 0; j < N; j++) {
   			//학생 번호
   			cin >> tmpInput;
   
   			//학생번호(index라서 -1), 몇번째 시험, 등수
   			v[tmpInput-1][i]=j;
   
   		}
   	}

3. 그 후, 첫번째 시험의 등수를 기준으로 정렬해준다.

   //첫번째 등수 기준으로 정렬 (어떤학생이 몇점맞았냐는 안중요하고 
   //성적이 굉장한 학생수만 중요하므로 학생순서가 섞여도 상관없다)
   sort(v.begin(), v.end());

4. 첫번째 시험의 등수로 정렬된 상태에서 (0<i<N일때)
   i+1~N 번째 학생은 i번째 학생보다 대단할수 없다.(이미 첫번째 시험부터 져서)

5. 따라서 i번째 학생은 0~i-1번째 학생만 경계하면 되고, 0~ i-1번째 학생이
   i번째 학생보다 두번째 세번째 등수가 더 작다면 i는 굉장할 수 없다.

6. 두번째 세번째 등수를 쉽게 알기 위해
   세그먼트 트리 리프노드의 인덱스를 2번째 시험등수,
   값을 세번째 시험등수로 정의한다.
   또한, 세그먼트 트리를 구간 최소합 트리로 정한다.

7. 이렇게 정의를 하게 되면 이제 0~ i번째 학생의 두번째 시험등수의 구간의 최소합이 i번째 학생의 3번째 시험등수보다 작은지 비교하면 된다.
   ->0부터 (i번째 학생의 두번째 시험등수)의 구간 = i번째 학생보다 2번째 시험을 잘본 구간
   -> 0부터 (i번째 학생의 두번째 시험등수)의 구간의 최소값 = 0~ i-1번째 학생들의 3번째 시험 등수의 최소값

   //sort가 되어있는 상태이므로 v는 첫번째 시험의 등수로 정렬되어있다.
   for (int i = 0; i < N; i++) {
   	//첫번째 시험등수로 정렬되어있으므로 이미 i번째학생이 첫번째 시험로 이겨서\
   	i번째 학생 뒤의 학생들은 i번째 학생보다 대단할수 없음.\
   	따라서 i번째학생은 자신의 앞 순서의 학생들과 2번째 3번째를 비교해야함.\
   
   	//따라서 자신의 두번째 시험 성적 보다 작은 index구간의\
      최소 등수값이 자신의 세번째 등수보다 크다면 자신은 굉장하다. 
   	if (FindMin(0, v[i][1], 1, 0, firstLeafNodeIdx - 1) > v[i][2]) result++;

8. 그 후, 자신의 정보를 세그먼트 트리에 업데이트해준다.

   //자신의 두번째 시험성수 index에 자신의 세번째 시험등수 value로 세그트리 업데이트해줌
   SetAncestorNode(v[i][1], v[i][2]);

전체코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//리프노드 구성은 한 학생의 두번째 시험등수가 index, 세번째 시험등수가 value 
int segTree[1'048'576];
int N,firstLeafNodeIdx=1,MAXINT = 1'000'000'000;
//학생마다 성적용 크기 3짜리 벡터 할당해줌 
vector<vector<int>> v;

void SetAncestorNode(int idx,int val) {
	int tmpIdx = idx + firstLeafNodeIdx;
	segTree[tmpIdx] = val;
	while (tmpIdx > 1) {
		tmpIdx /= 2;
		segTree[tmpIdx] = min(segTree[tmpIdx * 2], segTree[tmpIdx * 2 + 1]);
	}
}

int FindMin(int targetL, int targetR, int nodeNum, int curL, int curR) {
	if (targetL > curR || curL > targetR) return MAXINT;
	if (targetL <= curL && curR <= targetR) return segTree[nodeNum];
	int mid = (curL + curR) / 2;
	return min(FindMin(targetL, targetR, nodeNum * 2, curL, mid), FindMin(targetL, targetR, nodeNum * 2 + 1, mid + 1, curR));
}

void Solution() {
	int result=0;

	//sort가 되어있는 상태이므로 v는 첫번째 시험의 등수로 정렬되어있다.
	for (int i = 0; i < N; i++) {
		//첫번째 시험등수로 정렬되어있으므로 이미 i번째학생이 첫번째 시험으로 이겨서\
		i번째 학생 뒤의 학생들은 i번째 학생보다 대단할수 없음.\
		따라서 i번째학생은 자신의 앞 순서의 학생들과 2번째 3번째를 비교해야함.\

		//따라서 자신의 두번째 시험 성적 보다 작은 index구간의 최소 등수값이 자신의 세번째 등수보다 크다면 자신은 굉장하다. 
		if (FindMin(0, v[i][1], 1, 0, firstLeafNodeIdx - 1) > v[i][2]) result++;
		//자신의 두번째 시험성수 index에 자신의 세번째 시험등수 value로 세그트리 업데이트해줌
		SetAncestorNode(v[i][1], v[i][2]);
	}
	cout << result;
}

void Input() {
	int tmpInput=0;
	cin >> N;
	//구간 최소합 트리이므로 제일 큰 숫자로(여기선 10억) 채워준다.
	fill(segTree, segTree + 1'048'576, MAXINT);
	//크기3의 벡터를 학생 수만큼 할당해준다.
	v.resize(N, vector<int>(3));
	//세그먼트 트리의 리프노드의 시작점을 구해준다.
	while (firstLeafNodeIdx < N) firstLeafNodeIdx *= 2;

	//시험 번호 0~2
	for (int i = 0; i < 3; i++) {
		//등수
		for (int j = 0; j < N; j++) {
			//학생 번호
			cin >> tmpInput;

			//학생번호(index라서 -1), 몇번째 시험, 등수
			v[tmpInput-1][i]=j;

		}
	}

	//첫번째 등수 기준으로 정렬 (어떤학생이 몇점맞았냐는 안중요하고 
	//성적이 굉장한 학생수만 중요하므로 학생순서가 섞여도 상관없다)
	sort(v.begin(), v.end());
	Solution();

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

레퍼런스

참조한 https://jason9319.tistory.com/57 님의 블로그 링크