백준 2841 - 외계인의 기타 연주
Updated:
Java
2841 번 - 외계인의 기타 연주
문제
상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.
보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.
멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.
예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로 7번 프렛을 누르고 줄을 튕기면 된다. 여기서 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다.
이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오.
접근 방법
총 6개의 기타 줄을 ArrayList로, 그 기타 줄의 프렛을 Stack으로 구현한다.
입력에 따라 음을 스택에 저장할지, 스택에서 뺄지 결정한다.
음을 스택에 저장하거나 제거 할때, 한번 손가락이 움직인 것으로 생각하여 개수를 센다.
구현
ArrayList의 타입을 Stack으로 주어 총 6개의 Stack을 생성한다.
각 줄을 ArrayList의 인덱스로 접근하여 stack으로 프렛을 구현한다.
코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String []args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int n = stoi(st.nextToken());
int p = stoi(st.nextToken());
int result = 0;
ArrayList<Stack<Integer>> line = new ArrayList<Stack<Integer>>();
for(int i = 0; i <= 6; i++) { // 6개의 기타 줄을 ArrayList, 각 기타 줄의 플랫을 stack으로 생성
line.add(new Stack<Integer>());
}
while(n-- != 0) {
st = new StringTokenizer(br.readLine());
int l = stoi(st.nextToken());
int num = stoi(st.nextToken());
if(line.get(l).empty() || line.get(l).peek() < num) { // 해당하는 줄에 손가락이 없거나, 기존에 있던 음보다 높으면 추가한다.
line.get(l).push(num);
result++;
}
else if(line.get(l).peek() == num) { // 만약 같은 음이면, 누른 상태로 음을 재생 할 수 있으므로, continue한다.
continue;
}
else {
while(!line.get(l).empty() && line.get(l).peek() > num) { // 현재 스택에서 재생할 음까지 pop을한다
line.get(l).pop();
result++;
}
if(!line.get(l).empty() && line.get(l).peek() == num) { // 만약 같은 음에 도달하면 음을 바로 재생하면 되므로 continue 한다.
continue;
}
line.get(l).push(num); // 중복되는 음이 없고, 현재 음보다 높은 음들을 제거하면 음을 stack에 넣고 연주한다.
result++;
}
}
System.out.println(result);
br.close();
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
총평
난이도
⭐⭐⭐★★
후기
처음 접근은 쉬웠지만, 다양한 조건을 부여하는데 어려움을 느낀 문제이다.
