탑

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<Integer> towers = Arrays.stream(br.readLine().split(" "))
                .map(i -> Integer.parseInt(i))
                .collect(Collectors.toList());

        int[] answer = new int[N];
        Stack<Integer> temp = new Stack<>();
        for (int i = N - 1; i > -1; i--) {
            while (!temp.isEmpty() && towers.get(temp.peek()) <= towers.get(i)) {
                answer[temp.pop()] = i + 1;
            }
            temp.add(i);
        }
        for (int item : answer) {
            System.out.print(item + " ");
        }
    }
}

Python 코드

def solution(numbers):
    sz = len(numbers)
    answer = [-1 for i in range(sz)]
    temp = []
    
    for i in range(sz):
        while temp and numbers[temp[-1]] < numbers[i]:
            answer[temp.pop()] = numbers[i]
        temp.append(i)
    
    return answer

G5

문제의 핵심은 한번 쭉 순회하면서 앞선 수를 계속해서 비교해야 한다는 것인데, N의 크기가 10^9 이기 때문에 이중 for문은 무조건 터진다는 것이다.

따라서 O(N)으로 만들어야 한다.

문제를 보자마자 프로그래머스 뒤에 있는 큰 수 찾기 문제가 떠올랐다.
이 문제는 N의 크기가 10^6 이었음에도 이중 for문을 돌리고 시간 초과가 났었다.

그래서 아직 처리될 수들을 담는 stack 을 두고, 내부에서 while문을 돌아 현재 순회하고 있는 값과 비교하는 로직을 구현했다.

이렇게 되면 큰 틀에서는 한바퀴를 돌리는 O(N)이고 while문을 돌면서 stack에 가장 위에 있는 값을 비교하는 것이므로 무난하게 통과할 수 있다.

출처: https://www.acmicpc.net/problem/2493