오답노트 #16564 : 히오스 프로게이머

풀이방법 및 문제점

2022.06.10

전체적인 알고리즘은 완성되었다.

그런데 check 함수의 시간복잡도가 문제이다. 여기 때문에 시간초과가 발생한다.

check만 상수시간이 걸리도록 바꾸면 해결될 것 같다.

 

 

...

 

 

구글링을 하다가 아래의 블로그 글을 발견했다.

백준 (BOJ) 16564 히오스 프로게이머 java

분명히 내 코드랑 똑같은 아이디어로 짠 코드인데 이 코드를 백준에 돌려보면 순식간에 정답처리가 된다. 대체 무슨 원리로 시간이 이렇게 많이 줄어드는지 납득이 안 된다.

 

다른 점이 뭐지?

 

첫째, 나는 함수형으로 코드를 짰고 이 사람은 그냥 Main 안에서만 해결했다는 것. 이에 따라 이 사람은 전역변수도 안 썼다는 것

 

둘째, 내 코드가 다음과 같다면

for(int i: champs) {
	if(i<lv) sum += (lv-i);
}

이 사람의 코드는 다음과 같다는 것

for(int i=0; i<n; i++) {
	int diff = mid-champs[i];
	if(diff>0) sum += diff;
}

 

셋째, 이 사람은 ans라는 변수와 Math.max()를 사용하여 정답을 확정했다는 것

 

넷째, mid 값을 정할 때 나는 /2를 사용했고 이 사람은 >>1로 쉬프트했다는 것

 

 

아니 애초에 두 코드 모두 N개의 모든 요소를 탐색하는 반복문이 while문 안에 들어가있는 이중 반복문이 있으니까 둘 다 시간초과가 나야 맞는 거 아닌가?

오히려 나는 N개 요소 탐색 중 break를 할 수 있게 해놨고 이 사람은 N개를 무조건 다 탐색하게 해놨으니 내 코드가 더 빨라야 하는 거 아닌가?

 

한 가지씩 바꾸어가며 제출해보는데 다 시간 초과가 난다. 미스터리다. 다른 코드들을 구글링해봐도 비슷한 의문이 남는다. 구글링해서 나온 코드들처럼 새로 코드를 짜 제출해서 정답처리는 되었지만 대체 왜 시간이 단축됐는지 이해가 되지 않았다. 이해가 될 때까지 정답 게시글은 안 쓸 것임...

 

코드

Java(2022.06.10)

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

public class Main {
	
	static int[] champs;
	static int n, k;
	
	//해당 레벨이 달성 가능한지 판별하는 함수
	static boolean check(int lv) {
		boolean result = false;
		int resource = k;
		for(int i: champs) {
			if(i<lv) {
				resource -= (lv-i);
				if(resource<0) break;
			}
			else {result = true; break;}
		}
		return result;
	}
	
	//이분탐색 함수
	static int bs() {
		int start = champs[0];
		int end = champs[0] + k;
		
		while(start<end) {
			int mid = (start+end)/2;
			if(check(mid)) start = mid;
			else end = mid-1;
		}
		
		return end;
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer (br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		champs = new int[n];
		for(int i=0; i<n; i++) {
			champs[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(champs);
		
		System.out.print(bs());
		
	}

}