[프로그래머스] 코테연습 - 뒤에 있는 큰 수 찾기(lv.1)

- 내 방법 풀이

• 처음에 문제를 보고, 스택보다 Arrays.sort를 사용하여 풀려고 했으나 크면서 가장 가까이 있는 수를 찾기에 시간복잡도가 커 알맞지 않은 방법이었다.
• 아직 스택을 알고리즘에 적용하는 것이 어려워 개념을 재정리해야겠다는 생각이 들었다.
• 다른 사람의 풀이를 참고하여, 스택을 활용하여 풀었다.
• Stack은 LIFO(Last In First Out), 가장 마지막에 추가된 항목은 맨 바깥쪽에 위치한다. Pop시 가장 먼저 제거됨.
• Stack에 index를 대신할 i를 넣는다. 이후 while문을 통해 스택에 있는 index를 뽑아 해당 인덱스보다 큰 numbers[i]을 찾아 answer[i]에 할당해준다.
• 핵심은 Stack에 i를 넣어 answer의 인덱스로 활용하는 것.
  Stack peek를 통해 꺼내진 Index의 numbers[Index]가 numbers[i]의 비교를 통해 answer[Index]에 할당되는 구조.

import java.util.*;

class Solution { 
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> stack = new Stack<>();
        Arrays.fill(answer, -1);

        for (int i=0; i < answer.length; i++) {
            while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                answer[stack.pop()] = numbers[i];
            }
            stack.push(i);
        }
        return answer;
    }
}

- 다른 사람 방법 풀이

• Stack을 이용하여 풀었다. Stack에 Index를 담고, pop하여 numbers[Index]와 다음 항인 number[i]를 비교하여 더 크다면 answer [Index] 에 할당. 아니면 다시 Stack에 push해준다.

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Arrays.fill(answer, -1);
        Stack<Integer> s = new Stack<>();
        s.push(0);
        for(int i = 1; i < numbers.length; i++){
            while(!s.isEmpty()){
                int idx = s.pop();
                if(numbers[i] > numbers[idx]){ // 뒤가 더 클때
                    answer[idx] = numbers[i];
                } else { // 앞이 더 크거나 같을 때
                    s.push(idx);
                    break;
                } 
            }
            s.push(i);
        }

        return answer;
    }
}