[오늘의 문제] 같은 숫자는 싫어

출처: https://school.programmers.co.kr/learn/courses/30/lessons/12906?language=python3

문제 설명
배열 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
문제의 예시와 같습니다.

내가 작성한 코드문

def solution(arr):
    answer = []
    # [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    set_data = set(arr)
    answer = list(set_data)
    
    return answer

이렇게 되면 중복은 set을 통해 제거가 된다.
하지만 순서가 유지가 안됨 무조건 오름차순 정렬

두번째 시도

def solution(arr):
    # answer = []
    # [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    # answer 변수 제거
    
    # while문 으로 해보고 초기값 i = 1
    i = 1
    while i < len(arr):
        if arr[i] == arr[i-1]: # 현재 i 위치의 원소 삭제. 인덱스는 그대로 둠
            arr.pop(i) # i < len(arr) 조건이 리스트가 줄어들 때마다 다시 평가됨 
        else: 
            i += 1 # 중복이 아니면 다음 인덱스로 이동

    return arr

채점 결과
정확성: 71.9
효율성: 0.0
합계: 71.9 / 100.0
시간 초과가 뜬다.

AI 코드 피드백 이용결과..
사용자의 코드에서 arr.pop(i)를 사용해 현재 원소를 삭제할 때, 리스트의 길이가 달라지고, 인덱스도 조정됩니다. 그러나 코드에서는 i를 증가시키기 전에 삭제를 하기 때문에, 연속된 중복 원소 중 두 번째 원소부터 제대로 검사하지 못하는 문제가 발생합니다.

예를 들어, [1, 1, 1]과 같은 리스트가 있다면, 첫 번째 '1'이 삭제된 후 다음 '1' 또한 검사해야 하지만, i 값을 증가시키는 현재 방식으로는 그 다음 원소를 뛰어넘고 말 것입니다. 즉, 첫 번째 '1'을 삭제한 뒤, i를 증가시켜 다음 '1'을 바로 검사하지 않고 그 다음 인덱스로 넘어가 버립니다.

이 문제를 해결하기 위해서는, 원소를 삭제한 후에 인덱스를 증가시키지 않고, 삭제하지 않았을 때만 인덱스를 증가시켜야 합니다. 원소를 삭제했다면, 다음 순회에서 같은 인덱스를 다시 검사할 수 있도록 i의 값에 변화를 주지 않아 현재 위치를 유지해야 합니다.

🔍 문제 상황 요약

코드는 인접한 중복 원소를 제거하려는 의도다.
[1,1,3,3,0,1,1] → [1,3,0,1] 이런 식으로.

⚙️ 핵심 원인: list.pop(i)의 시간 복잡도

파이썬의 list.pop(i) (단, i가 마지막이 아닐 때)는
👉 O(N) (리스트 길이에 비례) 시간이 걸린다.

왜냐면, 리스트는 연속된 메모리 공간에 데이터를 저장하므로,
중간 원소를 삭제하면 그 뒤의 모든 원소를 한 칸씩 앞으로 이동시켜야 하기 때문이다.

📉 따라서 전체 복잡도는?

while문은 최대 N번 반복

각 반복에서 pop(i)가 최악의 경우 O(N)

👉 전체 시간 복잡도는 O(N²) 이 된다.

길이가 수천 이상인 입력에서는 시간 초과가 난다.

✅ 효율적인 해결 방법

리스트를 직접 수정하지 말고,
새로운 리스트에 값을 하나씩 쌓는 방식으로 해결하면 O(N)에 된다.
예시👇

def solution(arr):
    result = []
    for num in arr:
        if not result or result[-1] != num:
            result.append(num)
    return result

이 방식은 pop이나 insert를 사용하지 않고,
단순히 한 번의 순회(O(N))로 해결할 수 있다.

원인	설명
arr.pop(i)	O(N) 연산이라 반복문과 함께 쓰면 느림
while문 구조	리스트 길이가 줄어들며 반복 많아짐
해결책	새 리스트에 조건적으로 append (O(N))

다른 사람의 풀이

def no_continuous(s):
    # 함수를 완성하세요
    a = []
    for i in s:
        if a[-1:] == [i]: continue
        a.append(i)
    return a

새로운 리스트 a를 만들어 정답을 축적하는 방식(가장 권장되는 O(N) 풀이)이다.

1. 초기화 및 반복 (Initialization and Iteration)

• 결과를 담을 빈 리스트 a를 생성한다.

• 입력 리스트 s의 원소를 순서대로 i에 담아 반복한다.

a = []
for i in s:

2. 이전 원소와의 비교 (The Core Logic)

if a[-1:] == [i]: continue

• a[-1:]:

리스트 a의 마지막 원소 하나를 추출하는 슬라이싱입니다.

결과는 항상 리스트 형태로 나옵니다 (예: [1], [3]).

a가 비어 있을 경우 ([]), a[-1:]의 결과는 빈 리스트 []가 됩니다.

• [i]:

현재 반복 중인 원소 i를 리스트 형태로 만듭니다 (예: [1], [3]).

• == 비교:
  경우 1: a가 비어 있을 때

[] == [i]는 항상 False이다. 따라서 continue가 실행되지 않고, a.append(i)로 이동하여 첫 번째 원소가 a에 추가된다.

경우 2: a에 원소가 있고 중복일 때

a가 [1, 3]이고 i가 3이라면, [3] == [3]이 되어 True다.

continue가 실행되어 a.append(i)를 건너뛰고 다음 반복으로 넘어간다. (중복 제거)

경우 3: a에 원소가 있고 중복이 아닐 때

a가 [1, 3]이고 i가 0이라면, [3] == [0]이 되어 False다.

a.append(i)로 이동하여 0이 a에 추가됩니다. (새로운 원소 축적)

3. 원소 추가 및 반환

    a.append(i)
return a

• 비교 결과 중복이 아닌 경우에만 현재 원소 i를 결과 리스트 a에 추가한다.

• 모든 반복이 끝나면 중복이 제거된 리스트 a를 반환한다.
  

✨ 코드의 장점 요약
O(N) 시간 복잡도: 리스트 순회(O(N))와 리스트 끝에 추가(O(1))만 사용하므로 가장 효율적이다.

안전성: a[-1:] 슬라이싱을 사용하여 a가 비어있는 경우([])에 대한 예외 처리가 자연스럽게 이루어지므로, IndexError 발생 위험이 없다.

가독성: while 문과 pop(i)를 사용하여 인덱스를 조정할 필요가 없어 코드가 간결하고 이해하기 쉽다.

def no_continuous(s):
    # 함수를 완성하세요
    result = []
    for c in s:
        if len(result) == 0 or result[-1] != c:
            result.append(c)

    return result    

이전 풀이(if a[-1:] == [i]: continue)보다 명시적이며, 특히 리스트가 비어 있는 초기 상태를 len(result) == 0으로 명확하게 처리한다.

✅ 풀이 분석: len(result) == 0 or result[-1] != c
이 코드는 새로운 리스트 result를 만들고, 입력 문자열/리스트 s를 순회하며 조건을 검사하는 방식으로 작동한다.

1. 초기화 및 반복

result = []
for c in s:

• 결과를 담을 빈 리스트 result를 생성합니다.

• 입력 s의 원소를 순서대로 c에 담아 반복합니다.

2. 조건 검사 (핵심 로직)

if len(result) == 0 or result[-1] != c:
        result.append(c)

if 조건문은 두 부분으로 구성되어 있으며, or 연산자로 연결되어 있다.

제시해주신 코드는 이전 풀이와 동일한 $O(N)$의 시간 복잡도를 가지며, 가장 표준적이고 정석적인 방식으로 연속 중복을 제거한다.

이 코드는 이전 풀이(if a[-1:] == [i]: continue)보다 명시적이며, 특히 리스트가 비어 있는 초기 상태를 len(result) == 0으로 명확하게 처리한다.

✅ 풀이 분석: len(result) == 0 or result[-1] != c
이 코드는 새로운 리스트 result를 만들고, 입력 문자열/리스트 s를 순회하며 조건을 검사하는 방식으로 작동한다.

1. 초기화 및 반복
   Python

result = []
for c in s:
결과를 담을 빈 리스트 result를 생성한다.

입력 s의 원소를 순서대로 c에 담아 반복한다.

2. 조건 검사 (핵심 로직)
   Python

   if len(result) == 0 or result[-1] != c:
       result.append(c)

   if 조건문은 두 부분으로 구성되어 있으며, or 연산자로 연결되어 있다.

조건 1: len(result) == 0
의미: 결과 리스트가 비어 있다면 (즉, 첫 번째 원소를 처리하는 중이라면) True가 된다.

작동: or 연산자는 앞의 조건이 True이면 뒤의 조건을 확인하지 않고 바로 실행 블록으로 진입합니다. 따라서 리스트가 비어 있으면 첫 번째 원소는 무조건 result에 추가된다.

조건 2: result[-1] != c
의미: 결과 리스트의 마지막 원소(result[-1])가 현재 원소(c)와 다르다면 True가 된다.

작동: result에 이미 원소가 있을 때 (즉, len(result) > 0일 때) 이 조건이 평가된다.

다르면 (중복 아님): True가 되어 result.append(c)가 실행됩니다.

같으면 (중복임): False가 되어 append를 건너뛰고 다음 반복으로 넘어간다.

3. 최종 결과
   결과적으로 이 코드는 모든 원소를 한 번씩(O(N)) 확인하며, 결과 리스트의 마지막 원소와 현재 원소가 다를 때만 result에 추가하여 연속 중복을 깔끔하게 제거한다.