[C++] 백준 2841번: 외계인의 기타 연주

문제

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

 

풀이

 

 

2차원 배열로 풀어도 되지만 top index를 데리고 다니기 싫어서 stack으로 풀었다.

지금 누르고 있는 줄의 프렛을 저장하는 변수를 생성했다

자료구조를 시각화 하면 대충 아래처럼 생각하면 된다 

 

stack[줄] = [프렛 | 프렛 | ... ] 

 

 

• 누르려는 음  <  stack[줄]의 가장 높은 프렛 
  • 가장 높은 프렛이 누르려는 음보다 작을 때까지 손가락을 떼야 한다. 
• 누르려는 음 == stack[줄]의 가장 높은 프렛 
  • 손가락을 움직이지 않는다.
• 누르려는 음  >  stack[줄]의 가장 높은 프렛 
  • 누르려는 음을 하나 더 누르면 된다. 

 

 

+ 스택이 비었는지 체크하는 부분을 쉽게 처리 하는 방법을 알았다.

https://ryute.tistory.com/3

위 블로그에서 얻은 아이디어인데 stack에 0을 집어 넣어줘서 조건문을 줄일 수 있었다. 

 

소스

#include <iostream>
#include <stack>

int main()
{
    std::stack<int> stk[7]; // jul[fret]
    int N =0, P =0;
    int j =0, fret =0;
    int result = 0;

    std::cin >> N >> P;
    //here!
	for(int i=0; i<7; ++i)
	{
		stk[i].push(0);
	}
	
    for(int i =0; i<N; ++i)
    {
        std::cin >> j >> fret;

        while(stk[j].top() > fret)
        {
            stk[j].pop();
            ++result;
        }
        if(stk[j].top() != fret)
        {
            stk[j].push(fret);
            ++result;
        }
    }
    

    std::cout << result;
    return 0;
}