외계인의 기타 연주(BJ_2841)

1. 문제 링크

https://www.acmicpc.net/problem/2841

 

---

 

2. 나의 코드

메모리: 122288kb
시간: 576ms
코드 길이: 1421B
시간 복잡도 : O(N)
설명
- 6개의 스택을 생성하여 문제 해결

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class BJ_2841 {
    static int N, P, result;
    static Stack<Integer>[] stackArr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        stackArr = new Stack[7];

        for (int i = 1; i < 7; i++) {
            stackArr[i] = new Stack<>();
        }

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

            if (stackArr[rope].isEmpty()) {
                stackArr[rope].push(fret);
                result++;
                continue;
            }

            while (!stackArr[rope].isEmpty() && stackArr[rope].peek() > fret) {
                stackArr[rope].pop();
                result++;
            }

            if (!stackArr[rope].isEmpty() && stackArr[rope].peek() == fret) {
                continue;
            }

            stackArr[rope].push(fret);
            result++;

        }
        System.out.println(result);
    }
}

 

---

 

3. 정답 코드

// JAVA 11 , 메모리 : 14244KB, 시간 : 132ms

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int musicNum, fret = 0;
        int move = 0;
        int nowLine, nowFret;

        Stack<Integer>[] stack = new Stack[7];

        StringTokenizer st = new StringTokenizer(br.readLine());

        musicNum = Integer.parseInt(st.nextToken());
        fret = Integer.parseInt(st.nextToken());

        for (int x = 0; x <= 6; x++) {
            stack[x] = new Stack<Integer>();
        }

        for (int x = 0; x < musicNum; x++) {
            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++;
            }


        }

        bw.write(String.valueOf(move));
        bw.flush();


    }


}

 

---

 

4. 배운 점

- 오랜만에 다시 백준을 풀었다. 꾸준히 풀어야 겠다..

- 처음에는 배열 인덱스로 풀다가 PQ로 바꾸고 큐로 생각해보니 전부다 아닌거 같아서 스택으로 구현했다.