백준 #23567 Double Rainbow

코드

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline


def check(ls):  # 1부터 k까지 숫자를 포함하고 있는 지 확인
    for i in range(1, k + 1):
        if ls[i] == 0:
            return False
    return True

n, k = map(int, input().split())
arr = [int(input()) for _ in range(n)]
min_value = n
visited_rest = [0] * (k + 1)    # 전체에서 진행중인 수열을 제외한 부분
for num in arr:
    visited_rest[num] += 1

visited = [0] * (k + 1)         # 진행시킬 수열
end = 0

for start in range(n):
    flag = False
    while end < n:
        visited[arr[end]] += 1
        visited_rest[arr[end]] -= 1
        if check(visited):
            if check(visited_rest):
                min_value = min(min_value, end - start + 1)
            flag = True # 진행중인 수열에 대해서 check가 되었으면 일단 while 문 나오기
        if flag:
            visited[arr[end]] -= 1
            visited_rest[arr[end]] += 1
            break
        end += 1

    visited[arr[start]] -= 1
    visited_rest[arr[start]] += 1

if min_value == n:
    print(0)
else:
    print(min_value)

풀이

ICPC 문제들을 보다가 난이도도 골드5이고 풀만해 보여서 도전한 문제이다.

투 포인터로 접근했고(사실 문제 분류를 슬쩍 보았고) 당연히 첫 시도는 실패였다 ㅎㅎ

처음에는 배열을 슬라이싱 해가면서 풀었는데 시간초과 문제였다.

생각을 하다가 숫자는 1~k로 고정이기 때문에 크기가 (k + 1)인 visited 배열을 두개 만들어서

진행중인 수열과 나머지 수열의 숫자들의 개수를 저장시켜주는 방식으로 했다.

만약 visited를 검사했을 때 0인 부분이라도 있으면 조건을 만족시키지 못하는 것이다.