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

---

0. 문제

 

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

1. 아이디어

 

1) 누르는 줄과 프렛을 따로 배열에 보관한다.

 

2) 다른 줄번호끼리는 카운트에 서로 영향을 주지 않기 때문에 1번부터 6번 줄까지 각각 카운트해서 합한다! (각각 스택)

(예를 들어, 1번줄 3번 프렛을 누르고 있을 때, 3번 줄 2번 프렛을 누르든 5번 줄 1번 프렛을 누르든 영향을 주지 않음)

 

3) 해당 줄의 스택이 비어있을 땐 바로 PUSH

 

4) 해당 줄의 스택이 비어있지않고 입력받은 프렛 값이 스택의 TOP() 보다 크다면 PUSH

 

5) 해당 줄의 스택이 비어있지않고 입력받은 프렛 값이 스택의 TOP()과 같다면 스택과 최종 카운트에는 영향 없다.

 

6) 해당 줄의 스택이 비어있지 않고 입력받은 프렛 값이 스택의 TOP() 보다 작다면 입력값이 TOP()보다 같거나 커질 때까지 POP해주고

이후 스택의 TOP()보다 입력값이 더 클 때만 다시 PUSH 해준다.

 

2. 소스코드

 

#include <iostream>
#include <stack>
int main()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    int N, P, result = 0;
    std::cin >> N >> P;
    int* pitch = new int[N]; // 몇번째 줄을 누르는지만 저장 (N개)
    int* fret = new int[N]; // 몇번째 프렛을 누르는지만 저장 (N개)
 
    for (int i = 0; i < N; i++)
    {
        int p, f;
        std::cin >> p >> f;
        pitch[i] = p; //p는 1이상 6이하의 값
        fret[i] = f;
    } //줄의 번호와 프렛의 번호 따로 입력!
 
    for (int num = 1; num <= 6; num++) // 줄번호별로 따로 카운트
    {
        std::stack<int> st;
        for (int i = 0; i < N; i++)
        {
            if (pitch[i] == num) //1번줄부터 6번줄까지
            {
                if (!st.empty() && fret[i] > st.top())
                {
                    st.push(fret[i]);
                    result++;
                }
                else if (!st.empty() && fret[i] <= st.top())
                {
                    while (fret[i] < st.top())
                    {
                        st.pop();
                        result++;
                        if (st.empty()) break;
 
                    }
                    if (!st.empty() && fret[i] > st.top())
                    {
                        st.push(fret[i]);
                        result++;
                    }
                    else if (st.empty())
                    {
                        st.push(fret[i]);
                        result++;
                    }
                }
                else if (st.empty())
                {
                    st.push(fret[i]);
                    result++;
                }
            }
        }
    }
    std::cout << result;
}

 

3. 결과

 

4. 피드백

 

• POP연산뒤에 스택이 비어버릴 수 있다는 걸 생각 못하고 계속 오류가 났다..
• 줄과 프렛의 배열을 따로 두는거보다 STL중에 pair를 이용해서 스택을 구성했으면 더 간단할듯?
• std::ios_base::sync_with_stdio(0);와 std::cin.tie(0)을 적용해주니까 속도가 많이 향상됐다.

---

TO DO LIST: STL pair

---