문제
시간 제한 : 1초, 메모리 제한 : 256MB
상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.
보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.
멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.
예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로 7번 프렛을 누르고 줄을 튕기면 된다. 여기서 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다.
이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오.
입력
멜로디에 포함된 음의 수 N 프렛의 수 P
이후 N번만큼 줄의 번호와 프렛의 번호
출력
총 옮긴 횟수
풀이
누른 프렛의 값을 줄 별로 관리해야 하고, 이미 누르고 있는 프렛을 떼면 안 되므로 누르고 있는 프렛은 저장해두어야 한다. 그리고 제일 마지막에 누르고 있는 프렛과 비교하면 되므로 저장된 프렛들 중 조회한 값은 제일 최근 값(제일 큰 값)이다. stack을 사용하면 빠르게 조회, 삽입, 삭제가 가능하고, 후입선출(LIFO)이므로 제일 최근 값을 조회한다는 목적에도 알맞아 stack을 사용하기로 하였다!
생각한 플로우는 다음과 같다 :
size()가 0이면 일단 집어넣으며 result + 1
만약 .peek()을 한 것이 현재 값보다 작다면 스택에 집어넣고 result + 1
.peek()을 한 것이 현재 값보다 크다면 pop()을 하고 result + 1
.size == 0 이거나 .peek()한 게 작을 때까지 pop과 result + 1를 반복한다
이후 result 출력!
package baekjoon.src;
import java.io.*;
import java.util.*;
public class BJO2841 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int i;
// 줄 별로 관리해야하므로 줄 6개를 위한 스택 생성
Stack<Integer>[] guitar = new Stack[7];
for(i = 0; i<7; i++) {
guitar[i] = new Stack<Integer>();
}
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int P = Integer.parseInt(st.nextToken());
int result = 0;
for(i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
int currentString = Integer.parseInt(st.nextToken());
int currentFret = Integer.parseInt(st.nextToken());
// peek한 것이 currentFret보다 크거나 같은 경우 while문 진입
while(guitar[currentString].size() > 0 && guitar[currentString].peek() >= currentFret) {
// 밑에서 무조건 add를 하기 때문에 같다면 pop() 진행
// 밑에서 무조건 result++를 하기 때문에 result--를 한 번 해줌
if(guitar[currentString].peek() == currentFret) {
guitar[currentString].pop();
result--;
continue;
}
// 큰 경우 pop, result++;
guitar[currentString].pop();
result++;
}
// 사이즈가 0이거나 peek한 것이 currentFret보다 작은 경우 현재 값 추가, result++;
guitar[currentString].add(currentFret);
result++;
}
bw.write(result + "\n");
bw.flush();
bw.close();
br.close();
}
}
문제를 풀며
예제 위주 + 생각 난 반례 위주로 테스트를 해보고 제출하는데, guitar의 인덱스를 최대 6까지로 지정해서 에러가 발생했었다.. 더 꼼꼼해야 할 것 같다😅
그리고 .peek()한 값과 currentFret가 같을 때, .pop()과 .add()를 한 번씩 더 실행하게 되는 게 조금 비효율적으로 느껴진다. 코드를 가독성 좋고 깔끔하게 짜려고 해본 건데 비효율적 + 오히려 .add()가 되는 환경을 바로 알 수 없으므로 깔끔하게는 보이나 바로바로 이해가 안 되는 것 같기도 하다. 수정하는 게 나을 것 같다..!