[백준] 2841. 외계인의 기타 연주(Java)

문제

2841번: 외계인의 기타 연주

풀이

stack을 이용해서 푸는 문제

 

stack 배열을 만들고 N번을 순회하면서

1) stack[a]가 비어있지 않으며 stack[a].peek() 값이 b보다 크다면

조건이 만족하지 않을 때까지 반복하며 stack[a]를 pop해준다.(동작 수행을 한 것이기 때문에 ans ++)

2) stack[a]가 비어있거나 b값이 stack[a].peek()값보다 크다면

stack[a]에 b를 push해준다.(동작 수행을 한 것이기 때문에 ans ++)

코드

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 ans = 0;

        Stack<Integer>[] stack = new Stack[7];
        for(int i = 1 ; i <= 6 ; i ++)
            stack[i] = new Stack<>();

        for(int i = 0 ; i < N ; i ++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // 스택이 비어있지 않으며 stack의 마지막 값이 b보다 크다면
            while(!stack[a].isEmpty() && stack[a].peek() > b){
                stack[a].pop();
                ans++;
            }

            // 비어있거나 b가 stack의 마지막 값보다 크다면
            if(stack[a].isEmpty() || b > stack[a].peek()){
                stack[a].push(b);
                ans++;
            }
        }

        System.out.print(ans);
    }
}