스택/큐 - 같은 숫자는 싫어[프로그래머스 고득점 Kit]

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

프로그래머스

 

문제에 대한 내 첫 번째 풀이

문제에서 배열 arr이 매개변수로 주어지고, 각 원소가 숫자 0부터 9까지 구성되어 있다고 했다.

배열 arr에서 연속적으로 나타내는 숫자는 하나만 남기고 전부 제거하라고 했는데, 이 문장만 보고 그냥 배열에서 중복만 제거하면 되는 거 아닌가? 라는 생각을 단순하게 했고, Set() 을 활용했다.

그 결과 테스트 케이스 2개 중 한 개는 통과했고, 한 개는 통과하지 못했다.

 

실패한 코드

function solution(arr)
{
    let answer = []; // 배열에서 중복 제거 후 return
    let remove = [...new Set(arr)]; // remove에 중복 제거된 배열을 새로 생성
    answer = remove;
    
    return answer;
}

 

실행한 결과

테스트 1
입력값 〉	[1, 1, 3, 3, 0, 1, 1]
기댓값 〉	[1, 3, 0, 1]
실행 결과 〉	실행한 결괏값 [1,3,0]이 기댓값 [1,3,0,1]과 다릅니다.

테스트 2
입력값 〉	[4, 4, 4, 3, 3]
기댓값 〉	[4, 3]
실행 결과 〉	테스트를 통과하였습니다

 

문제를 다시 읽어보니, Set()을 활용해서 해시 알고리즘을 쓰겠다는 것은 옳지 못한 생각이었다!!

 

문제에서 요구하는 것은, 연속적으로 나타나는 숫자를 하나만 남기고 나머지는 제거하는 것이다.
예를 들어, [1, 1, 3, 3, 0, 1, 1]과 같은 배열이 주어졌을 때, 연속해서 나타나는 숫자 1과 3을 하나만 남기고 나머지를 제거하여 [1, 3, 0, 1] 을 반환해야 한다.

 

풀이 방식 : 반복문을 사용하여 배열을 순회하면서 연속된 숫자를 확인하고 중복을 제거함

 

코드를 보자.

// arr 배열에서 연속적인 숫자들 중 하나만 남기고, 제거
// [1, 1, 3, 3, 0, 1, 1] 일 경우, [1, 2, 3, 0, 1];
// 배열에서 중복되는 것을 제거하는 Set()을 활용한다면 [1, 1, 3, 3, 0, 1, 1] 이 주어질 경우 결과값이 [1, 3, 0] 이 된다. 중복이 아예 되면 안되기 때문에, 그래서 여기서는 모든 배열을 반복문을 통해 순회하면서 연속적인 숫자들 중 하나만 남기고 제거하는 조건문을 걸면 해결이 가능한 문제다.

function solution(arr) { // arr은 1차원 배열
    let answer = []; // 결과를 저장할 빈 배열 선언
    
    for(let i = 0; i < arr.length; i++) { // 반복문으로 배열 순회
        if(arr[i] !== arr[i+1]) { // 현재 요소와 다음 요소가 다르다면
            answer.push(arr[i]); // 결과 배열에 현재 요소 추가
        }
    } 
    
    return answer; // 결과 배열 반환
}

 

문제 풀이 방법 : 배열을 순회하면서 중복을 제거
스택과 큐 알고리즘은 이와 같은 방식으로 연속된 요소를 제거하는 데에는 직접적으로 사용되지 않는다.
위 문제 풀이 방식에서 사용되지는 않았지만, 스택, 큐 알고리즘이란 무엇인지 보자!

 

스택 (Stack)

 

- 후입선출(LIFO, Last-In-First-Out) 구조를 가진다.

- 데이터를 쌓아올리는 구조로, 가장 최근에 추가된 데이터가 가장 먼저 제거된다.

- 주로 재귀 함수 호출, 브라우저의 뒤로 가기 등에 활용된다.

 

큐(Queue)

 

- 선입선출(FIFO, First-In-First-Out) 구조를 가진다.

- 데이터가 일렬로 줄 서 있는 구조로, 가장 먼저 추가된 데이터가 가장 먼저 제거도니다.

- 주로 작업 대기열, 너비 우선 탐색(BFS, Breadth-First Search) 등에 활용된다.