[BOJ] 2841. 외계인의 기타 연주(Stack).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

외계인 친구와 친해지고 싶어서 이 문제를 풀게 되었다.

기타를 연주하기 위해 음을 누르고 떼는 동작은 마치 Stack 자료구조와 유사한 것을 느낄 수 있다.

프렛을 누르는 동작은 Stack의 push()

프렛을 떼는 동작은 Stack의 pop() !

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer;   public class BOJ2842 {       static int N, P;          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()); // 프렛의 수         // 기타 줄 세팅         Stack<Integer>[] line = new Stack[7];         for (int i = 1; i <= 6; i++) {             line[i] = new Stack<>();         }         // 어떤 음을 쳐볼까?         int cnt = 0;         for (int i = 0; i < N; i++) {             st = new StringTokenizer(br.readLine());                          int a = Integer.parseInt(st.nextToken());             int b = Integer.parseInt(st.nextToken());                          // 프렛 누르기             if(line[a].isEmpty() || line[a].peek() < b) {                 // 이미 음을 누르고 있다면                 if(!line[a].isEmpty() && line[a].peek() == b) continue;                                  line[a].push(b);                 cnt++;                                  continue;             }                          // 프렛 떼기             while(!line[a].isEmpty() && line[a].peek() > b) {                 line[a].pop();                 cnt++;             }             // 이미 음을 누르고 있다면             if(!line[a].isEmpty() && line[a].peek() == b) continue;             // 새로 음을 눌러야 하면             line[a].push(b);             cnt++;         }                  System.out.println(cnt);       }   } Colored by Color Scripter

cs

#. Code_v2

최적화를 위해 Stack을 구현해보았다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer;   public class BOJ2842_v2 {       static int N, P;          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()); // 프렛의 수         // 기타 줄 세팅         int[][] line = new int[7][P];         int[] tops = new int[7];         for (int i = 1; i <= 6; i++) {             tops[i] = -1;         }                  // 어떤 음을 쳐볼까?         int cnt = 0;         for (int i = 0; i < N; i++) {             st = new StringTokenizer(br.readLine());                          int a = Integer.parseInt(st.nextToken());             int b = Integer.parseInt(st.nextToken());                          // 프렛 누르기             if(tops[a] == -1 || line[a][tops[a]] < b) {                 // 이미 음을 누르고 있다면                 if(tops[a] >= 0 && line[a][tops[a]] == b) continue;                                  line[a][++tops[a]] = b;                 cnt++;                                  continue;             }                          // 프렛 떼기             while(tops[a] >= 0 && line[a][tops[a]] > b) {                 tops[a]--;                 cnt++;             }             // 이미 음을 누르고 있다면             if(tops[a] >= 0 && line[a][tops[a]] == b) continue;             // 새로 음을 눌러야 하면             line[a][++tops[a]] = b;             cnt++;         }                  System.out.println(cnt);       }   } Colored by Color Scripter

cs