백준 2841 java : 큐, 스택

왜 큐, 스택 자료구조를 사용했는가?

사실 큐는 필요가 없었다. 순서대로 나오게 구현하면 배열도 상관없다. 대신 예외를 발생하지 않는 offer,peek, poll 메서드를 연습했다.

각 줄을 스택으로 만들어,

1. 해당하는 라인을 확인해서, 현재 누르고 있는 프랫이 눌러야 하는 프랫보다 높다면, 낮은 프랫이 나올때까지 스택에서 꺼내기
2. 누르고 있는 프랫이 눌러야 하는 프랫과 같다면 다음 순회로 통과
3. 프랫을 누를 수 있는 조건이 되면 해당하는 줄의 해당하는 프랫 누르고 스택에 넣기

을 반복해서 손가락이 움직인 횟수를 갱신한다.

import java.util.*;

public class BJ2841 {
    static class Melody{
        int lineNum;
        int fretNum;
    }

    static Scanner scanner = new Scanner(System.in);
    static int N, P;
    static Queue<Melody> melodyQueue = new LinkedList<>();

    public static void main(String[] args) {
        inputData();
        System.out.println(findAnswer());

        scanner.close();
    }

    public static void inputData(){
        int i;

        N = scanner.nextInt();
        P = scanner.nextInt();
        for(i = 0; i < N; i++){
            Melody melody = new Melody();

            melody.lineNum = scanner.nextInt();
            melody.fretNum = scanner.nextInt();
            melodyQueue.offer(melody);
        }
    }

    public static int findAnswer(){
        int answer = 0;
        int nextLine, nextFret;
        int i;

        Stack<Integer>[] guitar = new Stack[7];
        for (i = 1; i <= 6; i++) {
            guitar[i] = new Stack<>();
        }

        while(!melodyQueue.isEmpty()){
            nextLine = melodyQueue.peek().lineNum;
            nextFret = melodyQueue.peek().fretNum;
            melodyQueue.poll();

            System.out.println("눌러야 하는 줄 : " + nextLine + " 눌러야 하는 프랫 : " + nextFret);//디버그

            //해당 라인에 누르고 있는 프랫이 있고, 눌러야 하는 프랫이 가장 높은 누르고 있는 프랫보다 낮은 경우
            while (!guitar[nextLine].isEmpty() && guitar[nextLine].peek() > nextFret) {

                System.out.println(nextLine + "번 줄 손가락 땜 : " + guitar[nextLine].peek());//디버그

                guitar[nextLine].pop();//해당 라인에 앞으로 눌러야 하는 프랫보다 낮은 프랫이 나올 때까지 손가락 땜
                answer++;
            }

            if (!guitar[nextLine].isEmpty() && guitar[nextLine].peek() == nextFret) {//누르고 있는 프랫이 눌러야 하는 프랫이랑 동일하면 그대로 통과
                continue;
            }

            //해당 라인을 누르는 손이 없는 경우 또는 눌러야 하는 프랫이 가장 높은 누르고 있는 프랫보다 높은 경우 손가락 하나만 누르면 됨
            guitar[nextLine].push(nextFret);
            System.out.println(nextLine + "번 줄 손가락 누름 : " + guitar[nextLine].peek());//디버그
            answer++;
        }

        return answer;
    }
}