백준 2841번 외계인의 기타 연주-JAVA

📝문제

📝알고리즘

//첫째 줄에 음의 수 N과 한 줄에 있는 프렛의 수 P를 입력받음
//최소 손가락 움직임 min을 0으로 초기화
//P개의 줄을 관리할 스택 배열 생성
//음의 수 N만큼 다음을 반복
//줄번호 num과 프렛 번호 fret을 입력받음
//해당 줄의 스택을 가져와서
//현재 프렛보다 큰 값이 남아 있다면 모두 pop하고 pop할때마다 min++함
//같은 프렛이면 아무 일 없이 그냥 진행한 이후에
//새로운 프렛을 누르고 min++함
//min 출력

❌틀린 코드

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        Stack<Integer> stack= new Stack<>();
        int N=Integer.parseInt(st.nextToken());
        int P=Integer.parseInt(st.nextToken());
        int min=0;
        
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            int num=Integer.parseInt(st.nextToken());
            int fret=Integer.parseInt(st.nextToken());
            if(stack.isEmpty()||fret>stack.peek()){
                stack.push(fret);
                min++;
            }
            else{
                stack.pop();
                stack.push(fret);
                min+=2;
            }
        }
        System.out.print(min);
    }
}

📝틀린 이유

✅줄마다 독립적인 스택이 필요한데 모든 줄에 대해 하나의 스택만 사용함
✅stack.peek()보다 작은 값이 들어오면 이보다 큰 값을 모두 pop해야 하는데 pop을 한 번만 수행하고 다시 push함➡️여러 개의 프렛이 동시에 눌려 있는 상태를 고려하지 않음

📝수정한 코드

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        
        int N=Integer.parseInt(st.nextToken());
        int P=Integer.parseInt(st.nextToken());
        int min=0;
        
        Stack<Integer>[] stacks=new Stack[P+1];
        for(int i=1; i<=P;i++){
            stacks[i]=new Stack<>();
        }
        
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            int num=Integer.parseInt(st.nextToken());
            int fret=Integer.parseInt(st.nextToken());
            
            Stack<Integer> stack=stacks[num];
            
            while(!stack.isEmpty()&&stack.peek()>fret){
                stack.pop();
                min++;
            }
            
            if(!stack.isEmpty()&&stack.peek()==fret){
                continue;
            }
            stack.push(fret);
            min++;
        }
        System.out.print(min);
    }
}

📌기록하고 싶은 내용

✅StringTokenizer는 한 번 사용하면 내부 문자열이 소모됨