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

입출력 예시

Input-1
[1,1,3,3,0,1,1]
Output-1
[1,3,0,1]

Input-2
[4,4,4,3,3]
Output-2
[4,3]

문제 풀이

이 문제는 큐의 FIFO 특성을 활용해 풀어보았다.
주어진 배열의 원소를 순회하며 현재 수와 이전 수가 다를 경우에만 큐에 넣어둔다면 연속으로 나타난 수, 즉 중복을 제거할 수 있다.

한 번 코드로 작성해보자.

Queue<Integer> qu = new LinkedList<>(); // 중복 제거된 수 삽입
int prev = arr[0]; // 이전 수 저장

prev변수를 배열의 첫번째 수로 초기화하고, 함께 사용할 큐를 초기화하였다.

for(int i=1; i<arr.length; i++) {
    if(prev != arr[i]) {
        qu.offer(prev);
        prev = arr[i];
    }
}

주어진 배열의 1번째 인덱스부터 마지막 인덱스까지 순회하며 이전 수를 저장한 prev와 현재 수인 arr[i]를 비교한다.
이전 수와 현재 수가 같지않다면 이전 수(prev)를 큐에 넣고, 이전 수를 현재 수로(prev를 arr[i]로) 최신화 한다.

마지막 수 저장 불가

반복문이 종료되면 배열의 마지막으로 나타난 수는 연속되든 연속되지 않든 큐에 들어가지 않는다.
반복문에선 이전수와 현재수가 다를 때의 조건만 존재하기에 마지막 수의 경우 조건을 타지 않는다.
그렇기에 마지막 수만 별도로 큐에 저장한다.

qu.offer(arr[arr.length-1]); // 맨 마지막 수 저장

이렇게 연속된 수들을 중복없이 큐에 쌓았으니 쌓은 순서대로 반환할 배열에 담으면 된다.
큐의 FIFO 특성으로 인해 poll()로 꺼내면 주어진 배열의 순서대로 담을 수 있다.

int[] answer = new int[qu.size()]; // 반환할 배열
int idx = 0; // 큐를 탐색할 인덱스
while(!qu.isEmpty()) {
    answer[idx] = qu.poll();
    idx++;
}

작성 코드

import java.util.*;

class Solution {
    public static void main(String[] args) {
        int[] arr = {1,1,3,3,0,1,1};
        // int[] arr ={4,4,4,3,3};
        // int[] arr = {1,1,2,3,4,5,5,5,5};
        
        long start = System.currentTimeMillis();
        solution(arr);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }
    public static int[] solution(int[] arr) {
        Queue<Integer> qu = new LinkedList<>();
        int prev = arr[0];
        
        for(int i=1; i<arr.length; i++) {
            if(prev != arr[i]) {
                qu.offer(prev);
                prev = arr[i];
            }
        }
        qu.offer(arr[arr.length-1]);
        
        int[] answer = new int[qu.size()];
        int idx = 0;
        while(!qu.isEmpty()) {
            answer[idx] = qu.poll();
            idx++;
        }

        return answer;
    }
}

회고

• 큐의 FIFO 특성을 이용하여 쌓은 순서대로 꺼내어 입력 순서를 보장할 수 있었다.