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

개요

문제 이름: 같은 숫자는 싫어 (12906)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12906
플랫폼: 프로그래머스
알고리즘 분류: 스택/큐
소요 시간: 1시간 15분

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 배열에서 연속적으로 나타나는 중복 숫자를 제거하고 남은 숫자들을 원래 순서대로 반환하는 알고리즘 문제입니다. 문제에서 요구하는 사항을 정리하면 다음과 같습니다.

1. 배열에서 연속적으로 나타나는 숫자는 하나만 남기고 제거한다.
2. 제거된 후 남은 숫자들은 기존 배열의 순서를 유지해야 한다.

이 문제를 해결하기 위해 스택(Stack) 자료구조를 활용할 수 있습니다. 스택은 후입선출(LIFO - Last In First Out)의 특징을 가지고 있어, 가장 마지막에 들어온 데이터가 가장 먼저 나가는 구조입니다.

 

스택을 사용하여 배열을 순회하면서, 현재 숫자와 이전 숫자를 비교하여 다른 경우에만 스택에 push하는 방식으로 중복을 제거할 수 있습니다.

 

문제 해결 과정은 다음과 같습니다:

1. 빈 스택을 초기화합니다.
2. 배열을 순회하면서, 현재 숫자와 스택의 top에 있는 숫자를 비교합니다.
   • 스택이 비어있거나, 현재 숫자와 스택의 top에 있는 숫자가 다른 경우에만 현재 숫자를 스택에 push합니다.
3. 스택에 남아있는 숫자들을 배열로 반환합니다.

이를 통해 연속적인 중복 숫자를 제거하고, 남은 숫자들의 순서를 유지할 수 있습니다.

 

시도

1차 시도  (성공)

// 1차 시도 (성공) - 스택/큐 미사용
function solution(arr) {
	return arr.filter((value, index) => value != arr[index + 1]);
}

처음에는 스택이나 큐를 사용하지 않고 배열의 filter 메서드를 사용하여 문제를 해결했습니다. filter 메서드는 콜백 함수의 조건에 맞는 요소들만 추출하여 새로운 배열을 반환합니다. 현재 요소와 다음 요소를 비교하여 다른 경우에만 남기는 방식으로 중복을 제거했습니다.

이 방법은 간단하고 직관적이지만, 배열의 크기가 커질수록 성능이 저하될 수 있습니다. 시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)입니다.

 

2차 시도  (성공)

// 2차 시도 (성공) - 내장 스택 사용
function solution(arr) {
	const stack = [];
	for (let i = 0; i < arr.length; i++) {
		if (stack.length === 0 || arr[i] !== stack[stack.length - 1]) {
			stack.push(arr[i]);
		}
	}
	return stack;
}

2차 시도에서는 스택을 활용하여 문제를 해결했습니다. 배열을 순회하면서, 스택이 비어있거나 현재 숫자와 스택의 top에 있는 숫자가 다른 경우에만 현재 숫자를 스택에 push합니다. 이렇게 하면 연속적인 중복 숫자는 스택에 추가되지 않고, 최종적으로 스택에는 중복이 제거된 숫자들만 남게 됩니다.

이 방법은 스택을 사용하여 중복을 효과적으로 제거할 수 있었습니다. 시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)입니다.

 

3차 시도 (실패)

// 3차 시도 (실패: 시간 초과) - 자체 연결리스트 스택 사용
function solution(arr) {
	const stack = new Stack_LinkedList();
	for (let i = 0; i < arr.length; i++) {
		if (arr[i] != arr[i + 1]) {
			stack.push(arr[i]);
		}
	}
	return stack.toArray();
}

// 연결리스트 노드
class Node {
	constructor(data) {
		this.data = data;
		this.next = null;
	}
}

// 연결리스트 스택
class Stack_LinkedList {
	constructor() {
		this.top = null;
		this.size = 0;
	}
	push(data) {
		const newNode = new Node(data);
		newNode.next = this.top;
		this.top = newNode;
		this.size++;
	}
	pop() {
		if (this.isEmpty()) {
			return;
		} else {
			this.top = this.top.next;
			this.size--;
		}
	}
	peek() {
		if (this.isEmpty()) {
			return;
		} else {
			return this.top.data;
		}
	}
	toArray() {
		const result = [];
		let current = this.top;
		while (current) {
			result.unshift(current.data);
			current = current.next;
		}
		return result;
	}
	getSize() {
		return this.size;
	}
	isEmpty() {
		return this.top === null;
	}
}

3차 시도에서는 직접 구현한 연결 리스트 기반의 스택을 사용하여 문제를 해결하려 했습니다. 연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조입니다. 연결 리스트로 구현한 스택은 맨 앞에 있는 노드를 top으로 지정하고, 새로운 요소를 삽입할 때는 top 앞에 새로운 노드를 추가하는 방식으로 동작합니다.

배열을 순회하면서, 현재 숫자와 다음 숫자를 비교하여 다른 경우에만 현재 숫자를 스택에 push합니다. 최종적으로 스택에 남아있는 숫자들을 배열로 변환하여 반환합니다.

 

하지만 이 방법은 연결 리스트의 특성상 데이터 접근 속도가 느리기 때문에 효율성 테스트에서 시간 초과가 발생했습니다. 연결 리스트는 데이터를 찾기 위해서는 처음부터 순차적으로 탐색해야 하기 때문에 배열에 비해 접근 속도가 느립니다. 따라서 데이터 접근이 빈번한 경우에는 배열 기반의 스택이 더 적합하다고 할 수 있겠습니다.

 

4차 시도 (성공)

// 4차 시도 (성공) - 자체 배열 스택 사용
function solution(arr) {
	const stack = new Stack_Array();
	for (let i = 0; i < arr.length; i++) {
		if (arr[i] != arr[i + 1]) {
			stack.push(arr[i]);
		}
	}
	return stack.toArray();
}

// 배열 스택
class Stack_Array {
	constructor() {
		this._arr = [];
	}
	push(item) {
		this._arr.push(item);
	}
	pop() {
		return this._arr.pop();
	}
	peek() {
		return this._arr[this._arr.length - 1];
	}
	toArray() {
		return [...this._arr];
	}
	getSize() {
		return this._arr.length;
	}
	isEmpty() {
		return this.getSize() === 0;
	}
}

4차 시도에서는 직접 구현한 배열 기반의 스택을 사용하여 문제를 해결했습니다. 배열을 순회하면서, 현재 숫자와 다음 숫자를 비교하여 다른 경우에만 현재 숫자를 스택에 push합니다. 최종적으로 스택에 남아있는 숫자들을 배열로 변환하여 반환합니다.

이 방법은 자체적으로 구현한 스택을 활용하여 문제를 해결한 것이 특징입니다. 스택의 구현 방식에 따라 성능이 달라질 수 있습니다. 배열 기반의 스택은 시간 복잡도와 공간 복잡도 모두 O(n)입니다.

 

사족

이 문제를 통해 스택 자료구조의 활용 방법과 중복 제거 알고리즘에 대해 알 수 있었습니다. 스택을 사용하면 연속적인 중복 숫자를 효과적으로 제거할 수 있음을 확인했습니다. 또한, 직접 스택을 구현해보면서 자료구조에 대한 이해도를 높일 수 있었습니다.