99클럽 코테 스터디 2일차 TIL + Queue, LinkedList

✨ 문제 

같은 숫자는 싫어

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

- arr = [1, 1, 3, 3, 0, 1, 1]이면 [1, 3, 0, 1]을 return 합니다.

- arr = [4, 4, 4, 3, 3]이면 [4, 3]을 return 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return하는 solution 함수를 완성해 주세요.

 

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

프로그래머스

 

 

 

✨ 개념

LinkedList

- List 구현 클래스로, 인접 참조를 링크해서 체인처럼 관리함.

- LinkedList에서 특정 인덱스의 객체를 제거하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않음. 그래서 순차적 연산이 아닌 중간에 삽입, 삭제 연산이 많이 일어나는 경우 LinkedList가 적합함. 

 

Queue

- FIFO 자료구조로 인터페이스이다. 

- Queue 인터페이스를 구현한 대표적 클래스 중 하나가 LinkedList임

 

 

 

✨ 최종코드

public int[] solution(int []arr) {
    if (arr.length == 0)
        return new int[0];

    Queue<Integer> queue = new LinkedList<>();

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

    int[] answer = new int[queue.size()];
    int i = 0;
    while (!queue.isEmpty())
        answer[i++] = queue.poll();

    return answer;
}

 

Queue를 사용해서 풀어야하는 것 같아 시도해봤지만  도저히 방법을 모르겠어서 gpt에게 물어보니 리스트를 사용해도 상관없다는 식으로 답하길래 List를 사용해서 풀어보았다. 그러나 유효성 테스트에서 통과하지 못했다  . . 그래서 다시 Queue를 사용하여 풀었고 위 코드로 통과하였다. 그래서 도대체 시간이 얼마나 차이가 나길래 그러는지 확인해봤는데 List가 79600ns, Queue가 29300ns로 약 2.7배 정도 차이가 났다. 아무튼 어제 오늘 알고리즘을 풀면서 문제의 요구사항에 맞게 적절한 자료구조를 사용해야 한다는걸 깨달았다.