문제
기타의 6줄에서 음을 연주할 때, 각 줄의 프렛을 누르거나 떼는 최소 횟수를 구하라. 높은 프렛을 누르려면 낮은 프렛이 눌려있어야 하고, 낮은 프렛을 누르려면 높은 프렛을 모두 떼야 한다.
입력
첫째 줄에 N(음의 수), P(프렛 수), 이후 N줄에 줄 번호와 프렛 번호가 주어진다.
출력
손가락을 움직이는 최소 횟수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 15 2 8 2 10 2 12 2 10 2 5 | 9 |
풀이
각 줄마다 스택을 관리하여 현재 프렛보다 높은 프렛을 pop하고, 필요한 프렛을 push한다.
- 6개의 스택을 줄별로 관리한다
- 현재 프렛보다 높은 프렛이 스택 top에 있으면 pop(손가락 떼기)한다
- 스택 top과 같으면 추가 동작 없음
- 스택이 비었거나 top보다 높은 프렛이면 push(손가락 누르기)한다
- 각 push/pop마다 카운트를 증가시킨다
핵심 아이디어: 각 줄의 프렛 상태를 스택으로 모델링하면, 높은 프렛부터 순서대로 떼고 누르는 동작을 자연스럽게 표현할 수 있다.
코드
package day649;
import java.io.*;
import java.util.*;
public class Day636BOJ2841외계인의기타연주 {
static int N, P, ans;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input;
input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
P = Integer.parseInt(input[1]);
Stack<Integer>[] stack = new Stack[7];
for (int i = 1; i < 7; i++) {
stack[i] = new Stack<Integer>();
}
for (int i = 0; i < N; i++) {
input = br.readLine().split(" ");
int line = Integer.parseInt(input[0]);
int fret = Integer.parseInt(input[1]);
while (!stack[line].isEmpty()) {
if (stack[line].peek() < fret) {
stack[line].push(fret);
} else if (stack[line].peek() > fret) {
stack[line].pop();
} else {
break;
}
ans += 1;
}
if (stack[line].isEmpty()) {
stack[line].push(fret);
ans += 1;
}
}
System.out.println(ans);
}
}복잡도
- 시간: O(N)
- 공간: O(N)