[알고리즘] Swift -백준 #2841(외계인의 기타 연주)

문제링크

https://www.acmicpc.net/problem/2841

2841번: 외계인의 기타 연주

 

문제

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

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

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

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

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

입력

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

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

출력

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

 

---

분석

외계인은 손이 수십억개를 가지고 있다.

기타는 6개의 줄이 있다. 기타의 번호 1번~6번

각 줄은 p개의 플렛으로 나누어져 있다. 플렛의 번호 1번~p번

여러 줄의 플렛을 여러 개 누르고 있다면 가장 높은 플렛의 음이 발생한다. (?)

 

3번 줄의 5번 플렛을 누르고 있을 때

7번 플렛의 음을 연주하려면 5번 플렛을 누르는 손을 떼지않고 다른 손가락으로 7번을 누르면 된다.

하지만 2번 플렛의 음을 연주하려면 5번과 7번을 뗀 다음에 2번을 눌러야 한다.

손가락을 떼거나 누르는 동작을 한 번 할 때마다 손가락을 한 번 움직인다고 한다.

손가락이 가장 적게 움직이는 횟수를 구하시오.

 

풀이 과정

n = 음의 수

p = 플렛의 수

n개의 줄에는 줄의 번호와 플렛의 번호가 주어진다.

음별로 큐를 생성한다.

플렛이 낮은 순서대로 큐에 넣고 제일 높은 플렛과 비교하여 추가하거나 삭제한다.

 

풀이

let input = readLine()!.split(separator: " ").map{ Int($0)!}
var arr = [[Int]](repeating: [Int](), count: input[0])

var count = 0
for _ in 0..<input[0] {
    let guitar = readLine()!.split(separator: " ").map{ Int($0)!}

    while true {
        if arr[guitar[0]].last == guitar[1] {
            //상관없음 그냥 넘어가기
            break
        } else if arr[guitar[0]].last ?? 0 > guitar[1] {
            //마지막 요소보다 작기때문에 삭제하기
            arr[guitar[0]].removeLast()
            count += 1
            continue
        } else {
            //마지막 요소보다 크니까 추가하기
            arr[guitar[0]].append(guitar[1])
            count += 1
            break
        }
    }
}

print(count)

 

결과

 

 

알게된 점

• 문제분석을 빠르게 하면 빠르게 풀 수 있었던 문제다.
• repeating 과 같은 문법을 알고 있다면 빠르게 접근가능하다.

https://nlestory.tistory.com/132

[Swift] 같은 원소 반복한 배열 만들기 -repeating , count