프로그래머스 - 같은 숫자는 싫어(Java)

 

 

Queue를 이용하여 해결한 문제이다.

 

알고리즘 설명

1. arr[i]와 arr[i-1]을 비교하여 다르면 큐에 삽입

하지만 이렇게만 하면 4, 4, 4, 3, 3일때 배열의 끝에 있는 3이 삽입이 안된다. 왜냐하면 다를때만 삽입하기 때문이다.

따라서 변수 ex에 저장했던 숫자를 저장해두고 반복문의 마지막에 사용해야함

 

2. 배열의 마지막 숫자가 가장 최근에 삽입한 숫자와 다른 경우 ==> 큐에 삽입해준다.

 

3.큐에서 poll을 이용하여 차례대로 answer배열에 넣어준다.

 

4. answer 리턴

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        int[] answer = {};
        Queue<Integer> q = new LinkedList<>();
        int ex=10;
        for(int i=1; i<arr.length; i++){
            if(arr[i]!=arr[i-1]){
                q.add(arr[i-1]);
                ex=arr[i-1];
            }
            if(i==arr.length-1){
                if(arr[i]!=ex){
                    q.add(arr[i]);
                }
            }
        }
        answer=new int[q.size()];
        int i=0;
        while(!q.isEmpty()){
            answer[i]=q.poll();
            i++;
        }
        return answer;
    }
}

 

 

 

 

 

---

 

2025-03-02 새로운 풀이

 

스택과 큐를 동시에 활용하여 문제를 해결했다.

 

스택 ==> 연속된 수 판별용

큐 ==> 정답으로 반환할 answer 배열에 삽입하기 위한 용도

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        Stack<Integer> stack = new Stack<>();
        Queue<Integer> queue = new LinkedList<>();
        
        for(int i=0; i<arr.length; i++){
            if(stack.isEmpty()){  //처음에는 스택이 비어있으므로 스택과 큐에 모두 삽입
                stack.push(arr[i]);
                queue.add(arr[i]);
            }
            
            else{
                int n = stack.pop();
                if(n!=arr[i]){ //연속된 수가 아니라면 큐와 스택에 추가
                    stack.push(arr[i]);
                    queue.add(arr[i]);
                }
                else{
                    stack.push(n); //연속된 수이면 다시 스택에 추가
                }
            }
        }
        
        int[] answer = new int[queue.size()];
        int i=0;
        while(!queue.isEmpty()){
            answer[i]=queue.poll();
            i++;
        }
        
        return answer; 
    }
}