이제 스택을 간단한 문제 풀어보면서 익히겠다.
https://school.programmers.co.kr/learn/courses/30/lessons/12906
프로그래머스의 [같은 숫자는 싫어] 문제를 풀었다.
스택
일단 제미나이 말로는 다음과 같다.
| 1. 스택이란 무엇인가? (가장 쉬운 비유) 핵심 컨셉: "마지막에 넣은 것이 가장 먼저 나온다. (LIFO: Last-In, First-Out)" 스택은 이름 그대로 '쌓아 올린 더미'를 생각하면 가장 이해하기 쉽습니다. 우리가 책상 위에 책을 한 권씩 쌓는다고 상상해 보세요. 자바의 정석을 맨 아래에 놓습니다. 그 위에 클린 코드를 쌓습니다. 마지막으로 객체지향의 사실과 오해를 맨 위에 쌓습니다. 이제 책을 다시 꺼내려면 어떻게 해야 할까요? 당연히 가장 마지막에 쌓은 '객체지향의 사실과 오해'부터 꺼내야 합니다. 이것이 바로 스택의 핵심 원리인 후입선출(LIFO)입니다. 데이터를 넣는 행위: Push (책을 맨 위에 쌓는다) 데이터를 꺼내는 행위: Pop (맨 위의 책을 꺼낸다) 맨 위 데이터를 확인만 하는 행위: Peek (맨 위 책의 제목만 살짝 본다) 2. 이 문제에서 왜 스택을 사용해야 할까? 같은 숫자는 싫어 문제의 핵심 요구사항은 "배열을 순서대로 보면서, 바로 이전에 처리한 숫자와 지금 숫자가 다른 경우에만 저장한다"는 것입니다. 여기서 '바로 이전에 처리한 유효한 숫자'라는 개념이 등장합니다. 스택은 이 역할을 완벽하게 수행합니다. [1, 1, 3, 3, 0, 1, 1] 배열을 처리하는 과정을 스택의 시점으로 따라가 보겠습니다. 1이 들어옵니다. 스택이 비어있으니, push(1). (스택: [1]) 두 번째 1이 들어옵니다. 스택의 맨 위(peek())를 보니 1이 있습니다. "어, 방금 넣은 거랑 똑같네?" -> 아무것도 안 합니다. (스택: [1]) 3이 들어옵니다. 스택의 맨 위(peek())를 보니 1이 있습니다. "방금 넣은 거랑 다르네?" -> push(3). (스택: [1, 3]) 두 번째 3이 들어옵니다. 스택의 맨 위(peek())를 보니 3이 있습니다. "똑같네?" -> 아무것도 안 합니다. (스택: [1, 3]) 0이 들어옵니다. 스택의 맨 위(peek())를 보니 3이 있습니다. "다르네?" -> push(0). (스택: [1, 3, 0]) ... 이런 식으로 끝까지 진행하면 됩니다. 이처럼 스택을 사용하면 **가장 최근에 저장된 값(Top/Peek)**과의 비교가 매우 쉬워지기 때문에, 이 문제에 아주 적합한 자료구조라고 할 수 있습니다. |
즉 최근 저장된 값을 빠르게 불러오고, 비교하기 위해 사용되는 것 같다.
같은 숫자는 싫어
import java.util.*;
import java.util.stream.*;
import java.math.*;
public class Solution {
public int[] solution(int []arr) {
int[] answer = {};
Deque<Integer> st = new ArrayDeque<>();
// System.out.println(st.peek()); // null 반환
for (int i = 0 ; i < arr.length ; i++) {
if (st.isEmpty() || st.peek() != arr[i]) { // 비었는지 확인 후 위에 거 확인
st.push(arr[i]);
}
}
answer = new int[st.size()];
for (int i = st.size() - 1 ; !st.isEmpty() ; i--) // 역순으로 해야함.
answer[i] = st.pop();
return answer;
}
}풀이는 위와 같다.
Stack을 예전에는 좀 썼는데 Deque라는 것을 최근에 사용한다는게 놀랐다.
댓글