문제번호	제목	난이도
2841	외계인의 기타 연주	실버 1

2841번 외계인의 기타 연주

해결코드:

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());
        Stack<Integer>[] stack = new Stack[n+1];
        for (int i = 0; i < n; i++) {
            stack[i] = new Stack<>();
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int line = Integer.parseInt(st.nextToken());
            int pret = Integer.parseInt(st.nextToken());
            if(stack[line].isEmpty()){
                stack[line].push(pret);
                count++;
            }else{
                if(stack[line].peek() < pret){
                    stack[line].push(pret);
                    count++;
                }else{

                    while (!stack[line].isEmpty() && stack[line].peek() > pret){
                        stack[line].pop();
                        count++;
                    }
                    if(!stack[line].isEmpty() && stack[line].peek() == pret){
                        continue;
                    }
                    stack[line].push(pret);
                    count++;
                }
            }
        }
        bw.write(count+"");
        br.close();
        bw.close();
    }

}

고민의 시간과 해결방법:

1. 각 줄별로 배열을 만들고, 이전에 누른 pret과 현재 누르려고 하는 pret을 비교하는 방식으로 해결하면 된다.
2. pret은 스택으로 해결하기로 생각하였고 선택한 자료구조 형태는 스택 배열이다
3. 배열의 크기는 line만큼 선언한 뒤, 각 스택 배열의 line인덱스마다 new Stack<>()으로 인스턴스를 생성하였다
4. 이제 입력으로 값을 받고 비교하는데, 만약 해당 스택 배열 line의 값이 비어있다면 해당 스택 배열에 push한다
5. 비어있지 않다면 비교를 해야한다. 만약 스택의 peek보다 현재 pret이 더 크다면 그냥 줄을 누르면 되므로 스택에 push하고 count++해준다
6. 그렇지 않다면, 작거나 같아질때까지 손가락을 떼어야하므로 while문을 돌려서 pop과 떼는 행위 count++를 진행한다
7. 이후 만약 peek와 pret이 같다면 추가 행위가 필요없으므로, continue하고 작다면 push한 뒤 count++해준다
8. 완성한 count를 출력한다.

문제 링크:

2841 - 외계인의 기타 연주