찰떡개발자 코딩

문제 : https://www.acmicpc.net/problem/17298

풀이 : 

처음에 보자마자 아 for문 많이 돌려서 찾으면 금방하겠다 였다...

아직도 문제푸는데에 좋은 방법을 생각해 내지 못하나보다 했다~ ㅜ

문제 밑에 보면 어떤 문제인지 힌트 처럼 볼수 있는것이 있는데, 스택이 적혀있던것..!

어떻게 스택을 사용해서 풀수 있나 엄청 고민했다 ...

결국 나온풀이는.

현재 값을 기준으로 전에있던 값들을 비교하여 뒤에서 앞(키포인트)을 비교하는 방법으로 생각했다.

그래서, 뒤값보다 앞에 값이 작다면 앞에값들을 하나씩 꺼내서 뒤값으로 바꿔준다.

만약 뒤값보다 앞에값이 크다면 뒤값 = 변경되야될 값으로 stack에 넣어준다.

이 방법을 통해 구현한 코드이다.

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

		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		//temp로 변경될만한 값의 index를 담아놓는다.
		Stack<Integer> stack = new Stack<Integer>();

		int[] arr = new int[n];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < arr.length; i++) {
			//뒤를 바라보고 자기 자신과 비교한다.
			//자기자신이 더 크다면 이전값을 변경해준다. => 근데 하나만 바꾸는게 아니라 쌓여있는 이전값들 다 체크한다.
			while(!stack.empty() && arr[i]> arr[stack.peek()]) {
				arr[stack.pop()] = arr[i];
			}
			//자기자신이 작다면 stack에 쌓아 이전값으로 비교할 수 있게 담아준다.
			stack.push(i);
		}

		while(!stack.empty()) {
			arr[stack.pop()] = -1;
		}

		for (int i = 0; i < arr.length; i++) {
			sb.append(arr[i]+" ");
		}
		System.out.println(sb);

	}