[백준BOJ] 2841번 외계인의 기타 연주.java

 

백준 저지에서 외계인의 기타 연주를 자바를 통해 풀어 보았다. 

 

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

2841번: 외계인의 기타 연주

2841번 외계인의 기타 연주.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

2841번 외계인의 기타 연주

문제

상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.
보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.
멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.
예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로 7번 프렛을 누르고 줄을 튕기면 된다. 여기서 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다.
이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오.

설명

총 6개의 줄이 있으며 각 줄을 또 여러개의 프렛으로 나뉜다. 같은 줄에서 더 높은 프렛을 연주하려면 높은 프렛을 누르기만 하면 되지만 낮은 프렛을 연주하려면 해당 프렛보다 높은 프렛이 없어야 하므로 높은 프렛이 있다면 손을 떼야한다. 손을 누르거나 떼면 손가락을 한 번 움직인 것이다.

 

1번 줄에서 1번 프렛을 누르고 있다고 가정한다. 2번 프렛을 연주한다면 2번 프렛을 누르면 된다. 그러나 다시 1번 프렛을 연주한다고 하면 2번 프렛을 떼야한다. 1번 프렛은 이미 눌려 있으므로 추가로 움직이지 않는다.

 

각 줄에 대해 스택을 선언했다. 각 스택에는 눌러져있는 프렛이 순서대로 들어간다. 

 

만약 스택이 비어있다면 프렛을 바로 넣는다. 즉 프렛을 손가락으로 누른 것이다.

 

만약 스택의 top에 있는 프렛보다 높은 프렛을 연주한다면 이 역시 바로 스택에 넣는다. 더 높은 프렛을 손가락으로 누른 것이다.

 

만약 위 두가지 경우가 다 아니라면 누르고자 하는 프렛보다 낮은 프렛이 나올 때까지 스택으로부터 pop한다. pop하는 과정에서 스택이 비거나 누르고자 하는 프렛과 같은 프렛이 나오면 pop을 멈추고 스택에 push하거나 종료한다.

 

위 3가지 상황에서 스택을 넣거나 빼는 경우마다 손가락을 움직인 것이므로 카운트해준다.

코드

//2841번 외계인의 기타 연주.java
package week6;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class 외계인의_기타_연주_2841 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    static class guitar{
    	int line;
    	int num;
    	guitar(int line, int num){
    		this.line=line;
    		this.num=num;
    	}
    }
    static class s{
    	Stack<guitar> g = new Stack<guitar>();
    }
    public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());
		
		s[] g = new s[N+1];
		for(int i=1;i<=N;i++) {
			g[i] = new s();
		}
		int count=0;
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int line = Integer.parseInt(st.nextToken());
	    	int num = Integer.parseInt(st.nextToken());
	    	guitar now = new guitar(line, num);
	    	if(g[line].g.isEmpty()) {
	    		g[line].g.add(now);
	    		count++;
	    	}
	    	else if(g[line].g.peek().num<now.num) {
	    		g[line].g.add(now);
	    		count++;
	    	}
	    	else {
	    		while(!g[line].g.isEmpty()&&g[line].g.peek().num>now.num) {
	    			g[line].g.pop();
	    			count++;
	    		}
	    		if(!g[line].g.isEmpty()&&g[line].g.peek().num<now.num) {
	    			g[line].g.add(now);
	    			count++;
	    		}
	    		else if(g[line].g.isEmpty()){
	    			g[line].g.add(now);
	    			count++;
	    		}
	    	}
		}
		System.out.println(count);
	}
}