2517 달리기 - 백준

달리기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

8823

3722

2497

45.817%

문제

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개를 입력에 주어진 선수 순서와 동일한 순서로 한 줄에 하나씩 출력한다.

예제 입력 1 복사

8
2
8
10
7
1
9
4
15

예제 출력 1 복사

1
1
1
3
5
2
5
1

풀이

현재 위치에 있는 선수는 자기보다 앞에 있는 선수보다 몇 번째로 앞서있는지 알아야 한다.

 

일반적인 brutforce 방법은 1~50만 계산하면 답이 없다.(timeover가 날 가능성 높음) - 이렇게 풀라고 하는건 아닌거 같음.

 

 

방법

1. 일단 능력 높은 순으로 정렬을 진행(자신의 앞에 있는 자신보다 능력이 높은 사람의 수 +1 이 자기 등수이기 때문에 능력순 정렬

2. 배열에 접근해서 해당 인덱스에 있는 사람의 인덱스 번호를 확인 후 1~ 구한 인덱스 사이에서 앞에 존재하는 인원수 구하고 그 인원수 +1

3. 자신의 앞에 기록된 사람 수는 추월이 불가능하기에 1~자기 인덱스 사이의 모든 사람수 +1이 됨. 능력 떨어지는 사람도 자기가 앞에 있으면 1 (결국 자기 앞에 사람 수를 세어야 함)

 

 

문제 풀다가 발생한 이슈

1. 초기에 sysout 을 사용했더니 타임 오버가 뜨길래 먼가 한참 찾아다녔다.

2. 결국 sysout이 생각보다 시간을 많이 잡아먹는다는 것을 알게되었고 bufferedreader를 이용하여 출력을 하였더니 성공하였다.

 

코드

package test2517;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static List<Runner> inputArr;

	static class Runner {
		int index;
		int ability;

		public Runner(int index, int ability) {
			this.index = index;
			this.ability = ability;
		}
	}

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner(System.in);

		N = sc.nextInt();

		inputArr = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			inputArr.add(new Runner(i, sc.nextInt()));
		}

		// 내림차순 정렬
		Collections.sort(inputArr, (a, b) -> (a.ability - b.ability));

		for (int i = 0; i < inputArr.size(); i++) {
			Runner runner = inputArr.get(i);
			runner.ability = i + 1;
		}
		Collections.sort(inputArr, (a, b) -> (a.index - b.index));

		SegmentTree segTree = new SegmentTree();

		segTree.init(sc.writer);
		
		sc.close();
	}

	static class SegmentTree {
		int segTree[];

		SegmentTree() {
			segTree = new int[4 * N]; // segmentTree의 크기는 4N을 넘지 않는다.
		}

		void init(BufferedWriter writer) throws IOException {
			for(int i=1; i<=N; i++) {
				int ability = inputArr.get(i-1).ability;
				writer.write(i- query(1,N, 1, 1,ability) + "\n");
				update(1,N,1, ability);
			}
		}

		int query(int start, int end, int node, int left, long right) {
			if (left > end || right < start) {
				return 0;
			}
			if (left <= start && end <= right) {
				return segTree[node];
			}

			int mid = (start + end) / 2;
			return query(start, mid, node * 2, left, right) + query(mid + 1, end, node * 2 + 1, left, right);

		}

		int update(int start, int end, int node, int index) {
			if (index < start || index > end) {
				return segTree[node];
			}

			if (start == end) {
				return segTree[node] += 1;
			}

			int mid = (start + end) / 2;
			return segTree[node] = update(start, mid, node * 2, index) + update(mid + 1, end, node * 2 + 1, index);

		}

	}

	static class MyScanner {
		final BufferedReader reader;
		final BufferedWriter writer;
		StringTokenizer tokenizer = null;

		MyScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			writer = new BufferedWriter(new OutputStreamWriter(System.out));
		}

		String nextToken() throws IOException {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}
			return tokenizer.nextToken();
		}

		int nextInt() throws Exception {
			return Integer.parseInt(nextToken());
		}

		long nextLong() throws Exception {
			return Long.parseLong(nextToken());
		}

		void close() throws IOException {
			reader.close();
			writer.close();
		}

	}
}