[백준(BOJ)] 2841 외계인의 기타 연주 - 스위프트 (Swift)

[Silver I] 외계인의 기타 연주 - 2841

문제 링크

성능 요약

메모리: 73016 KB, 시간: 612 ms

분류

자료 구조, 스택

제출 일자

2023년 12월 28일 10:50:30

문제 설명

상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.

보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.

멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.

예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로 7번 프렛을 누르고 줄을 튕기면 된다. 여기서 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다.

이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (1 ≤ N ≤ 500,000, 2 ≤ P ≤ 300,000)

다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수는 줄의 번호이고 두 번째 정수는 그 줄에서 눌러야 하는 프렛의 번호이다. 입력으로 주어진 음의 순서대로 기타를 연주해야 한다. 줄의 번호는 N보다 작거나 같은 자연수이고, 프렛의 번호도 P보다 작거나 같은 자연수이다.

출력

첫째 줄에 멜로디를 연주하는데 필요한 최소 손가락 움직임을 출력한다.

 

풀이

위 문제를 풀기 위해선 우선 줄마다 스택을 두고, 해당 줄이 들어왔을 때 스택을 조정하는 방식을 생각하였습니다.

그리하여 n개의 스택이 있는 배열을 생성하였습니다. 그리고 스택은 오름차순으로 정렬되기를 예상하였습니다.

 

그리고 스택에 값을 추가하는 상황과 값을 제거하는 상황을 분리하여 생각해보았습니다.

그리고 스택이 비어있지 않은데, 새로 들어오는 프렛보다 스택의 마지막 값이 더 큰 경우에 스택의 값을 계속해서 제거해줍니다.

만약 스택이 비어있거나 새로 들어오는 프렛이 다른 값인 경우, 스택에 값을 추가하면서 손가락 움직임을 하나 추가하면 될 것이라 생각하였습니다.

다른 값인 경우로 설정한 이유는 값이 다르다면 새로 들어오는 값이 더 큼 (더 큰 경우는 값을 제거해주었기 때문입니다.)

 

이를 식으로 표현하면 다음과 같습니다.

let np = readLine()!.split(separator: " ").map { Int($0)! }
let (n, p) = (np[0], np[1])
var stack: [[Int]] = Array(repeating: [Int](), count: n + 1)
var ans = 0

for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map { Int($0) }
    let (str, fret) = (input[0]!, input[1]!)

    while !stack[str].isEmpty && stack[str].last! > fret {
        stack[str].removeLast()
        ans += 1
    }

    if stack[str].isEmpty || stack[str].last! != fret {   // 만약 값이 다르다면 새로 들어오는 값이 더 큼
        stack[str].append(fret)
        ans += 1
    }
}
print(ans)