99클럽 코테 스터디 1일차 TIL [배열, 스택]

오늘의 학습 키워드 : [스택]
풀이 코드는 아래와 같다.

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 < numbers.length; i++) {
            // 인덱스를 스택에서 꺼내 값을 비교
            while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                // 현재 숫자를 해당 인덱스의 뒷 큰수로 설정
                answer[stack.pop()] = numbers[i];
            }
            
            // 스택에 인덱스 값을 저장
            stack.push(i);
        }

        return answer;
    }
}

[ 오늘의 회고 ]

되게 간단하게 풀이하려고 이중 for문으로 처음 코드를 짰는데, 몇 개의 테스트 케이스에서 시간 초과가 발생했다. 

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];

        for(int i=0; i<numbers.length; i++) {
            int cur = numbers[i];
            int temp = -1;
            for(int j=i+1; j<numbers.length; j++) {
                if(cur < numbers[j]) {
                    temp = numbers[j];
                    break;
                }
            }
            answer[i] = temp;
        }
        return answer;
    }
}

제한 사항에 시간 제한이 딱히 없어서, 간단하게 생각하고 짠 코드였다.

이에 다른 O(n^2)이 넘지 않는 선에서 어떻게 짜야할 지 다시 생각했다.

 

탐색을 하자니 정렬이 되어 있지 않아서 아닐 것 같았고, 같은 인덱스마다 비교를 해주어야 한다고 생각해서, Stack을 떠올리게 되었다.

1. 처음에, answer 배열을 -1 (뒷 큰 수가 없는 경우)으로 모두 초기화 한다.

2. stack이 비어있지 않은 경우와, 빈 경우를 생각한다.

3. 스택이 비어있는 경우, 해당 인덱스 값을 넣어준다.

4. 비어있지 않은 경우, while문으로 반복하며 값을 비교하여 뒷 큰수를 설정해준다.

 

아래 그림을 보면 쉽게 이해할 수 있다.

 

새롭게 알게 된 것

스택 자료구조를 좀 더 잘 활용할 수 있게 된 것 같다.

내일 학습할 것

DP 문제를 풀다가 냅색 알고리즘이 나왔는데, 개념이 정확하게 잡혀있는 것 같지 않아서 해당 알고리즘에 대해서 공부해 보려 한다.