프로그래머스_뒤에 있는 큰 수_Day6

 

알고리즘 챌린지 6일 차이다. 연휴 기간인 만큼 조금 쉬운 문제를 푸는 점은 양해 바란다... ㅎ 오늘은 자바로만 문제를 풀이해보고자 한다.

https://school.programmers.co.kr/learn/courses/30/lessons/154539?language=java

프로그래머스

간단하게 이중 반복문을 사용하여 완전탐색을 하면 쉽게 풀리겠지만, 배열의 크기가 최악의 경우 1,000,000이기 때문에 시간초과가 무조건 날 거다. 효율적이지도 않고. 이런 경우 특정한 알고리즘을 떠올리기 전에(명확하게 눈에 보이는 게 아니라면,,) 자료구조를 먼저 생각해 보자. 

앞에서부터 천천히 뒤에 있는 원소들을 비교하면서 조건에 만족하는 뒤 큰 수를 찾아내기 위해선 필자는 처음에 큐를 생각했지만, 방금 자료구조의 넣은 수보다 큰 가장 작은 인덱스를 구하기 위해서는 LIFO구조가 더 알맞다고 생각하여 스택을 사용해서 풀이해 보았다. 

기본 로직은 아래와 같다. 

1.  배열의 0번 인덱스 값을 스택에 넣는다.(원소를 넣어도 될 것 같지만 그렇지 않은 이유를 마지막에 설명하겠다.)
2. 1번 부터 배열의 길이만큼 반복을 돌면서 배열의 값이 스택의 있는 값보다 큰지 확인한다. 
   1. 값이 크다면, 조건을 만족하는 뒤 큰수 이다. 
   2. 조건을 만족한 인덱스는 스택에서 꺼내서 정답 배열에 넣고, 그 밑에 있는 스택도 조건을 만족하는지 확인한다. 
3. 스택을 벗어나지 못한 인덱스는 뒤 큰수가 없으므로 -1을 넣어준다.
   1. 배열의 값이 아니라 인덱스를 넣은 이유가 바로 이 점이다. 
   2. 배열의 값을 넣어버리면 해당 값이 어떤 위치에 있던 값인지 알 수가 없다. 

 

그림으로 살펴보자. 

 

그림이 조잡해서 이해하기 어려울 수도 있을 것 같다.. 차라리 코드로 보는 것이 더 편할 수도 있을 것이다. 

Java

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        //배열의 인덱스를 담을 스택 생성
        Stack<Integer> stack = new Stack<>();
        
        int[] answer = new int[numbers.length]; 
        stack.push(0);
        
        for (int i=1; i<numbers.length; i++) {
        	//스택이 비어있지 않고 뒤큰수 인경우 하위 요소까지 모두 점검
            while(!stack.isEmpty() && numbers[stack.peek()] < numbers[i]){
                answer[stack.pop()] = numbers[i];
            }
            stack.push(i);
        }
        
        //탈출하지 못한 인덱스는 뒤큰수가 없는 거임
        while (!stack.isEmpty()) {
            answer[stack.pop()] = -1;
        }
        return answer;
    }
}