문제 내용

문제 분석

1. 입력된 수열의 현재 인덱스 기준, 오른쪽에 있는 수를 확인한다.
2. 오른쪽에 있는 수를 확인하다가, 현재 인덱스의 수보다 큰 수일 경우, 해당 수가 현재 인덱스의 오큰수이다.
3. 오른쪽에 있는 수 중에, 현재 인덱스의 수보다 큰 수가 없으면, 현재 인덱스의 오큰수는 -1이다.
4. 입력된 수열의 오큰수를 공백으로 구분해 출력한다.
5. 문제에서는 인덱스를 1부터 시작했지만, 설명과 코드에서는 0부터 시작한다.

의사결정

이중 for문

• 현재 인덱스 기준, 오른쪽에 있는 수를 확인하면서 큰 수가 있는지 없는지 확인하는 것이 제일 먼저 떠오르나, 시간복잡도 O(n^2)으로 시간 초과가 날 것으로 판단된다.

- stack 방식

• 입력받은 수열을 저장하는 배열 : input
• 오큰수를 저장하는 배열 : answer
• input 배열의 인덱스 0부터 n-1(input의 길이)까지 반복문에 넣고 비교
  • stack에 가장 마지막으로 들어간 값과, input 배열의 수를 비교하여, 오른쪽의 수가 큰지 아닌지 확인한다.
    - 오른쪽의 수가 더 크면, stack을 확인하여 작은 수들의 오큰수를 대입한다.
    • 오른쪽의 수가 작으면, stack에 push
    • stack이 비어있으면, stack에 넣는다.

코드구현

1. 입력 받기 & 초기화

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] input = new int[n];
int[] answer = new int[n];

String arr = br.readLine();
StringTokenizer st = new StringTokenizer(arr);
for (int i = 0; i < n; i++) {
    input[i] = Integer.parseInt(st.nextToken());
    answer[i] = -1;
}

• 수열을 입력받기 위한 배열 input생성, 오큰수를 저장하기 위한 배열 answer생성
• input에는 수열을 저장
• answer에는 -1로 초기화

2. 반복문으로 순회하며 값 비교하기

Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && input[stack.peek()] < input[i]) {
           answer[stack.pop()] = input[i];
    }
    stack.push(i);
}

• input을 순회하며 현 index와 stack의 peek값 비교

2-1. stack이 비어있으면,

• stack에 해당 index를 push

2-2. stack이 비어있지 않고, stack의 peek값보다 index값이 크다면,

• stack의 peek값을 index로 가지는 input의 값보다 현재 비교중인 i를 index로 가지는 input의 값이 더 크기 때문에,
• stack의 peek값의 오큰수(answer[stack.peek()])는 input[i]가 된다.
• 이후 stack에서 pop해야 하므로, answer[stack.pop()]을 사용하여 대입하는 것이 코드가 간결해진다.
• while문을 사용하여, stack의 peek값이 input[i]보다 작을 때까지, stack의 peek값을 input[i]로 대입한다.

2-3. stack이 비어있지 않고, stack의 peek값보다 index값이 작다면,

• stack의 peek값을 index로 가지는 input의 값보다 큰 값을 찾아야 하므로, stack에 현재 index를 push

즉, 2-2를 반복하며 stack의 peek값을 확인하며 pop하다가도, peek값이 index값보다 크다면, 반복 중지하고 stack에 현재 index값 push

3. 오큰수 값 출력

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

• 일반적인 System.out.println의 경우 시간초과 발생
• 문자열 사용하기 용이한 클래스 StringBuilder 사용 추천

코드

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

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[] input = new int[n];
        int[] answer = new int[n];

        String arr = br.readLine();
        StringTokenizer st = new StringTokenizer(arr);
        for (int i = 0; i < n; i++) {
            input[i] = Integer.parseInt(st.nextToken());
            answer[i] = -1;
        }

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && input[stack.peek()] < input[i]) {
                answer[stack.pop()] = input[i];
            }
            stack.push(i);
        }

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