[알고리즘] 스택 문제 풀이

백준 2841

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

class Main{
    public static void main(String args[])throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int musicNum, fret = 0;
        int move = 0;
        int nowLine, nowFret; //현재 줄과 프렛 번호를 알기 위한 변수 선언

        Stack<Integer>[] stack = new Stack[7]; // 1~6번 줄 스택 배열생성
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        musicNum = Integer.parseInt(st.nextToken());
        fret = Integer.parseInt(st.nextToken());
		
        //스택 배열 각각 요소에 스택 선언
        for (int i = 1; i<7 ; i++) {
            stack[i] = new Stack<Integer>();
        }
	
        for (int i = 0; i < musicNum; i++) {
            st = new StringTokenizer(br.readLine());

            nowLine = Integer.parseInt(st.nextToken());
            nowFret = Integer.parseInt(st.nextToken());

            // 현재 프렛보다 크면 손 떼기
            while(!stack[nowLine].isEmpty() && stack[nowLine].peek() > nowFret ){
                stack[nowLine].pop();
                move++;
            }

            //  현재 줄 에서 잡은 프렛이 없거나 현재 줄에서 잡은 프렛이 현재 프렛보다 작을 경우 프렛을 새로 잡기
            if (stack[nowLine].isEmpty() || stack[nowLine].peek() < nowFret) {
                stack[nowLine].push(nowFret);
                move++;
            }
        }
        System.out.println(move);
    }
}

        
  

얻어갈 점:

• 핵심 키워드는 "특정 input이 들어왔을때 기존의 저장하고 있던 곳에서 하나씩 빼고, 넣고"=> stack 구조
• 여태 스택을 활용한 문제는 하나의 스택만 활용했는데 스택 배열을 생성하여 각각의 줄마다 할당해주는 idea + 해당 줄로 찾아가기 위한 현재의 줄 번호와 프렛 번호 저장해줄 변수 선언
• 원래 풀이는 .split() 함수를 사용해 공백을 기준으로 나눠줬는데 StringTokenizer를 사용하여 더 간편하게 풀이 가능
• 핵심 로직의 순서가 중요한데 원래 풀이는 현재 줄 에서 잡은 프렛이 없거나 현재 줄에서 잡은 프렛이 현재 프렛보다 작을 경우 프렛을 새로 잡기 조건을 먼저 걸고, 현재 프렛보다 크면 손 떼기 순서로 작성했었다. 그러나 해당 방식은 특정 프렛이 로직 순서상 손 떼기는 할 수 있지만 해당 프렛을 추가하지 못함 => 따라서 while문으로 현재 프렛보다 크면 손을 떼는 로직부터 시작하고 pop()시킨 후 다음 로직을 타야함. => 손 떼기 로직이 먼저 오다보니 스택이 비어있는지도 check 해야함