[2841] 외계인의 기타 연주

구분

• 자료구조
• 스택

 

문제

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

2841번: 외계인의 기타 연주

 

풀이

1. 서로 다른 줄 끼리는 영향이 가지 않는다 -> 각 line별 fret을 스택으로 나누어 분리한다.

2. 기타는 줄이 6번 까지 존재 -> vector<stack<int>> guitar(7) ; // 0번라인은 쓰지않음

 

now : 지금 연주하려는 음 

stack : 해당 라인 스택에 존재하는 프랫 

 

now == stack : 아무것도 안함 

now > stack : 지금 연주하려는 음을 눌러줘야함 (ans++ / stack[line] push )

now < stacl : now가 더 크거나 같아질때까지 pop 

 

 

코드

//2 8    8push
//2 10  10push
//2 12  12push
//2 10  12pop
//2 5   10pop 8 pop 5 push

// 다른 줄 끼리는 영향안감 -> 어쩌피 거기 팅길거아님
//1 5   1-5push
//2 3   2-3push
//2 5   2-5push
//2 7   2-7push
//2 4   2-4push 2-5pop 2-7pop
//1 5
//1 3   1-5pop 1-3push

/*
 * 샘플코드 참고 -> 생각한 방법은 맞았는데
 * 1. 기타의 줄수가 최대 6개라는 사실을 캐치못함
 * 2. 알고리즘을 구현하는 방식이 너무 정리되지 않게 짜여짐
 * */

#include <iostream>
#include <vector>
#include <stack>

using namespace std;
vector<pair<int, int>> v;

vector<stack<int>> s(7);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int N, P; //음의 수 , 프렛의 수
    stack<int> stack;

    cin >> N >> P;

    v.assign(N, {0, 0});


    int l, p;//줄 번호, 프렛번호


    for (int i = 0; i < N; i++) {
        cin >> l >> p;
        v[i] = {l, p};


    }


    int ans = 0; //맨 처음 연주
    int line, fret;

    for (int i = 0; i < N; i++) {

        //현 입력
        line = v[i].first;
        fret = v[i].second;


        if (s[line].empty()) { //해당 줄 연주가 없음
            ans++;
            s[line].push(fret);
        } else {//s[line]스택에 뭔가 있음(이전 연주가 존재)
            if (s[line].top() > fret) {
                while (!s[line].empty() && s[line].top() > fret) {
                    s[line].pop();
                    ans++;
                }
                //여기서
                // 비었으면 -> 그냥 넣기
                // 같으면 -> 아무것도 x
                // 더커졌으면 -> 그냥 넣기
                if (s[line].empty()) {
                    s[line].push(fret);
                    ans++;
                } else {
                    if (s[line].top() == fret) continue;
                    s[line].push(fret);
                    ans++;
                }
            } else if (s[line].top() < fret) {
                ans++;
                s[line].push(fret);
            }
            //같은 경우는 아무것도 안해도됨
        }

    }

    cout << ans;


}

 

 

 뻘짓 

기타 줄이 6줄까지 인 것을 몰라서, stack을 많이두어 메모리 초과가 났었음 

 

 

 

가독성 개선

겹치는 부분을 합쳐준다. 이때는 수행 내용은 똑같지만, 선행조건이 있을 수 있으므로, 순서에 주의해야한다.

겹치는 부분을 뺴면,

s[line].empty() == true || s[line].top()<fret  -> 답++ / line에 push

s[line].top() > fret -> 답++ / pop

인데, 주의할점은 아래 부분이 먼저 수행되는것을 조건으로 두어야 초록색 네모 4가지를 합칠 수 있다.

따라서 2.가 먼저 수행되어야하고, 이가 먼저수행되려면 s[line].empty() == false조건을 추가해야 먼저 실행시킬 수 있다. 

 

또한, 2가 먼저 실행될 경우 s[line].top()인 경우는 제외되며, 남은것은 s[line].top() == fret과 < fret경우일 뿐인데,

==인경우 아무것도 하지 않고 넘어가야하므로, !=으로 대체할 수 있다 

 

/*
 * 샘플코드 참고 -> 생각한 방법은 맞았는데
 * 1. 기타의 줄수가 최대 6개라는 사실을 캐치못함
 * 2. 알고리즘을 구현하는 방식이 너무 정리되지 않게 짜여짐
 * */


#include <iostream>
#include <vector>
#include <stack>

using namespace std;
vector<pair<int, int>> v;


vector<stack<int>> s(7);


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int N, P; //음의 수 , 프렛의 수
    stack<int> stack;

    cin >> N >> P;

    v.assign(N, {0, 0});


    int l, p;//줄 번호, 프렛번호


    for (int i = 0; i < N; i++) {
        cin >> l >> p;
        v[i] = {l, p};


    }


    int ans = 0; //맨 처음 연주
    int line, fret;


    for (int i = 0; i < N; i++) {



        //현 입력
        line = v[i].first;
        fret = v[i].second;


        while (!s[line].empty() && s[line].top() > fret) {
            s[line].pop();
            ans++;
        }
        if (s[line].empty() || s[line].top() != fret) {
            ans++;
            s[line].push(fret);
        }


    }

    cout << ans;


}

다음 4줄로 줄일 수 있으며, 걸리는 시간은 사실 동일하더라..