프로그래머스 뒤에 있는 큰 수 찾기 python

프로그래머스 뒤에 있는 큰 수 찾기 python

문제

• 문제
  정수로 이루어진 배열 numbers가 주어집니다.
  각 원소에 대해 자신보다 뒤에 있는 수들 중에서, 자신보다 크면서 가장 가까운 수를 찾아야 합니다.
  만약 그런 수가 없으면 -1을 넣어야 합니다.
• 테스트케이스
  
  • 입력: [2, 3, 3, 5]
    출력: [3, 5, 5, -1]
  • 입력: [9, 1, 5, 3, 6, 2]
    출력: [-1, 5, 6, 6, -1, -1]
• 문제 작동원리
  이 문제는 배열 내의 각 수에 대해, 뒤에 있는 수들 중에서 자신보다 크고 가장 가까운 값을 찾아야 합니다.
  이 과정을 모든 원소에 대해 수행하면 정답 배열을 만들 수 있습니다.
  하지만 이중 반복문으로 순차적으로 비교하면 시간 복잡도는 \(O(N^2)\)이며,
  입력 크기가 최대 1,000,000이기 때문에 시간 초과가 발생합니다.
  이를 해결하기 위해 스택 자료구조를 사용한 효율적인 탐색 방식을 적용해야 합니다.

---

아이디어

• 풀이방법
  
  1. 배열의 오른쪽에서 왼쪽으로, 즉 뒤에서 앞으로 탐색합니다.
  2. 스택에는 아직 처리하지 않은 수들을 넣습니다. 이 수들은 현재 원소보다 뒤에 있는 수들입니다.
  3. 현재 값보다 작거나 같은 값은 스택에서 모두 제거합니다.
  4. 제거가 끝난 후, 스택이 비어 있지 않다면, 스택의 top 값이 뒷 큰수입니다.
  5. 현재 수를 스택에 push합니다.
  6. 이 과정을 배열 전체에 대해 반복하고, 정답 배열을 reverse()하여 반환합니다.
• 테스트케이스별 풀이방법

✅ 구현 방식

• 배열 출력 시, 각 숫자 사이에 고정된 너비(공백 3칸)를 둡니다. 예: 9 1 5 3 6 2
• 포인터도 해당 숫자에 맞춰 정확히 정렬되도록 공백을 계산하여 위치를 지정합니다.
• 스택은 이전과 같이 top이 위쪽에 있도록 출력합니다.

---

🔎 [9, 1, 5, 3, 6, 2] 텍스트 도식 – 포인터 위치 정렬 개선

🎯 초기 상태

• 스택: [] (비어 있음)
• 정답: [?, ?, ?, ?, ?, ?]
• 방향: 오른쪽에서 왼쪽

▶️ 인덱스 5, 값 = 2

numbers =  9   1   5   3   6   2
                               ↑
    

• 현재 값: 2
• 스택 비어 있음 → 뒷 큰수 없음 → -1
• 2를 스택에 push

stack (top ↓)
  2
    

• 정답: [?, ?, ?, ?, ?, -1]

▶️ 인덱스 4, 값 = 6

numbers =  9   1   5   3   6   2
                           ↑
    

• 현재 값: 6
• 스택 top = 2 → 제거 (2 ≤ 6)
• 스택 비어 있음 → 뒷 큰수 없음 → -1
• 6을 스택에 push

stack (top ↓)
  6
    

• 정답: [?, ?, ?, ?, -1, -1]

▶️ 인덱스 3, 값 = 3

numbers =  9   1   5   3   6   2
                       ↑
    

• 현재 값: 3
• 스택 top = 6 → 6 > 3 → 뒷 큰수는 6
• 3을 스택에 push

stack (top ↓)
  3
  6
    

• 정답: [?, ?, ?, 6, -1, -1]

▶️ 인덱스 2, 값 = 5

numbers =  9   1   5   3   6   2
                   ↑
    

• 현재 값: 5
• 스택 top = 3 → 제거 (3 ≤ 5)
• 다음 top = 6 → 6 > 5 → 뒷 큰수는 6
• 5를 스택에 push

stack (top ↓)
  5
  6
    

• 정답: [?, ?, 6, 6, -1, -1]

▶️ 인덱스 1, 값 = 1

numbers =  9   1   5   3   6   2
               ↑
    

• 현재 값: 1
• 스택 top = 5 → 5 > 1 → 뒷 큰수는 5
• 1을 스택에 push

stack (top ↓)
  1
  5
  6
    

• 정답: [?, 5, 6, 6, -1, -1]

▶️ 인덱스 0, 값 = 9

numbers =  9   1   5   3   6   2
           ↑
    

• 현재 값: 9
• 스택 top = 1 → 제거
• 다음 top = 5 → 제거
• 다음 top = 6 → 제거
• 스택 비어 있음 → 뒷 큰수 없음 → -1
• 9를 스택에 push

stack (top ↓)
  9
    

• 정답: [-1, 5, 6, 6, -1, -1]

---

✅ 최종 결과 출력

입력  : [9, 1, 5, 3, 6, 2]
출력  : [-1, 5, 6, 6, -1, -1]
    

---

📌 요약

• 포인터(↑)는 숫자 위치 기준으로 완전 수직 정렬
• 숫자 간 공백은 고정 길이로 정렬 (3칸씩)
• 스택은 항상 top이 위쪽
• 현재 인덱스의 값이 스택의 top보다 작으면 → top이 뒷 큰수
• 현재 값보다 작거나 같은 top은 모두 제거
• 이 방식으로 시간복잡도는 \(O(N)\)으로 최적입니다.

---

전체코드

아래 코드는 사용자가 직접 작성한 코드이며, 요청에 따라 수정이나 주석 없이 그대로 유지합니다.

def solution(numbers):
    answer = []
    stack=[]
    N=len(numbers)
    for i in range(N-1,-1,-1):
        if not stack:
            answer.append(-1)
            stack.append(numbers[i])
        else:
            while stack and stack[-1]<=numbers[i]:
                stack.pop()
            if stack and stack[-1]>numbers[i]:
                answer.append(stack[-1])
                stack.append(numbers[i])
            else:
                answer.append(-1)
                stack.append(numbers[i])
    answer.reverse()
    return answer
    

---

결론

• 이 문제는 배열의 각 원소마다 뒤에 있는 값들을 전부 탐색하면 시간 복잡도가 \(O(N^2)\)로 증가하므로, 입력 크기가 클 경우 반드시 시간 초과가 발생합니다.
• 이를 해결하기 위해 스택을 이용한 역방향 탐색 방식을 적용합니다.
• 뒤에서부터 앞으로 이동하면서, 스택을 통해 현재 값보다 큰 값을 빠르게 추적할 수 있습니다.
• 스택에 현재 값보다 작거나 같은 수를 제거하고, 남은 값 중 첫 번째(즉 top 값)가 뒷 큰수가 되며, 스택이 비어 있다면 뒷 큰수가 존재하지 않는다는 의미이므로 -1을 넣습니다.
• 이 방식은 각 원소가 스택에 한 번 push, 한 번 pop만 되므로 총 시간 복잡도는 \(O(N)\)으로 매우 효율적입니다.
• 결과적으로 이 문제는 스택의 기본 원리를 이용하여 시간 최적화를 달성하는 대표적인 알고리즘 문제입니다.
• 실전 문제에서 자주 등장하며, 다양한 응용 문제로도 확장될 수 있는 중요한 유형입니다.