cho.sh

화성 DNA

K개 기호로 이루어진 문자열과 R개 기호의 최소 개수가 주어질 때, 모든 조건을 만족하는 가장 짧은 연속 부분 문자열의 길이를 구하고 없으면 impossible을 출력한다.

보통5슬라이딩 윈도우배열투 포인터해시맵면접 대비아직 제출이 없습니다시간 제한2초메모리 제한1024 MB

문제

인간의 DNA는 4종류의 염기(아데닌, 사이토신, 구아닌, 티민에 대응하는 A, C, G, T)로 이루어진 긴 문자열로 나타낼 수 있다.

그러나 화성인의 DNA는 다르다. 최근 조사 결과 화성인의 DNA는 무려 K종류의 염기로 이루어져 있으며, 따라서 크기가 K인 알파벳 위의 문자열로 나타낼 수 있다.

어느 연구팀이 화성 DNA를 인공지능에 활용하기 위해 화성 DNA 문자열의 연속 구간 하나를 표본으로 요청했다. R개의 염기에 대해서는 그 염기가 표본 안에 최소 몇 개는 들어 있어야 한다는 조건이 정해져 있다.

DNA의 연속 부분문자열 중에서 연구팀의 요구 조건을 모두 만족하는 가장 짧은 구간의 길이를 구하라.

입력

첫째 줄에 화성 DNA의 전체 길이, 알파벳 크기, 수량 조건이 있는 염기의 수를 나타내는 세 정수 N, K, R이 주어진다. 1≤R≤K≤N1 \le R \le K \le N을 만족한다.

둘째 줄에는 화성 DNA 전체를 나타내는 N개의 정수가 공백으로 구분되어 주어진다. i번째 정수 DiD_i는 DNA 문자열의 i번째 위치에 있는 염기를 나타내며, 염기는 0부터 번호가 매겨져 0≤Di<K0 \le D_i < K를 만족한다. 모든 염기는 DNA 문자열 안에 최소 한 번은 등장한다.

이어지는 R개의 줄에는 각 염기와 그 최소 필요 수량을 나타내는 두 정수 B와 Q가 주어진다(0≤B<K0 \le B < K, 1≤Q≤N1 \le Q \le N). 같은 염기가 두 번 이상 주어지지 않는다.

출력

연구팀의 요구 조건을 만족하는 DNA의 연속 부분문자열 중 길이가 가장 짧은 것의 길이를 하나의 정수로 출력하라. 그런 부분문자열이 존재하지 않으면 impossible을 출력하라.

힌트

오른쪽 끝을 한 칸씩 확장하면서 왼쪽 끝을 가능한 만큼 좁히는 슬라이딩 윈도우로 풀 수 있다. 조건이 있는 각 염기가 현재 구간 안에 몇 개 들어 있는지 세고, 요구 수량을 채운 염기가 몇 종류인지 함께 관리하면 DNA 전체를 한 번 훑는 동안 최적 길이를 찾을 수 있다.