5일차부터 14일차까지 코테만 풀고 TIL 정리를 안해 정말 밀린 상태에서 작성하고 있다.
논문 리부탈 작업과 가정사로 인해 밀렸지만 다시 시작해보자! (작성 날짜: 8월 5일)
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. 나의 풀이
접근 방법
이 문제는 스택/큐 카테고리에 속한 문제이다. 그럼 스택이냐 큐 자료구조를 활용해서 문제를 접근해보았다. (이러한 접근 방법은 사실 좋은 접근 방법은 아니다..)
스택이란 빈 리스트를 주고, 어떠한 조건에 맞으면 스택에 값을 넣고, 스택을 리턴하면 이 문제를 해결할 수 있을 것처럼 보인다.
그렇다면 어떠한 조건이 무엇일까?
이 문제는 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 한다. 배열 arr에서 연속적으로 나타나는 숫자를 하나로 남기는 값을 스택 리스트에 넣어주는 조건을 만들면 되지 않을까?
조건은 다음과 같이 작성할 수 있다.
- 스택 리스트가 비어있거나 스택 리스트의 마지막값이 arr값과 같지 않다면, 스택 리스트에 arr값을 넣어라!
- 이 조건이 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 한다. 을 만족하는 조건이다.
이것을 코드로 작성하면 다음과 같다.
stack = []
for num in arr:
if not stack or stack[-1] != num:
stack.append(num)전체 코드는 다음과 같다.
def solution(arr):
# stack은 LIFO
stack = []
for num in arr:
if not stack or stack[-1] != num:
stack.append(num)
return stack4. 다른 풀이
이 방법은 문제를 잘 읽고 문제 내용을 그대로 구현한 방법이다. 문제를 살펴보면 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 한다. 라고 나와있다. 여기서 연속적이 키포인트라 볼 수 있다.
반복문을 통해, 현재 값과 이전값이 같지 않으면 새로운 리스트에 넣고, 아니면 넣지 않는 형태로 하여 그 새로운 리스트를 리턴한다면 연속적으로 나타나는 숫자를 제외한 리스트를 구할 수 있다.
코드는 아래와 같다.
def solution(arr):
ans = [arr[0]]
for i in range(1,len(arr)):
if arr[i] != arr[i-1]:
ans.append(arr[i])
return ans5. 결론
이 문제는 스택을 활용한 방법이다. 문제의 제목을 보자마자 집합 자료형을 쓸 뻔했지만 쭉 읽어보고 문제의 카테고리를 보니 스택을 활용한 방법을 사용하게 되었다. 스택을 사용하지 않더라도, 문제의 내용을 그대로 코드로 변환하는 과정을 거쳐도 해결할 수 있었다.
읽어 주셔서 감사합니다!
