백준 챔피언 (Easy)(21319)

챔피언 (Easy)

1. 힌트

1) 어떤 격투기 선수가 챔피언이 될 수 있는지 여부를 확인하기 위해서는 $O(N)$의 시간이 필요하다. 당연히 $N$명의 선수에 대해서 모두 하면 시간 초과.

2) 전투력이 같은 선수들 중에서 맨 왼쪽 선수 제외하고는 전부 챔피언이 될 수 없다.

3) 2번 성질을 이용해서 맨 왼쪽에 존재하는 선수들 끼리만 비교한다면 $i$번째 선수가 챔피언이 될 수 있다면 $i + 1$

2. 접근

단, 각 격투기 선수들의 초기 전투력은 비내림차순으로 정렬되어 있다.

이 조건을 보면 뭔가 이분 탐색이 가능할 것 처럼 보인다. $i$번째 격투기 선수가 챔피언이 될 수 있다면, 그보다 전투력이 더 높은 $i + 1$

$S = \{a_1, a_2, …, a_N\}$

3. 구현

public class Main {
	static int N; static int[] S;
	
	// i번째 있는 사람이 챔피언이 될 수 있는지 반환
	// 단 i번째는 같은 전투력을 가진 사람들 중에서 가장 왼쪽에 있음
	static boolean f(int i) {
		int here = i; int size = S[i];
		while (here - 1 >= 0 && size > S[here - 1]) { size++; here--; }
		if (here != 0) return false;
		here = i;
		while (here + 1 < N && size > S[here + 1]) { size++; here++; }
		if (here != N - 1) return false;
		return true;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		S = new int[N];
		ArrayList<Integer> P = new ArrayList<>();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			S[i] = Integer.parseInt(st.nextToken());
			if (i == 0 || S[i] > S[i - 1]) P.add(i);
		}
        	// lo번째 선수는 챔피언이 될 수 없고
            	// hi번째 선수는 챔피언이 될 수 있다고 가정
		int lo = 0; int hi = P.size() - 1;
		if (f(P.get(lo))) {
			for (int x : P) bw.append(x + 1).append(" ");
			System.out.println(bw.toString().trim());
		} else if (!f(P.get(hi))) {
			System.out.println(-1);
		} else {
			while (lo + 1 < hi) {
				int mid = (lo + hi) / 2;
				if (f(P.get(mid))) hi = mid;
				else lo = mid;
			}
			for (int x : P) if (x >= P.get(hi))
				bw.append(x + 1).append(" ");
			System.out.println(bw.toString().trim());
		}
	}
	
}

1) 시간 복잡도

이분 탐색을 통해 $O(lgN)$의 비교를 하고, 비교 한번에 $O(N)$이므로 $O(NlgN)$

2) 테스트 케이스

10
1 2 3 4 5 6 7 8 9 10
->3 4 5 6 7 8 9 10
1
1
->1