[BOJ 백준] 달리기(2517) C++, Java

링크 : https://www.acmicpc.net/problem/2517

2517번: 달리기

문제 설명 : 

KOI 장거리 달리기 대회가 진행되어 모든 선수가 반환점을 넘었다. 각 선수의 입장에서 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 남은 거리 동안 앞지르는 것은 불가능하다. 반대로, 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있으면 남은 거리 동안 앞지르는 것이 가능하다. 이러한 가정 하에서 각 선수는 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다. 

각 선수의 평소 실력은 정수로 주어지는데 더 큰 값이 더 좋은 실력을 의미한다. 현재 달리고 있는 선수를 앞에서 부터 표시했을 때 평소 실력이 각각 2, 8, 10, 7, 1, 9, 4, 15라고 하면 각 선수가 얻을 수 있는 최선의 등수는 (같은 순서로) 각각 1, 1, 1, 3, 5, 2, 5, 1이 된다. 예를 들어, 4번째로 달리고 있는 평소 실력이 7인 선수는 그 앞에서 달리고 있는 선수들 중 평소 실력이 2인 선수만 앞지르는 것이 가능하고 평소실력이 8과 10인 선수들은 앞지르는 것이 불가능하므로, 최선의 등수는 3등이 된다.

선수들의 평소 실력을 현재 달리고 있는 순서대로 입력 받아서 각 선수의 최선의 등수를 계산하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다.  

 

출력 : 

각 선수의 최선의 등수를 나타내는 정수 N개를 입력에 주어진 선수 순서와 동일한 순서로 한 줄에 하나씩 출력한다.

 

예제 입력 : 

8
2
8
10
7
1
9
4
15

 

예제 출력 : 

1
1
1
3
5
2
5
1

 

 

접근법 : 

1) 어떻게 풀 것인가?

50만명의 선수.

최종 가능한 순위를 체크하려면 모든 선수의 speed를 입력받은 후, 다시 처음부터 선수들의 speed를 체크해야한다.

 

단순하게 접근하면 다시 처음부터 id까지 speed가 낮은 선수를 count하면 된다.

이렇게 할 경우 시간복잡도 50만 제곱으로 시간초과가 발생한다.

 

문제의 출력을 위해선 결국 N번 확인 해야하기에 logN의 복잡도를 가지는 자료구조로 선수들의 속도를 구조화해야 

N * log N 의 시간복잡도로 문제를 풀 수 있다.

 

logN의 시간복잡도를 가지는 자료구조, 모든 선수들의 속도를 알 수 있을때, 구간에서의 합을 안다면 답을 구할 수 있다.

 

logN의 시간복잡도 + 구간합 = 인덱스드트리 로 해결 가능한 문제이다.

 

기본 구간합 문제에 비해 주의해야할 부분은 인덱스드트리를 초기에 세팅하는 것이 아니라 0으로 만들고

1) speed가 가장 빠른 녀석부터 indexed tree 최초 순위 위치에 1로 갱신한다. 

2) 1로 갱신하고 바로 최초 1위~방금녀석의 최초 순위 까지 구간합을 구한다.

   (왜냐면 현재 속도 기준 더 빠른 녀석들만 indexed tree 에 1이란 값으로 추가됐기 때문에)

3) 마지막까지 반복한다.

 

하면 쉽게 정답배열을 구할 수 있고 그 내용을 최초 id 순서에 맞게 출력하면 끝이다.

 

참고 : 세그먼트 트리 

https://www.acmicpc.net/blog/view/9

세그먼트 트리 (Segment Tree)

 

2) 시간복잡도

인덱스드트리 값 수정시 시간복잡도 logN, 구간합 구할때 시간복잡도 logN으로 N번수행하고 각각 2번 발생하므로

50만*2*logN = 1,000,000*log500000 의 시간복잡도로 약 200만으로 여유있으나, 

최초 입력받은 데이터를 sort할때도 N * logN이 발생하는 등 시간적으로 엄청 넉넉하지는 않다.

(Java 기준 -  1,800ms)

 

3) 공간복잡도

N이 50만이므로 인덱스드트리를 넉넉하게 만들고, 최초 입력을 넉넉하게 받아도 수백만의 int 배열이므로 넉넉하다.

1,000만개의 int 배열의 크기는 4Bytes * 1000만 = 약 38Mbytes

 

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

인덱스드트리의 활용. 어떻게 문제에 적용할 것인가에 대한 고민.

인덱스드트리가 아닌 Merge Sort 로 푸는 방법에 대한 고민.

 

C++코드 : 

// 달리기 2517 C++
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <vector>
#include <algorithm>

#define MAX (500000+2)

using namespace std;

// first : 선수 id,  second : 스피드
typedef pair<int, int> pii;

int N, nn;

pii playerInfo[MAX];
int ans[MAX];

int indexedTree[1048576+2];

void input();
void makeIndexedTree();
void edit(int id, int value);
int sum(int start, int end);
void output();

bool playerComp(const pii &a, const pii &b) {
	if (a.second > b.second) return true;
	return false;
}

int main() {
	// 1. 입력받는다
	freopen("input.txt", "r", stdin);
	input();

	// 2. 선수 정보를 speed 순으로 정렬
	sort(playerInfo, playerInfo + N+1, playerComp);


	// 3. indexedTree를 만들면서 정답배열에 답 추가
	makeIndexedTree();

	// 4. 정답배열 출력
	output();

	return 0;
}

void input() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		// first 선수 id / second 속도
		playerInfo[i].first = i;
		scanf("%d", &playerInfo[i].second);
	}
}

void makeIndexedTree() {
	// 인덱스드트리 크기 선언 (N보다 큰 최소 2^n)
	for (nn = 1; nn < N; nn *= 2);
	
	for (int i = 0; i < N; i++) {
		pii cur = playerInfo[i];
		// 지금 들어온 선수를 인덱스드트리에 넣기
		edit(cur.first, 1);
		// 1 ~ 최초순위까지 이미 들어온 선수 count = 가능한 최고 순위 
		ans[cur.first] = sum(1, cur.first);
	}

}

void edit(int id, int value) {
	int x = id + nn - 1;
	// 인덱스드트리 위치에 value로 값을 덮어쓰고
	indexedTree[x] = value;
	x /= 2;
	while (x > 0) {
		indexedTree[x] = indexedTree[x * 2] + indexedTree[x * 2 + 1];
		x /= 2;
	}
	return;
}

int sum(int start, int end) {
	int l = start + nn - 1;
	int r = end + nn - 1;
	int ret = 0;
	while (l <= r) {
		if ((l & 1) == 1) ret += indexedTree[l++];	// 왼쪽 id가 홀수이면 값이 튀므로 더해주고 l++ 해줌 (짝수부터 시작해야하니까)
		if ((r & 1) == 0) ret += indexedTree[r--];	// 오른쪽 id가 짝수이면 값이 튀므로 더해주고 r-- 해줌 (홀수로 끝나야하니까)
		l /= 2;	// 위로 올라가기
		r /= 2;	// 위로 올라가기
	}
	return ret;
}

void output() {
	for (int i = 1; i <= N; i++) {
		printf("%d\n", ans[i]);
	}
}

#endif

 

Java 코드 : 

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

// 달리기 백준 2517
public class Main {
	
	// 선수 id : 현재 순서, speed : 속도
	static class player implements Comparable<player>{
		int id, speed;
		
		public player(int id, int speed) {
			this.id = id;
			this.speed = speed;
		}
		
		// 내림차순 정렬
		@Override
		public int compareTo(player o) {
			return o.speed - this.speed;
		}
		
	}
	
	static int N, offset;					// N 선수 숫자,	offset 인덱스드트리 기준점 (2^n)
	static int[] indexedTree;			// 인덱스드트리
	static player[] playerList;				// 선수의 playerList (현재순위 -> speed순 정렬 예정)
	static int[] ans;					// 정답출력용 배열
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// N 입력
		N = Integer.parseInt(br.readLine());
		playerList = new player[N];
		
		// i번째 선수의 id와 speed를 playerList 배열에 넣음
		for(int i=0; i<N; i++) {
			playerList[i] = new player(i, Integer.parseInt(br.readLine()));
		}
		// speed 기준 내림차순 정렬		
		Arrays.sort(playerList);
				
		for (offset=1; offset<N; offset*=2);	    // 인덱스드트리 크기 특정 및 선언   (N보다 큰 최소 2^N)
		indexedTree = new int[offset*2+2];
		ans = new int[N];				// 정답출력 배열
		
		// playerList에서 선수 뽑으면서 speed 제일 높은 선수부터 indexedTree에 넣고 합을 구함 = speed로 역전 가능한 최고 순위
		for (int i=0; i<N; i++) {
			player cur = playerList[i];
			// 지금 들어온 선수를 인덱스드트리에 넣기
			update(cur.id, 1);
			// 1 ~ 최초순위까지 이미 들어온 선수 count = 가능한 최고 순위 
			ans[cur.id] = sum(0, cur.id);  
		}
		
		// 정답배열 출력
		for (int i=0; i<N; i++) {
			bw.write(String.valueOf(ans[i])+"\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 인덱스드트리 수정 1) 해당 id 값 수정 2) 위로 올라가면서 값 갱신 -> logN의 시간복잡도
	static void update(int id, int value) {
		int x = id + offset;
		// 인덱스드트리 위치에 value로 값을 덮어쓰고
		indexedTree[x] = value;
		while(x>0) {
			x /=2;
			indexedTree[x] = indexedTree[x*2] + indexedTree[x * 2 + 1];
		}
		return;
	}
	
	// 인덱스드트리 합 구하기 위로 올라가면서 합 구하기
	static int sum(int start, int end) {
		int l = start + offset;
		int r = end + offset;
		int ret = 0;
		while(l<=r) {
			if ((l & 1) == 1) ret += indexedTree[l++];	// 왼쪽 id가 홀수이면 값이 튀므로 더해주고 l++ 해줌 (짝수부터 시작해야하니까)
			if ((r & 1) == 0) ret += indexedTree[r--];	// 오른쪽 id가 짝수이면 값이 튀므로 더해주고 r-- 해줌 (홀수로 끝나야하니까)
			l/=2;	// 위로 올라가기
			r/=2;	// 위로 올라가기
		}
		return ret;
	}
}