[PRG] 154539.뒤에 있는 큰 수 찾기 - Java

📝 문제

문제 | 프로그래머스 154539.뒤에 있는 큰 수 찾기

💡 풀이 과정

⛓ 사용한 자료구조 : 스택(Stack)

numbers 배열의 길이가 1,000,000 이기 때문에 완전탐색을 했을 때 최악의 경우 시간 복잡도가 $O(n^2)$ 이기 때문에 다른 방식을 이용해서 풀어야 한다.

방법1: 투포인터 이용 - 실패

처음에는 투 포인터를 사용해서 풀이하는 문제인 줄 알았다. 왼쪽 포인터의 숫자가 작으면 왼쪽 포인터를 이동시키고, 왼쪽 포인터의 숫자보다 오른쪽 포인터의 숫자가 작으면 오른쪽 포인터를 이동시키는 방식으로 풀어야 하나 고민했는데, 불가능한 경우의 수가 많았다. 예를 들어 배열에서 가장 큰 수가 제일 앞에 있는 경우나 내림차순으로 정렬된 배열의 경우에는 앞서 고안한 풀이가 성립되지 않는 것이다!

방법2: 스택

그 다음으로 생각난 방법은 스택을 이용한 방법이다. 예전에 비슷한 문제를 풀었던 것 같은데, 그 문제는 잘 기억이 나지 않지만 스택을 이용했던 것만 기억이 나서 이 문제에도 사용해보자!하는 생각이 들었다.

우선 numbers 배열의 숫자와 인덱스를 함께 스택에 저장한다. 이 때 현재 숫자( tmp )가 스택의 peek() 보다 크다면 스택의 원소를 꺼낸다. 이러한 원소를 꺼내는 과정은 현재 스택의 peek() 보다 현재 숫자가 작거나 같아질 때까지 반복한다. 아래는 이 부분에 해당하는 코드이다.

int tmp = numbers[i];
            
if(!st.isEmpty() && st.peek().num<tmp) {
		while(st.peek().num<tmp) {
				Item cur = st.pop();
				answer[cur.idx] = tmp;
                    
				if(st.isEmpty()) break;
		}
}

두 번째 입출력 예시를 이 풀이에 적용해보면 다음 그림과 같이 진행이 된다.

for문으로 numbers 배열을 모두 순회한 후에 스택에 남아있는 원소들은 본인 뒤에 본인보다 큰 요소를 찾지 못한 원소들이다. 따라서 for문이 종료된 후에 스택에 원소가 남아있다면 모두 빼서 해당 인덱스에는 -1 을 넣어줘야 한다. 즉, 위의 예시에서 정답 배열의 0 , 2 , 5 번 인덱스는 모두 -1이 된다.

코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Item> st = new Stack<>();
        
        for(int i=0,size=numbers.length;i<size;i++) {
            
            int tmp = numbers[i];
            
            if(!st.isEmpty() && st.peek().num<tmp) {
                while(st.peek().num<tmp) {
                    Item cur = st.pop();
                    answer[cur.idx] = tmp;
                    
                    if(st.isEmpty()) break;
                }
            }
            
            st.push(new Item(i,tmp));
            
        }
        
        if(!st.isEmpty()) {
            while(!st.isEmpty()) {
                Item cur = st.pop();
                answer[cur.idx] = -1;
            }
        }
        
        
        return answer;
    }
    
    static class Item {
        int idx, num;
        public Item(int idx, int num) {
            this.idx = idx;
            this.num = num;
        }
    }
}