[JAVA] 프로그래머스 | 12906 같은 숫자는 싫어

📝 TIL

- [프로그래머스] 12906 같은 숫자는 싫어

https://school.programmers.co.kr/learn/courses/30/lessons/12906

 

제한사항

배열 arr의 크기 : 1,000,000 이하의 자연수

배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

 

입출력 예

입력#1

[1, 1, 3, 3, 0, 1, 1]

[1, 3, 0, 1]

 

출력#1

[1, 3, 0, 1]

[4, 3]

 

---

🦔 설계 및 시도

1. stack을 사용하여 아예 비어있으면 값을 넣고,

2. 앞의 값과 동일하면 안 넣기 / 2-1. 다르면 넣기

 

처음에 stack을 사용해서 아래와 같이 풀었다.

 

public class Solution {
    public int[] solution(int []arr) {
        Stack<Integer> num = new Stack<>();
        
        for(int a : arr){
           if(num.isEmpty()) {
               num.push(a);
           }
            else {
                int n = num.pop();
                if(n==a) {
                    num.push(n);
                }
                else {
                    num.push(n);
                    num.push(a);
                }
            }
        }
        
        int[] answer=new int[num.size()];
        for(int i=0; i<num.size(); i++){
            answer[i]=num.get(i);
        }

        return answer;
    }

 

예전에 풀었을 때도 이렇게 풀었던 거 같은데,

deque를 사용해서 푸는 방법으로 전환하고 싶어서

+ for문 내의 if문이 너무 많은 거 같아서 다시 풀어보았다.

 

🔥 풀이에 사용된 개념

Deque<Integer> num = new Array<>();

Deque는 Stack, Queue와 비슷하지만, '양방향'이라는 점에서 다르고, 효율적이다!

- 양방향 삽입/삭제가 가능한 큐

- LIFO처럼, FIFO처럼 둘다 사용 가능

 

peekLast()

마지막 요소 확인(stack의 peek과 비슷)

 

addLast()

뒤에 요소 추가

 

Deque에서의 push() / pop()

- Stack 처럼 사용된다!

- push(E e) : 실제 동작 addFirst(e) : 앞쪽 헤드 삽입

- pop() : 실제 동작 removeFirst(e) : 앞쪽에서 제거

 

---

💡 풀이 소스 코드

 

시간복잡도 : O(n)

 

public class Solution {
    public int[] solution(int []arr){
        Deque<Integer> num = new ArrayDeque<>();
        
        for(int a: arr){
            if(num.isEmpty() || num.peekLast() != a) {
                num.addLast(a);
            }
        }
        
        int[] answer = new int[num.size()];
        int i=0;
        for(int n : num){
            answer[i]=n;
            i++;
        }
        return answer;
    }
}

 

---

🚀 새로 배운 내용

- Deque는 인덱스처럼 접근할 수 없다! 따라서 배열 변환이 필요할 땐 향상된 for를 사용하여 하나씩 꺼내자

 

---

😺  느낀점

- Deque를 활용하여 많이 풀어보자

 

 

*소스 코드는 다음 깃허브에 올라옵니다 - https://github.com/s0ooo0k/Algorithm_Study

GitHub - s0ooo0k/Algorithm_Study: Algorithm Study 문제 및 풀이