태야

배열이나 리스트에서 각 원소에 대해 오른쪽에 있는 원소들 중 자신보다 크거나 같은(또는 보통은 '큰' 경우가 많지만, 변형으로 '크거나 같은' 조건을 쓰기도 한다) 첫 번째 원소를 찾는 문제다.

예시 문제 설명

예를 들어, 배열 A가 주어졌을 때A = [3, 5, 2, 7, 5]각 원소에 대해 오른쪽으로 이동하며, 처음 만나는 자신보다 크거나 같은 원소를 찾습니다.

- 3의 오른쪽에는 5, 2, 7, 5가 있는데, 처음으로 3보다 크거나 같은 수는 5입니다.
- 5의 오른쪽에는 2, 7, 5가 있는데, 2는 작으므로 건너뛰고, 다음 7은 5보다 크므로 7이 됩니다.
- 2의 오른쪽에는 7, 5가 있으므로 7이 첫 번째 큰(또는 같은) 수입니다.
- 7의 오른쪽에는 5만 있으나 5는 7보다 작으므로, 7은 오른쪽에 조건을 만족하는 원소가 없는 것으로 처리합니다.
- 마지막 원소인 5는 오른쪽에 아무 원소도 없으므로 조건을 만족하는 원소가 없습니다.

보통 조건을 만족하는 원소가 없을 경우 -1 또는 0 등 특정 값을 반환합니다.

단순하게 이중 반복문을 사용하면, 각 원소마다 오른쪽의 모든 원소를 확인해야 하므로 시간복잡도가 O(n^2)가 된다. 하지만 스택(stack)을 이용하면, 한 번의 순회로 각 원소를 효율적으로 처리할 수 있다.

스택을 사용하는 이유

• 스택의 특징
  
  • 스택은 후입선출(LIFO) 구조다. 이 특성을 이용하면, 배열을 한 번 순회하면서 "아직 답을 찾지 못한 원소들의 인덱스"를 스택에 저장해 두고, 새로운 원소가 들어올 때마다 이전 원소들과 비교하여 조건(큰 혹은 큰/같은)을 만족하는지 빠르게 확인할 수 있다.
• 시간복잡도
  • 각 원소는 스택에 한 번 push되고, 조건이 맞으면 pop되므로 각 원소가 스택에 들어가고 나오는 과정이 한 번씩 이루어집니다. 따라서 전체 시간 복잡도는 O(n)이 됩니다.

알고리즘 동작 과정

1. 초기화:
   빈 스택을 준비하고, 결과를 저장할 배열을 초기화한다. 결과 배열은 각 원소의 "다음 큰(또는 같은) 수"의 인덱스나 값을 저장할 수 있다.
2. 배열 순회:
   배열의 인덱스를 0부터 n-1까지 순회한다.
   • 현재 원소와 비교:
     현재 원소(A[i])가 들어왔을 때, 스택의 최상단에 있는 인덱스(예: j)를 확인한다.
     • 만약 A[i]가 A[j]보다 크거나(또는 크거나 같은) 하면, A[i]는 A[j]의 조건(다음 큰 또는 같은 수)을 만족하는 원소가 된다.
       따라서 결과 배열의 j번째 위치에 A[i] 또는 인덱스 i를 저장하고, 스택에서 j를 pop한다.
     • 이 과정을 스택이 비거나, 스택의 최상단 원소가 현재 원소보다 크거나 같은 조건을 만족할 때까지 반복한다.
   • 현재 인덱스 push:
     그 후, 현재 인덱스 i를 스택에 push한다.
3. 후처리:
   배열 순회가 끝난 후에도 스택에 남아있는 인덱스들은 오른쪽에 조건을 만족하는 원소가 없는 경우다. 이 경우, 결과 배열에 -1 또는 0을 기록한다.

Python 코드 예시

def next_greater_or_equal(arr):
    n = len(arr)
    result = [-1] * n  # 조건을 만족하는 원소가 없으면 -1로 처리
    stack = []  # 인덱스를 저장하는 스택

    for i in range(n):
        # 현재 원소 arr[i]가 스택의 최상단 원소보다 크거나 같으면 조건을 만족
        while stack and arr[stack[-1]] <= arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)
    
    return result

# 예시 실행
A = [3, 5, 2, 7, 5]
print(next_greater_or_equal(A))  # 출력 예: [5, 7, 7, -1, -1]

위 글을 요약하자면 다음과 같다.

• 문제: 각 원소에 대해 오른쪽에서 처음으로 자신보다 크거나 같은 원소를 찾는 문제.
• 단순 방법: 이중 반복문을 사용하면 O(n^2) 시간복잡도.
• 스택 사용: 스택을 이용하면 각 원소가 한 번씩만 처리되므로 O(n) 시간복잡도로 해결 가능.
• 핵심: 스택에 아직 답을 찾지 못한 원소의 인덱스를 저장하고, 새 원소가 들어올 때마다 조건에 맞는 이전 원소들을 처리.

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

1. 단순 탐색 풀이 - O(n^2)

시간복잡도 O(n^2)를 가지는 모든 요소를 탐색하는 방식으로 풀이했다. 당연히, 시간초과로 실패했다.

N = int(input().strip())
heights = list(map(int, input().strip().split()))

def get_answer():
    answer = [0 for _ in range(N)]
    for i in range(len(heights), 0, -1):
        if i == 1:
            break
        current_top = heights[i - 1]
        for j in range(i - 1, 0, -1):
            left_top = heights[j - 1]
            if left_top >= current_top:
                answer[i - 1] = j
                break
    print(" ".join(map(str, answer)))

get_answer()

2. 스택 이용한 풀이 - 최악 O(n^2), 최선 O(n)

스택을 사용하면 각 요소를 한 번만 처리(삽입/삭제)하게 되어, 이미 검사한 요소들을 재검사하지 않아도 된다.

일반적으로 스택 기반 알고리즘에서는 리스트를 한 번 순회하며, 현재 요소보다 작은(또는 큰) 후보들은 스택에서 제거하는 식으로 진행하여, 각 요소가 스택에 한 번 push되고 최대 한 번 pop되도록 한다.

최악의 경우:
예를 들어, 만약 리스트가 내림차순 정렬되어 있다면, 각 요소마다 내부 for 루프가 거의 전체 남은 요소를 검사하게 된다.
따라서 전체 연산 횟수는 약 n+(n−1)+(n−2)+…+1=O(n^2)가 된다.

N = int(input().strip())
heights = list(map(int, input().strip().split()))

def get_answer():
    answer = [0 for _ in range(N)]

    while heights:
        height = heights.pop()

        for i in range(len(heights) - 1, -1, -1):
            if height < heights[i]:
                answer[len(heights)] = i + 1
                break

    print(" ".join(map(str, answer)))

get_answer()

3. 스택 이용한 풀이 - 최적화 O(n)

N = int(input().strip())
heights = list(map(int, input().strip().split()))

def get_answer():
    answer = [0 for _ in range(N)]
    stack = [] # 인덱스 저장

    for i in range(len(heights)):
        height = heights[i]
        # 스택에 있는 인덱스의 높이가 현재보다 작으면, 이들은 현재 탑의 신호를 받을 수 없음
        while stack and heights[stack[-1]] < height:
            stack.pop()

        # 스택이 남아 있으면, 스택의 최상단 인덱스가 현재 탑의 신호를 수신하는 탑이다
        if stack:
            answer[i] = stack[-1] + 1
        else:
            answer[i] = 0

        stack.append(i) # 현재 탑 인덱스 추가

    print(" ".join(map(str, answer)))

get_answer()

<내 코드>

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        for(int i=0; i<prices.length; i++){
            for(int j=i+1; j< prices.length; j++){
                if (prices[i] > prices[j]) {
                    answer[i] = j-i;
                    break;
                }
                if(j == prices.length-1){ // 마지막 요소 확인
                    answer[i] = j-i;
                }
            }
        } 
        return answer;
    }
}

def solution(prices):
    answer = []
    
    n = len(prices)
    for i in range(n): #0~4
        cnt = 0
        if i == n-1:
            answer.append(cnt)
            break
        for j in range(i+1,n): #1~4
            if prices[i] <= prices[j]:
                cnt += 1
            else:
                cnt += 1
                break
        answer.append(cnt)
    
    return answer