백준[2517] 달리기

박지호·2022년 7월 12일
0

백준 2517 달리기

Language

Java

Input

첫 번째 줄에는 선수의 수 N.
두 번째 줄부터는 현재 등수 순서대로 해당 선수의 실력을 입력받는다.

Output

각 선수의 자신의 앞 선수 중 자신보다 실력 수치가 낮은 선수만을 앞지를 수 있다. 각 선수의 최대 등수를 차례대로 출력한다.

문제 이해 및 풀이

기본적인 idea는 간단하다.
선수의 바로 앞 선수까지 탐색해서 만약 선수보다 실력이 낮다면 앞지를 수 있는 선수로 탐색한다.
(현재 등수 - 앞지를 수 있는 선수의 수) = (최대 가능 등수)가 된다.

하지만 0+1+2+...+N-1 즉, O(N^2)의 시간 복잡도를 지니게 되고, N은 최대 500,000이 되므로 최악의 경우 대략 5000000*5000000 / 2 의 연산을 해야한다. 1억번 연산이 1초라고 할 때, 이는 제한시간인 1초를 훌쩍 뛰어넘는다.

그래서 시간복잡도를 줄일 방법을 생각하여야 하고, 특정 자료구조나 알고리즘을 차용해볼 필요가 있는 것이다.

  1. 좌표 압축

선수의 실력값은 최대 1,000,000,000의 값을 가진다. 하지만 우리에게 필요한 것은 절대적인 선수의 실력값이 아닌, 선수끼리의 상대적인 실력값이다. 따라서 실력값을 실력 등수로 재정의 해준다. 실력 등수는 실력값이 낮을 수록 낮게 책정한다.

  1. 인덱스 트리 생성

값이 상당히 많으므로 우리는 최소한 시간복잡도를 O(NlogN)까지는 줄여야 할 것이다. O(NlogN)의 시간복잡도를 가지는 자료구조를 생각해보자면, (특정) 정렬, priority queue, index tree 등이 있을 것이다.

index tree를 생각해보자.

Index Tree는 내부노드와 리프노드로 나뉜다. 리프노드에는 배열의 값이 들어가고, 내부노드에는 구간 합이 들어간다.

여기에서는 리프노트에 모두 0이 들어가도록 초기화해준다.

  1. 인덱스 트리를 활용하여 앞선 선수 파악
    및 최대 등수 갱신

로직은 다음과 같다.

첫 번째 선수부터 N번째 선수까지 차례대로 진행해준다. 재정의된 실력등수의 리프노드에 값을 update해준 후, 0부터 해당실력까지의 구간 합을 구하면 앞선 선수 중 앞지를 수 있는 선수의 수가 나온다.

현재 등수 순서대로 진행하기에 앞선 선수만을 고려할 수 있게된다.

필요한 함수

필요한 함수는 크게 두 개로 나눌 수 있다.

1. update 함수
리프노드의 값을 바꿔주고 그에 따라 구간 합을 다시 설정해서 tree를 업데이트 해주는 함수이다. 모든 실력값이 다르므로 실력 재정의값도 다를 것이다. 따라서 업데이터는 node 값 + 1, 그의 parent 값 + 1만 하면 그 이외의 업데이트는 필요 없다.

public static void update(int idx) {
//해당 노드와 해당 노드의 부모노드를 거슬러 올라가며 + 1 해주면 된다
		while(idx>=1) {  //루트노드까지 업데이트
			tree[idx] += 1;
			idx /= 2; //부모노드로 이동
		}
	}

2. sum 함수

0번째 부터 idx-1까지의 구간합을 구하면 앞설 수 있는 선수의 수가 도출된다. 이를 위해 index tree의 0번째 리프노드부터 idx-1번째 리프노드까지의 구간합을 구하는 함수가 필요하다.

//i번째부터 j번째까지 구간합을 구하는 함수
	public static int sum(int i, int j,int tmpN) {
		
		//각 번째에 맞는 리프노트 찾기
		i = i + tmpN -1;
		j = j + tmpN -1;
		
		//합 담기
		int sum = 0;
		
		//두 좌표가 엇갈릴 때 까지 반복
		while(i<=j) {
			//i가 right child라면
			if(i % 2 == 1) {
				sum += tree[i]; //parent는 구간을 포함하지 않으므로 i의 값을 sum에 더함
			}
			//j가 left child라면
			if(j % 2 == 0) {
				sum += tree[j];
			}
			i = (i+1)/2;
			j = (j-1)/2;
		}
		return sum;
	}

Code

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

class Person{
	int idx; long skill;
	public Person(int idx,long skill){
		this.idx = idx; //현재 등수 - 1을 인덱스로 넣는다.
		this.skill = skill; //실력 값 (실력 재정의 값)을 넣는다.
	}
	
}
public class Main {
	public static ArrayList<Person> people;
	public static int[] tree;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		//INPUT
		String str = br.readLine();
		int num = Integer.parseInt(str); // 선수의 수
		
		people = new ArrayList<>();
		//실력 저장 + 계수 정렬을 위한 세팅
		for(int i = 0; i<num;i++) {
			str = br.readLine();
			people.add(new Person(i,Long.parseLong(str))); //idx와 skill을 저장
		}
		//skill 순서에 따라 ArrayList sorting + skill값 재정의
		Collections.sort(people,new peopleComparator());
		
		for(int i = 0;i<num;i++) {	
			people.get(i).skill = i+1;
		}
		
		
		Collections.sort(people,new com_idx());
		
		
		int tmpN;
		for(tmpN=1; tmpN<num; tmpN*=2);
		
		int []Run = new int[num]; //최종 등수를 담을 배열.
		tree = new int[tmpN*2]; //index tree 생성
		
		//초기화
		for(int i = 0;i<2*tmpN;i++) {
			tree[i] = 0;
		}
		
		//people 리스트에서 하나씩 꺼내가면서 tree에 담아준 후
		// 구간합을 구해서 run에 넣어준다.
		
		//만약 첫번째 주자의 skill 등수가 2라면
		//두번째 리프노드에 +1을 해주고 1까지의 구간합을 구한 후 index-합이 답이 된다.
		for(int i = 0; i<num;i++) {
			//주자의 skill의 리프노드 값을 구한다.
			int skill = (int) people.get(i).skill;
			int tmp_skill = (int) (skill+ tmpN -1);
			
			//더한 값을 반영하여 tree를 업데이트
			update(tmp_skill);
			//구간합 구하기
			Run[i] = (i+1) - sum(1,skill-1,tmpN); //(i+1)부터 skill이전 (skill-1)의 구간합 구하기
		}
		
		for(int i = 0; i<num;i++) {
			bw.write(Run[i]+"\n");
		}
		br.close();
		bw.flush();
	}
	//idx 번째 값을 +1 한다.
	public static void update(int idx) {
		while(idx>=1) {
			tree[idx] += 1;
			idx /= 2;
		}
	}
	//i번째부터 j번째까지 구간합을 구하는 함수
	public static int sum(int i, int j,int tmpN) {
		
		//각 번째에 맞는 리프노트 찾기
		i = i + tmpN -1;
		j = j + tmpN -1;
		
		//합 담기
		int sum = 0;
		
		//두 좌표가 엇갈릴 때 까지 반복
		while(i<=j) {
			//i가 right child라면
			if(i % 2 == 1) {
				sum += tree[i]; //parent는 구간을 포함하지 않으므로 i의 값을 sum에 더함
			}
			//j가 left child라면
			if(j % 2 == 0) {
				sum += tree[j];
			}
			i = (i+1)/2;
			j = (j-1)/2;
		}
		return sum;
	}

}

class peopleComparator implements Comparator<Person>{

	@Override
	public int compare(Person o1, Person o2) {
		if(o1.skill>o2.skill) return 1;
		else if(o1.skill < o2.skill) return -1;
		else return 0;
	}
	
}

class com_idx implements Comparator<Person>{

	@Override
	public int compare(Person o1, Person o2) {
		if(o1.idx>o2.idx) return 1;
		else if(o1.idx < o2.idx) return -1;
		else return 0;
	}
	
}

check

  • 인덱스 트리를 활용하는 문제

  • 처음에 문제를 접했을 때는 인덱스 트리를 활용하는 문제인지 가늠하지 못하였다.

  • 시간복잡도를 계산해보고 시간 제한 조건에 맞는지 체크 -> 적당한 자료구조 찾아보기의 루트로 적당한 해결방법을 모색해보자.

0개의 댓글