오늘 문제는 백준이 아닌 프로그래머스 문제입니다. 계속 진행해왔던 스택 자료구조 유형의 문제입니다. 한 번 살펴볼까요?
1. 오늘의 학습 키워드
- 스택
2. 문제: 같은 숫자는 싫어
문제 설명
배열 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 함수를 완성해 주세요.
제한사항
- 배열 arr의 크기 : 1,000,000 이하의 자연수
- 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수
입출력 예
| arr | answer |
|---|---|
| [1,1,3,3,0,1,1] | [1,3,0,1] |
| [4,4,4,3,3] | [4,3] |
입출력 예 설명
입출력 예 #1,2
문제의 예시와 같습니다.
3. 나의 풀이
문제 이해 및 접근
이 문제는 배열에서 연속적으로 중복된 숫자를 제거하고, 남은 숫자들을 배열의 순서를 유지하면서 반환하는 문제입니다. 즉, 연속된 중복된 숫자를 하나로 축약하여 배열을 만들어야 합니다. 문제를 해결하기 위한 핵심 아이디어는 바로 연속된 숫자의 중복을 확인하고 제거하는 것입니다.
이 문제는 두 가지 방법으로 해결할 수 있습니다:
- 스택(Stack) 자료구조를 활용한 방법.
- 반복문을 사용하여 이전 숫자와 비교하는 방법.
스택 자료구조를 사용하면, 데이터를 순차적으로 처리하면서 조건에 따라 저장할지 여부를 결정할 수 있습니다. 스택을 사용하지 않더라도 단순히 반복문을 통해 이전 원소와 비교하여 연속된 숫자를 제거하는 방식으로도 풀 수 있습니다.
코드 분석
1. 스택을 활용한 풀이
from collections import deque
def solution(arr):
stack = deque() # 스택으로 사용할 deque 생성
for num in arr: # 배열의 각 숫자에 대해
if not stack or stack[-1] != num: # 스택이 비었거나, 마지막 숫자가 현재 숫자와 다르면
stack.append(num) # 스택에 숫자 추가
return list(stack) # 스택을 리스트로 변환하여 반환
설명:
- 이 방법은 스택(Stack)을 사용하여 중복을 제거합니다.
deque를 스택처럼 사용하여, 숫자를 차례대로 처리하면서 스택의 마지막에 있는 숫자와 현재 숫자를 비교합니다. 만약 연속되지 않으면 스택에 숫자를 추가합니다.- 중복이 없는 최종 결과를 반환할 때는, 스택을 리스트로 변환하여 반환합니다.
핵심 로직은 if not stack or stack[-1] != num 구문입니다.
- 스택이 비어 있거나, 스택의 마지막 원소와 현재 원소가 다르면 현재 숫자를 스택에 추가하는 방식으로 연속된 중복을 제거합니다.
시간 복잡도:
- 배열의 길이를
n이라고 하면, 배열을 한 번 순회하므로 의 시간 복잡도를 가집니다.
2. 반복문에서 비교를 활용한 풀이
def solution(arr):
result = [arr[0]] # 첫 번째 원소를 결과 리스트에 넣음
for i in range(1, len(arr)): # 두 번째 원소부터 시작하여
if arr[i] != arr[i-1]: # 현재 원소와 이전 원소가 다르면
result.append(arr[i]) # 결과 리스트에 현재 원소 추가
return result
설명:
- 이 방법은 단순히 배열의 첫 번째 원소를
result리스트에 넣고, 두 번째 원소부터 반복문을 돌며 바로 이전 원소와 비교하는 방식입니다. - 만약 현재 원소가 이전 원소와 다르면
result리스트에 그 값을 추가합니다. - 즉, 인접한 숫자가 같은지 비교하면서 중복된 숫자를 건너뛰는 방식입니다.
이 방식도 간단하면서 효율적입니다. 배열의 원소들을 순차적으로 처리하고 바로 이전 원소와 비교하는 방식으로 중복을 제거합니다.
시간 복잡도:
- 배열의 길이를
n이라고 하면, 마찬가지로 배열을 한 번 순회하므로 의 시간 복잡도를 가집니다.
두 풀이 방법 비교
- 스택을 사용한 풀이는 스택 자료구조를 활용해 조건을 만족할 때만 원소를 추가하는 방식으로 중복을 제거합니다. 이 방식은 스택의
append()와pop()연산이 간단하고 명확하게 동작합니다. - 반복문 비교를 사용한 풀이는 더 직관적이며, 배열에서 인접한 원소들만 비교하여 처리합니다. 중복 제거의 원리는 같지만 스택을 사용하지 않으므로 코드가 더 간결합니다.
두 풀이 모두 시간 복잡도는 으로 동일하며, 배열의 길이가 최대 1,000,000 이하로 주어지기 때문에 두 방법 모두 성능 상의 문제는 없습니다.
마무리
이번 문제는 연속된 숫자의 중복을 제거하는 간단한 알고리즘 문제였지만, 두 가지 접근 방식으로 해결할 수 있었습니다. 스택을 활용하는 방법과 단순한 반복문 비교 방식을 통해, 문제의 핵심인 중복 제거를 효율적으로 구현할 수 있었습니다.
두 풀이 모두 시간 복잡도 을 가지며, 배열의 크기가 최대 1,000,000까지 주어져도 성능 상의 문제가 없음을 확인할 수 있었습니다.
이 문제는 스택과 배열 탐색의 기본적인 개념을 익히고, 효율적으로 문제를 해결하는 능력을 키울 수 있는 좋은 연습 문제입니다. 또한, 단순한 문제라도 여러 가지 방식으로 접근할 수 있다는 점에서 다양한 풀이 방법을 고민해보는 것도 좋은 학습 방법이 될 것입니다.
어제보다 발전한 개발자가 될거야!!💪
