[백준, 17298] 오큰수

문제

 

크기가 N인 수열 A = A1, A2, ..., AN이 있다.

Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수 (그러한 수가 없는 경우에 오큰수는 -1)

 

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. 이 때, 차례대로 오큰수를 출력

 

---

 

오른쪽에 있으면서 가장 왼쪽에 있는 수는 자기보다 큰 수가 나오면 바로 찾아지는데 단순하게 계산하면 for문 2개를 돌리게 된다.

더 나은 방법을 생각해봤는데 떠오르지 않아 찾아보니 스택에 값이 아닌 인덱스를 활용해서 푸는 방법이 있었다.

 

stack에는 인덱스를 push 하는데 배열의 다음 값과 stack에서 peek을 한 인덱스에 해당하는 값을 비교해서 다음 값이 작을 경우에 해당 값의 인덱스를 stack에 push 한다. 그러다가 stack의 인덱스에 해당하는 값보다 큰 값을 만나면 오큰수로 체크하는 식으로 계산하면 된다. 처음에 오큰수를 기록하는 answer 배열을 -1로 초기화하기 때문에 오큰수가 없는 경우는 따로 체크할 필요가 없다.

 

int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());

Stack<Integer> stack = new Stack<>();
int[] arr = new int[N];
int[] answer = new int[N];

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

Arrays.fill(answer, -1);

stack.push(0);
for (int i = 1; i < arr.length; i++) {
    while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
        answer[stack.pop()] = arr[i];
    }
    stack.push(i);
}

for (int num : answer) {
    sb.append(num).append(" ");
}

System.out.println(sb);