99클럽 코테 스터디 1일차 TIL + 배열/스택

💡문제

[level 2] 뒤에 있는 큰 수 찾기 - 154539

문제 링크

성능 요약

메모리: 206 MB, 시간: 259.36 ms

 

---

 

🤔접근법

주어진 정수 배열을 순회하면서 본인보다 오른쪽에 있는 수들 중에서 본인보다 크지만 가장 가까이 있는 수 찾기

범위 체크 및 시간복잡도 예상

• 1 ≤ N ≤ 1,000,000
• O($NlogN$) 보다 더 작아야 한다.
•  

풀이법

❌ 접근 방법. 완탐

1. 주어진 정수 배열을 인덱스 0 ~ N 까지 반복
2. 가르키는 정수로부터 오른쪽에 존재하는 모든 정수를 탐색
3. 만약 본인보다 큰 정수가 나오면 answer에 저장하고 정지

➡️ 해당 풀이법의 시간 복잡도 : $O(N^2)$ → 시간 초과

 

⭕ 접근 방법. stack을 사용하자 !

스택에는 정수배열의 인덱스와 값을 넣는다.

스택은 top 보다 값이 작을때만 쌓을 수 있다.

1. 주어진 정수 배열을 인덱스 0 ~ N 까지 반복
2. 스택의 top의 값이 배열의 값보다 크다면 answer 배열에 top 위치에 가르키는 값을 넣는다. → top보다 오른쪽에 있으면서 top보다 크고 가장 가까이 있는 수 찾음!
3. 스택의 top의 값이 배열의 값보다 작다면 스택에 쌓는다. → 스택에 쌓여있는 값들은 찾고자 하는 값 즉, 본인보다 오른쪽에 있고, 본인보다 크고, 가장 가까이 있는 수를 찾지 못한 수들이다.
4. 배열에 가르키고 있는 값을 스택에 쌓고 다음으로 넘어간다.

➡️ 해당 풀이법의 시간 복잡도 : $O(N)$

 

---

 

🤯FAIL

답을 봐서 문제를 푼 경우

• 스택 자료구조를 사용해야 한다는 아이디어를 떠올리지 못했다.
• 다양한 자료구조를 사용할 수 있도록 노력해보자.

 

👩‍💻 코드

import java.io.IOException;
import java.util.Arrays;
import java.util.Stack;

class Number {
    int idx;
    int num;
    public Number(int idx, int num){
        this.idx = idx;
        this.num = num;
    }
}
class Solution {
    public int[] solution(int[] numbers) {
            int[] answer =  new int[numbers.length];
            Arrays.fill(answer, -1);
            Stack<Number> st = new Stack<>();

            for(int i = 0; i < numbers.length; i++){
                while (true){
                    if(st.size() == 0 || st.peek().num >= numbers[i]){
                        break;
                    }else{
                        answer[st.pop().idx] = numbers[i];
                    }
                }
                st.push(new Number(i,numbers[i]));
            }
        
        return answer;
    }
}