[알고리즘/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
        }
    }
}