[백준 JAVA] 22866번: 탑 보기

https://www.acmicpc.net/problem/22866

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

public class Main {
	public static int N, cnt, min;
	public static int[] L;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		N = Integer.parseInt(br.readLine());
		L = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			L[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < N; i++) {
			cnt = 0;
			min = 0;
			int lmax = L[i];
			int rmax = L[i];
			int left = i, right = i;
			while (true) {
				if (left == 0 && right == N - 1) {
					break;
				}

				if (left - 1 >= 0) { // 왼쪽세기
					left -= 1;
					if (L[left] > lmax) {
						if (min == 0) {
							min = left + 1;
						}
						lmax = L[left];
						cnt++;
					}

				}
				if (right + 1 < N) { // 오른쪽 세기
					right += 1;
					if (L[right] > rmax) {
						if (min == 0) {
							min = right + 1;
						}
						rmax = L[right];
						cnt++;
					}
				}
			}

			if (cnt == 0) {
				sb.append(0 + "\n");
			} else {
				sb.append(cnt + " " + min + "\n");
			}
		}

		System.out.println(sb);
	}
}

 

완탐일경우 (O^2) = 100억정도 되는것을 확인한 후 시도해보았지만 역시나 시간초과

 

N의 크기가 10만 이므로 최소한 N log N의 방법으로 시도해야 한다.

 

dp, 이분탐색정도가 떠오르는데 이분탐색의 경우에는 빌딩의 크기를 전부 정렬해야 하는데 문제의 의도와 맞지 않을것같아서  dp 풀이법을 떠올려보았다.

 

우선 문제는 조건의 만족하는 해를 빌딩의 번호별로 구해야하는데 아무리 생각해도 문제가 쪼개지지가 않았다 

 

8
3 7 1 6 3 5 1 7

 

빌딩 1번과 2번의 차이가 있을 경우 1번에서 구한 값을 쓸 수 있을까 생각해 보았지만 생각하기 힘들었다.

 

 

 

 

스택을 활용하여 왼쪽부터 빌딩의 수를 계산하면서 오면 된다는 말을 듣고 한번 다시 풀어보았다.