[Baekjoon] 외계인의 기타연주

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

설명 : 6개의 기타 줄이 있고, P개의 프렛수가 주어진다. 

N개의 경우에 대해 줄의 번호와 프렛 번호가 주어질 때 최소 손가락의 움직임을 출력하는 문제이다.

풀이 :

1번줄의 3번을 누르고 있다가 5번을 누르면 5번음이 연주가 된다. 단, 이때 2번음을 연주하고자 한다면, 누른 5번음과 3번음을 때야한다.

한마디로 더 낮은 음을 연주하기 위해서는 그보다 높은 음을 떼야한다. -> LIFO구조의 스택을 이용

코드 :

 
package feb17.alien;
 
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
 
public class Main {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        Scanner sc = new Scanner(System.in);
        int N, P;
        int cnt = 0;
        
        N = sc.nextInt();
        P = sc.nextInt();
 
        List<Stack<Integer>> list = new ArrayList<Stack<Integer>>();
        
        for(int i = 0; i < 6; i++)
            list.add(new Stack<Integer>());
        
        for(int i = 0; i < N; i++){
            
            int num = sc.nextInt() - 1;
            int fret = sc.nextInt();
                
            Stack<Integer> s = list.get(num);
            
            if(s.isEmpty()){
                list.get(num).push(fret);
                cnt++;
                continue;
            }
            
            int s_fret = s.peek();
            
            if(s_fret < fret){
                list.get(num).push(fret);
                cnt++;
            }
            else if(s_fret > fret){
                
                boolean flag = false;
                while(!list.get(num).isEmpty()){
                    
                    int f = list.get(num).peek();
                    
                    if(f < fret){
                        list.get(num).push(fret);
                        cnt++;
                        break;
                    }
                    else if(f > fret){
                        list.get(num).pop();
                        cnt++;
                        if(list.get(num).isEmpty())
                            flag = true;
                    }
                    else {
                        break;
                    }
                }
                if(flag){
                    list.get(num).push(fret);
                    cnt++;
                }
                    
            }
            
        }
        
        System.out.println(cnt);
    }
 
}