얼마 전 코딩 테스트를 보았다가 충격을 먹고 알고리즘 공부를 다시 시작하게 되었다. (물론 그전에도 하고 있었지만, 더 다양한 알고리즘 문제를 풀어봐야겠다고 생각했다.)
평소엔 Programmers에서 문제 풀이를 자주 했었는데, Github를 꾸미면서 보니 백준에서는 Github에 티어를 나타낼 수 있다는 것을 보고 문제를 풀어보기로 하였다. 처음에는 방식이 익숙치 않았다.
- print()를 이용해 값을 출력한다는 것
- Programmers에서는 괜찮았지만, 몇몇 똑같은 문제에서 시간 초과가 떠 input() 대신 sys.stdin.readline()을 이용해야 한다는 것.
그래도 몇 문제를 해결하고 나니 금방 적응할 수 있었다.
백준 #2531 회전초밥
이번에는 다른 티어의 문제를 풀어보자 하며, 회전초밥 문제를 해결해보기로 했다. 의기양양하게 코드를 짠 뒤 테스트를 마치고 제출을 해보았다. 그런데, 리스트를 사용해서 그런지 시간초과가 떠버렸다. sys.stdin.readline()을 써보기도 했지만, 시간초과 문제는 똑같았다.
#2531
import sys
n, d, k, c = map(int,sys.stdin.readline().split())
dishes = [] #초밥 번호 리스트
for idx in range(n):
dishes.append(int(sys.stdin.readline()))
eat = [] # 먹을 수 있는 초밥 개수 리스트
for idx in range(n):
tmp = [] #임시 리스트
for dish_num in range(idx, idx+k):
if dishes[dish_num % n] in eat:
tmp = []
else:
tmp.append(dishes[dish_num % n])
if (c not in tmp) and (tmp != []):
tmp.append(c)
eat.append(len(tmp))
print(max(eat))다른 방식의 접근이 필요하다는 걸 느꼈다. 그래서 서칭해보니 슬라이딩 윈도우이라는 방식을 사용해야 한다고 한다.
윈도우 슬라이딩은 컨베이어 밸트 위에서 작업이 이루어지는 것처럼 순서대로 처리가능한 값을 읽어들여 처리 하고 가장 앞서 처리된 값을 하나씩 지워나가는 방식이다.
주로 입력된 연속된 값에서 몇 개를 연산해 최소/최대값을 찾는데 사용되는 것 같다. 몇몇 문제의 예시를 보면서 코드를 하나씩 이해하고, 다시 풀어볼 수 있었다.
from collections import defaultdict
n, d, k, c = map(int, input().split())
# 테이블에 놓여진 초밥 번호
sushi_num = [int(input().strip()) for _ in range(n)]
# defaultdict 선언
eat_dict = defaultdict(int)
max = 0
l_num = 0
r_num = k
# k개 일단 집어오기
for idx in range(r_num):
eat_dict[sushi_num[idx]] += 1
# k개 먹은 초밥이 모두 c번이 아닐 경우 주는 서비스 받아오기
# (중복돼도, 최대 개수에는 전혀 지장X)
eat_dict[c] += 1
while l_num < len(sushi_num):
#왼쪽 하나 갖다놓기
eat_dict[sushi_num[l_num]] -= 1
# 값이 없으면 제거
if eat_dict[sushi_num[l_num]] == 0:
del eat_dict[sushi_num[l_num]]
#오른쪽 하나 집어오기, r_num가 n을 초과하는 경우가 있으니 %로 처리
eat_dict[sushi_num[r_num % n]] += 1
r_num += 1
l_num += 1
if max < len(eat_dict):
max = len(eat_dict)
print(max)문제 해결!
이 문제에 defaultdict를 사용했다. defaultdict는 값을 지정해주지 않으면, 호출 시에 default로 지정해준 값(list, str, int 등)을 가지게 된다. 나는 int를 지정해주었다.
윈도우 슬라이딩은 내게 절대 잊지 못할 알고리즘이 되었다.
defaultdict와 함께 앞으로 많은 문제에서 유용하게 쓰일 것 같다.
