내용

글번호 802
작성자 heojk
작성일 2018-01-19 16:17:46
제목 코딩 테스트 1-1
내용 가장 작은 영역 어떤 문서에 등장하는 단어들 중 특정한 단어들이 단어 별로 지정된 횟수 이상 가장 가깝게 등장하는 영역을 찾고자 한다. 즉, 입력에는 (a, x)의 순서쌍들이 주어지는데, a는 단어의 번호, x는 그 단어가 등장하는 하나의 위치를 모든 문장 부호를 무시하고 단어 단위로 표시한 것이다. 예를 들어 어떤 문서의 내용이 “Tom Loves Jane as Jane Loves Tom”이고, 이 문서에서 Tom과 Jane 만이 관심 있는 단어라면, 이 문서를 다음과 같이 표현할 수 있다. (Tom이 1번이고 Jane이 2번이다.) (1, 1) (2, 3) (2, 5) (1, 7) 좀더 복잡한 입력의 예는 다음과 같다. (1, 3) (2, 5) (1, 6) (1, 7) (1, 8) (3, 10) (1, 18) (1, 19) (3, 25) (2, 30) 이 예에서 다루는 단어는 3가지이며 (문서에 등장하는 단어들 중 특정한 3가지 이외는 무시함), 1번 단어는 문서 전체에서 3번째 단어, 6번째 단어, 7번째 단어, 8번째 단어, 18번째 단어, 19번째 단어로 6회 등장하며, 2번 단어는 5번째 단어, 30번째 단어로서 2회 등장한다는 의미이다. 입력은 x에 의해 정렬된 형태로 주어진다고 가정한다. 1번 단어는 2회, 2, 3번 단어는 1회 이상 등장하여야 하는 조건이 주어졌다고 하자. 이제, 이 문서에서 세 개의 단어가 각각 주어진 횟수 이상 나타나는 가장 작은 영역은 5번째부터 10번째 단어 사이임이 자명하고, 이 영역의 크기는 10-5+1=6으로 생각하는 것이 자연스러울 것이다. (18번째부터 30번째 단어까지의 영역이 고려중인 3개의 단어만을 보았을 때는 4개의 쌍만을 포함하므로 더 작다고 생각할 수도 있지만, 원래 문서에서 영역의 크기를 생각한다면 앞의 답 보다 더 큰 영역이다.) 방금 보인 대로, 위치 s 부터 t 까지를 포함하는 영역의 크기는 t – s + 1로 정의한다. 위와 같은 입력이 주어졌을 때, 모든 단어가 최소 주어진 횟수 이상 등장하는 가장 작은 영역의 크기를 찾는 알고리즘을 구현하라. 제한시간: 테스트 데이터는 10개이며, 전체 수행시간은 10초 이내. (시간 초과가 발생할 경우 이미 출력한 답들도 모두 무시되어 점수가 0점이 된다. 따라서, 최적의 솔루션을 찾지 못한 경우라서 시간 초과가 예상되는 입력은 오답을 출력하는 편이 나을 수 있다. 예를 들어 입력의 크기가 큰 경우는 시간초과가 발생한다고 예상이 가능하다.) [입력] 입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 C가 주어지고, 이후 차례로 C개 테스트 케이스가 주어진다 (1≤C≤20). 각 케이스의 첫째 줄에 쌍의 수 N(1,000,000이하)과 단어의 종류를 나타내는 자연수 K(1,000이하)가 주어진다. 각 단어는 1부터 K까지의 자연수로 표현된다. 이후 K 개의 줄에 각각의 단어가 등장해야 하는 최소 횟수가 단어 번호 순서대로 주어진다. 이후 N 개의 줄에 한 쌍을 나타내는 두 개의 자연수가 주어진다. 첫 수는 단어의 번호이고, 두 번째 수는 단어의 등장 위치이다. N개의 쌍들은 두 번째 수에 따라 정렬되어 주어진다. 위치를 나타내는 값은 5,000,000 이하이다. [출력] 각 테스트 케이스에 대해서 출력은 한 줄로 구성된다. 첫 번째 줄에 가장 작은 영역의 크기를 나타내는 하나의 자연수를 출력한다. 답이 없는 경우는 -1을 출력한다. [입출력 예] 입력 2 ← 총 2개의 테스트 케이스가 있다는 뜻 10 3 ← 1번 케이스의 시작줄 2 1 1 1 3 2 5 1 6 1 7 1 8 3 10 1 18 1 19 3 25 2 30 3 2 ← 2번 케이스의 시작줄 2 1 1 1 2 3 2 5 출력 6 -1