[알고리즘/Swift] 0118 지금 무슨 노래 듣고 있어요?2

문제

현진이는 길거리를 걸을 때 에어팟으로 노래를 듣는다. 현진이는 자신만의 플레이 리스트가 있기 때문에 집을 나설 때 마다 플레이 리스트의 노래를 순서대로 이어서 듣고, 모든 플레이 리스트를 들었다면 처음부터 다시 반복 재생해서 듣는다.
현진이의 플레이 리스트는 N 개의 곡으로 이루어져 있다. 각각의 곡의 길이(초)를 B[1], B[2], … , B[N] 이라고 하자. 현진이는 집을 나선지 1 초가 지난 시점부터 B[1] 초까지 1 번째 노래를 듣고, B[1] + 1 초부터 B[1] + B[2] 초까지 2 번째 노래를 듣는 식으로 나머지 모든 노래를 듣는다.
예를 들어 현진이의 플레이 리스트에 있는 3 개의 곡의 길이가 각각 3, 1, 2 라고 하자. 현진이가 집을 나선지 1 초부터 3 초까지는 첫 번째 노래를 듣는다. 그리고 4 초부터 4 초까지는 두 번째 노래를 듣고, 5 초부터 6 초까지는 세 번째 노래를 듣고 7 초 부터는 플레이리스트의 처음으로 돌아가서 첫 번째 노래를 7 초부터 9초 까지 듣고 이를 계속 반복한다.
현진이는 길거리를 걷다가 지금 무슨 노래 듣고 있어요? 라는 질문을 자꾸만 받는다. 친절한 현진이는 그럴 때마다 자신이 듣고 있는 노래의 이름을 알려준다. M 개의 질문이 주어질 때, 현진이가 뭐라고 대답할 지 맞춰보자!

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10) 이 주어진다.
둘째 줄부터 N 개의 줄에 A[1], A[2], … , A[N] 이 주어진다. A[i] (1 ≤ i ≤ N) 은 현진이의 플레이 리스트에서 i 번째 곡의 이름을 의미한다. A[i] 는 알파벳 대소문자 혹은 공백으로 이루어진 길이 20 이하의 문자열이다. 노래 이름의 처음이나 끝에 공백이 들어간 경우는 없다.
그 다음 줄부터 N 개의 줄에 B[1], B[2], … , B[N] 이 주어진다. B[i] (1 ≤ B[i] ≤ 300) 은 현진이의 플레이 리스트에서 i 번째 노래의 길이가 몇 초인지를 의미한다.
그 다음 줄에 정수 M (1 ≤ M ≤ 10 000) 이 주어진다.
그 다음 줄부터 M 개의 줄에 Q[1], Q[2], … , Q[M] (1 ≤ Q[i] ≤ 10 000) 이 주어진다. 현진이는 집을 나선지 Q[i] 초가 지날 때 마다 i 번째 질문을 받는다. Q 는 오름차순으로 정렬되어 있다.

출력

M 개의 줄에 걸쳐서 i 번째 질문에 대한 대답을 출력한다. 즉, 현진이가 집에서 나선지 Q[1], Q[2], … , Q[M] 초가 지났을 때 현진이가 듣고 있는 노래의 제목을 한 줄에 하나씩 출력한다.

풀이

Dynamic Programming

이전 항들의 값을 참조하여 값을 넣는 Dynamic Programming 방식을 사용하여 노래의 길이가 입력될 때 마다 배열 B에 i번째 노래가 끝나는 시간을 넣어주었다

index 1번값부터 i-1번째 항의 값 + 입력받은 노래의 길이

for i in 0...N-1{
  if i == 0 {
      B.append(Int(readLine()!)!)
  } else{
      B.append(B[i-1]+Int(readLine()!)!)
  }
}
// 5개의 노래의 길이가 각각 180, 178, 179, 185, 176 이라면 DP(B) = [180, 358, 537, 722, 898] (각 노래들이 끝나는 시간을 넣어줌)

그런 듣고 있는 노래를 질문 받을 때마다 아까 만들어놓은 DP 배열(Array B)의 원소들에 접근하면서 질문 받은 시간과 노래가 끝나는 시간을 비교하여 대답한다
For문을 통해 DP 배열(Array B)내에 있는 노래 원소에 하나씩 접근하면서 질문을 받은 시간이 해당 노래가 끝나는 시간보다 클 경우 continue, 작거나 같을 경우 대답을 하고 break를 통해 빠져나왔다
```
for i in 0...N-1{
      if B[i] < q{
          continue
      }else{
          print(A[i])
          break
      }
  }
```
가장 신경 써줘야 하는 부분은 플레이리스트에 있는 노래가 끝나면 다시 첫번째 노래 1초부터 시작하도록 해야하는 것이다
- 새로운 변수를 놓아서
- 플레이리스트가 끝나기 전에 질문을 받으면 상관 안쓰고
- 아닐 경우 질문받은 시간을 총 플레이리스트 시간으로 나눈 나머지로 해당 배열(Array B)에 접근한다
- 만약 배열(Array B)이 [180, 358, 537, 722, 898] 이렇게 구성되어있다면 899초에 질문을 받을 경우 총 플레이리스트 시간인 898으로 나눈 나머지 1로 간주하여 배열(Array B)에 접근한다

하지만 이렇게 코드를 짜면 플레이리스트 마지막 곡에서 q = 0이 되어 예외가 발생한다 -> else if 구문으로 문제 q = 0 이 될 경우 마지막 노래로 처리를 해주었다

if Q <= B[B.endIndex-1] {
        q = Q
    }else if Q % B[B.endIndex-1] == 0 {
        q = B[B.endIndex-1]
    }else{
        q = (Q % B[B.endIndex-1])
    }

코드

import Foundation

let N = Int(readLine()!)!
var A : [String] = [String]()
var B : [Int] = [Int]()
for _ in 1...N{
    A.append(readLine()!)
}

// 배열 B dp로 만들어주기
for i in 0...N-1{
    if i == 0 {
        B.append(Int(readLine()!)!)
    } else{
        B.append(B[i-1]+Int(readLine()!)!)
    }
}

let M = Int(readLine()!)!
for i in 1...M {
    let Q = Int(readLine()!)!
    var q = 0
    // 입력받은 시간들을 연산들을 통해 dp 배열내의 원소에 접근하도록 하였다
    // 마지막 노래가 끝나면 다시 첫번째 노래로 돌아가기 때문에 나머지를 활용하였다
    if Q <= B[B.endIndex-1] {
        q = Q
    }else if Q % B[B.endIndex-1] == 0 {
        q = B[B.endIndex-1]
    }else{
        q = (Q % B[B.endIndex-1])
    }
    for i in 0...N-1{
        if B[i] < q{
            continue
        }else{
            print(A[i])
            break
        }
    }
}