[코딩 테스트] 오큰수

문제 출처

 

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

 

 

문제 풀이 생각과 과정

• 먼저 어떤자료구조를 사용할 지에 대해서 고민을 많이 했다.
• 이 문제는 결국에는 스택을 사용하는 문제를 알아차리는게 중요해 보인다.

 

그 다음 슈도코드는 다음과 같다.

 

• 배열의 오른쪽에서 왼쪽으로 역순으로 확인한다(오른쪽에 큰 수 가 있었는지 확인해야 하므로)
• 스택의 최상단에 있는 수가 내가 지금 확인하는 수보다 크면, 그 숫자를 배열에 저장한다.
  • 스택에 지금 내가 확인한 수를 push한다.
• 스택의 최상단에 있는 수가 내가 지금 확인하는 수보다 작거나 같으면, 스택에 있는 수를 빌때까지 pop한다.
  • 스택이 비게 되면 -1를 저장하게 됨(오큰수가 없는 경우임)

---

그림으로 설명해보도록 하겠다.

• 먼저 다음은 초기 상태이다. 스택은 비어져있고 배열의 마지막부터 접근을 하게 된다.

 

• 그 다음 스택이 비어져 있으므로, answer 배열에 -1을 추가한다.

• 다음 2를 확인하러가고, 스택에는 7이 있다.
• 스택의 최상단(7) 이랑, 현재 비교하는 수(2) 중에서 스택에 있는 수가 더 크므로 answer배열에 저장

 

 

• 그리고 스택에 추가해준다.
• 다음 5랑 스택의 최상단(2)이랑 확인하는데 스택에 있는 수가 더 작다

• 스택에서 2를 pop해준다음
• 7이랑 비교를 한다.
• 7이 5보다 더 크니까 7을 answer에 저장

• 그 다음 5랑 3이랑 비교를 하면 5가 더 크니까, 5를 저장하면 끝나게 된다.

 

 

정답으로

 

5 7 7 -1 을 출력해주면 된다.

 

스택을 알아차린다면 코드는 길지 않은 문제였던 것 같다.

 

코드

 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] numbers = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] answer = new int[n];
        ArrayDeque<Integer> stack =new ArrayDeque<>();
        A:for(int i = n-1  ; i>=0; i--){
            while(!stack.isEmpty()){
                if(stack.peek()>numbers[i]){
                    answer[i]=stack.peek();
                    stack.push(numbers[i]);
                    continue A;
                }else{
                    stack.pop();
                }
            }
            stack.push(numbers[i]);
            answer[i] =-1;
        }

        StringBuilder sb =new StringBuilder();
        for(int i = 0 ; i<n;i++){
            sb.append(answer[i]);
            sb.append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}