[BOJ] 백준 2841 외계인의 기타연주

[BOJ] 백준 2841 외계인의 기타연주

문제링크 : https://www.acmicpc.net/problem/2841


이 문제는 이전에 풀었던 "탑"(링크:https://gpfatp.blogspot.com/2018/09/boj-2493.html) 문제와
매우 비슷한 문제입니다.


스택을 사용해서 자기보다 작은 숫자가 나올때까지 POP()하는 개념을 이용해 풀었습니다.

소스코드 :

#include 
#include 
using namespace std;

int main() {
 int t, fret;
 cin >> t >> fret;
 cin.ignore();
 int cnt = 0;
 // 기타의 줄 개수는 6개이므로 스택 6개를 동적 메모리 할당.
 stack *st = new stack[6];
 for (int i = 0; i < t; i++) {
  int l, f;
  cin >> l >> f;
  cin.ignore();
  // 입력받은 기타줄 번호의 스택이 비어있으면
  if (st[l - 1].empty()) {
   st[l - 1].push(f);
   cnt++;
   continue;
  }
  // 눌러야 할 프랫과 이미 누르고 있는 프랫중 가장 높은것의 숫자가 같으면
  if (st[l - 1].top() == f) {
   // do nothing.
   continue;
  }
  // 눌러야 할 프랫보다 이미 누르고 있는 프랫중 가장 높은것의 숫자가 높다면
  else if (st[l - 1].top() < f) {
   st[l - 1].push(f);
   cnt++;
  }
  // 눌러야 할 프랫보다 이미 누르고 있는 프랫중 가장 높은것의 숫자가 작다면
  else {
   // POP()연산중 눌러야할 프랫과 같은 숫자가 나올 경우를 대비한 flag.
   bool flag = false;
   // 눌러야 할 프랫보다 작은 숫자가 나올때까지 누른 프랫을 POP().
   while (st[l - 1].top() > f) {
    st[l - 1].pop();
    cnt++;
    if (st[l-1] .empty()) break;
    // 만약 POP()한 뒤의 스택과 눌러야할 프랫이 같다면 아무것도 안눌러야 한다.
    if (st[l - 1].top() == f) {
     flag = true;
     break;
    }
   }
   // flag == true 면 아무것도 실시하지 않고 다시 반복문의 증감식으로 돌아감.
   if (flag) continue;
   st[l - 1].push(f);
   cnt++;
  }
 } // for end.
 cout << cnt << endl;
 //delete[] st;
}