스텍 / 큐 : 같은 숫자는 싫어

문제 이해

배열에서 연속된 같은 숫자를 제거하여 하나만 남기는 문제입니다.

 

예시:

• 입력: [1,1,3,3,0,1,1]
• 출력: [1,3,0,1]

 

접근 방법

왜 스택을 사용하는가?

이 문제의 핵심은 가장 최근에 추가된 원소와 현재 원소를 비교하는 것입니다.

• 스택의 top에 있는 값과 현재 값을 비교 (O(1))
• 연속된 같은 숫자를 효율적으로 제거 가능
• LIFO(Last In First Out) 특성이 문제와 딱 맞음

 

알고리즘 설계

1. 스택을 생성합니다
2. 배열을 순회하며 각 원소에 대해:
   • 스택이 비어있거나 top과 현재 원소가 다르면 → push
   • 같으면 → 무시 (아무것도 하지 않음)
3. 최종 스택을 배열로 변환하여 반환

 

구현 과정

초기 아이디어의 오류

처음에는 "같으면 기존 것을 빼고 새로운 것을 추가"하는 방식을 생각했습니다:

if (stack.isEmpty() || stack.peek() != num) {
    stack.push(num);
} else {
    stack.pop();    // 불필요한 연산
    stack.push(num);
}

하지만 이는 불필요한 연산입니다. 같은 값을 빼고 다시 넣는 것보다 아무것도 하지 않는 것이 더 효율적입니다.

 

최종 해결책

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        Stack<Integer> stack = new Stack<>();
        
        for (int num : arr) {
            // 스택이 비어있거나 top과 현재 숫자가 다르면 추가
            if (stack.isEmpty() || stack.peek() != num) {
                stack.push(num);
            }
            // 같으면 아무것도 안함 (연속된 같은 숫자 무시)
        }
        
        return stack.stream().mapToInt(i -> i).toArray();
    }
}

 

동작 과정 시뮬레이션

입력: [1,1,3,3,0,1,1]

1: [] → push(1) → [1]
1: top(1)==1 → 무시 → [1]
3: top(1)≠3 → push(3) → [1,3]
3: top(3)==3 → 무시 → [1,3]
0: top(3)≠0 → push(0) → [1,3,0]
1: top(0)≠1 → push(1) → [1,3,0,1]
1: top(1)==1 → 무시 → [1,3,0,1]

결과: [1,3,0,1]

핵심 포인트

1. 스택의 특성 활용: 가장 최근 원소와의 비교가 핵심
2. 간단한 조건문: 다르면 추가, 같으면 무시
3. 효율성: O(n) 시간복잡도로 한 번의 순회만 필요