백준 27504 - 상대음감의 노래찾기

문제 링크 : https://www.acmicpc.net/problem/27504

 

문제

상대음감은 음을 절대적인 높이로 구분하는 것이 아닌 어떤 음과의 상대적인 높이로 음을 인식하는 능력을 말한다. 상대음감은 절대음감에 비해 불리한 점이 있지만, 노래를 찾을 때 어렴풋한 멜로디 만으로도 노래를 찾을 수 있다는 장점이 있다.

기령이는 이러한 점에서 착안하여 상대음감의 노래찾기 서비스를 만들려고 한다. 노래찾기 서비스는 데이터베이스에 노래의 음 데이터를 갖고 있으며 사용자가 멜로디를 입력했을 때 그 멜로디가 데이터베이스의 노래에 포함되어 있으면 해당 노래를 안내해 주는 서비스이다. 상대음감의 노래찾기 서비스는 상대적인 멜로디가 포함되어 있어도 일치하는 것으로 판단해 노래를 안내해준다. 즉, 찾으려는 멜로디가 a1, a2, ... aL 일때, 임의의 정수 x에 대하여 a1 + x, a2 + x, ... aL + x 를 포함하면 일치하는 것으로 판단한다.

예를 들어 사용자가 "1 2 1 2"의 멜로디를 입력했을 때, "3 4 3 4 5 5"라는 노래에는 이러한 멜로디가 포함되어 있으며 따라서 해당 노래를 안내해줄 것이다.

상대음감의 노래찾기 서비스를 구현해보자.

입력

첫째 줄에 데이터베이스에 존재하는 노래의 수 N이 주어진다. (1 ≤ N ≤ 1 000)

이후 N개의 줄에 걸쳐 i (1 ≤ i ≤ N)번 노래의 길이 K_i(2 ≤ K_i ≤ 100 000), 음 데이터 a1, a2, ... aK_i가 공백으로 구분되어 주어진다. 단, 모든 K_i의 합은 1 000 000을 넘기지 않는다.

다음 줄에 찾으려는 멜로디의 길이 L가 주어진다.(2 ≤ L ≤ 10 000) 그 다음 줄에 길이가 L인 멜로디 데이터 b1, b2, ... bL가 주어진다.

데이터의 모든 값은 1보다 크거나 같고 10 000보다 작거나 같다.

출력

찾으려는 멜로디 데이터가 존재하는 노래의 번호를 공백으로 구분하여 오름차순으로 출력한다. 존재하지 않을 경우 -1을 출력한다.

풀이 과정

https://readytojoin.tistory.com/entry/KMP-%EB%AC%B8%EC%9E%90%EC%97%B4-%EB%A7%A4%EC%B9%AD-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

KMP - 문자열 매칭 알고리즘

 

찾고자 하는 멜로디는 특정 수를 더해도 상관없으므로, 편차 변화를 통해 찾는다. 찾고자 하는 멜로디와 노래들을 전부 편차 수열화 시키면 1 2 1 2 와 3 4 3 4 모두 1 -1 1 로 만들어져 공통점을 얻어낼 수 있다. 노래와 멜로디 길이가 기므로 KMP 알고리즘을 사용해 찾는다.

# 27504. 상대음감의 노래찾기 ( PLATINUM 4 )
import sys
input = sys.stdin.readline

n = int(input().rstrip())
data = []
for _ in range(n):
  arr = list(map(int, input().rstrip().split()))
  go = []
  for i in range(1, arr[0]):
    go.append(arr[i+1] - arr[i])
  data.append(go)

l = int(input().rstrip())
now = list(map(int, input().rstrip().split()))
now_find = []
for i in range(l - 1):
  now_find.append(now[i+1] - now[i])

table = [0 for _ in range(l - 1)]
i = 0
for j in range(1, l - 1):
  while i > 0 and now_find[i] != now_find[j]:
    i = table[i - 1]

  if now_find[i] == now_find[j]:
    i += 1
    table[j] = i

res = []
for nidx in range(n):
  i = 0
  for j in range(len(data[nidx])):
    while i > 0 and now_find[i] != data[nidx][j]:
      i = table[i - 1]

    if now_find[i] == data[nidx][j]:
      i += 1
      if i == len(now_find):
        res.append(nidx + 1)
        break

if res: print(' '.join(map(str, res)))
else: print(-1)