[백준] 20922 겹치는 건 싫어 - python

링크텍스트

실패 1

문제를 보고, 이를 dictionary로 풀면 쉽겠다고 생각했다.
따라서, 아래의 코드처럼 작성했다.

# 겹치는 건 싫어
import sys

n, k = map(int, sys.stdin.readline().rstrip().split(' '))

array = list(map(int, sys.stdin.readline().rstrip().split(' ')))

menu = {1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0, 0:0}

result = 0

for i in range(n):
    menu[array[i]] += 1
    if menu[array[i]] > k:
        result = i
        break

print(result)

쉽게 통과할 줄 알았지만

위와 같은 런타임 에러가 떴다.
KeyError가 무슨 소리인가 알아보았는데, dictionary 안에 해당 key가 없다는 소리였다.

나는 0~9 숫자만 들어오는 줄 알았는데, 아닌가보다.
따라서 아래처럼, key가 있는 지 확인하고, 없다면 key를 생성하는 방향으로 작성하였다.

for i in range(n):
    if array[i] in menu.keys():
        menu[array[i]] += 1
    else:
        menu[array[i]] = 1
    if menu[array[i]] > k:
        result = i
        break

print(result)

실패 2

그런데!!
틀렸다고 한다...
굳이 첫 번째 원소부터 연속이지 않아도 되는 건데, 그 부분을 확인하지 못하였다.

# 겹치는 건 싫어
import sys

n, k = map(int, sys.stdin.readline().rstrip().split(' '))
array = list(map(int, sys.stdin.readline().rstrip().split(' ')))

menu = {}

result = []
temp = []

for i in range(n):
    if array[i] in menu.keys():
        menu[array[i]] += 1
        temp.append(array[i])
    else:
        menu[array[i]] = 1
        temp.append(array[i])
    if menu[array[i]] > k:
        result.append(len(temp)-1)
        for j in temp:
            menu[j] -= 1
            temp.remove(j)
            if j == array[i]:
                break

result.append(len(temp)-1)

print(max(result))

그런데...
이렇게 고친 이후에도 2%에서 틀렸습니다가 떴다.

해결

예제들을 넣어보니 문제를 찾을 수 있었다.

if menu[array[i]] > k:
    result.append(len(temp)-1)
    for j in temp:
        menu[j] -= 1
        temp.remove(j)
        if j == array[i]:
            break

위의 코드는 k보다 많은 개수의 수가 있을 때, 제일 첫번째 까지 temp 리스트에서 삭제하는 코드라고 내가 작성한 것인데 이 부분이 제대로 작동하지 않았다.

temp에서 j를 삭제하고서는, array[i]와 j를 비교해서 생긴 문제였다.
이를 해결하기 위해 그냥 j를 숫자로 바꾸고, j+1부터 끝까지로 temp를 슬라이싱하였다.
아래는 이를 코드로 옮긴 것이다.

if menu[array[i]] > k:
    result.append(len(temp)-1)
    for j in range(len(temp)):
        menu[temp[j]] -= 1
        if temp[j] == array[i]:
            temp = temp[j+1:]
            break

이렇게 하니 문제를 해결할 수 있었다.