백준 2841번 외계인의 기타 연주

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

스택 배열을 이용하여 푸는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 줄이 1 ~ 6까지 6개이므로 크기가 7인 int형 스택을 선언합니다.

2. N번 동안 줄과 프랫을 입력받습니다.

i) 해당 줄의 스택이 비어있다면 무조건 추가합니다.

ii) 해당 줄의 스택이 비어있지 않고 현재 입력 받은 프랫이 기존에 입력받은 프랫보다 높을 경우 추가해줍니다.

iii) 해당 줄의 스택이 비어있지 않고 현재 입력 받은 프랫과 기존에 입력받은 프랫과 동일하다면 다음 줄과 프랫을 입력받습니다.

iv) 해당 줄의 스택이 비어있지 않고 현재 입력 받은 프랫이 기존에 입력받은 프랫보다 낮다면 현재 입력 받은 프랫이 스택의 top보다 높거나 같을 때까지 혹은 스택이 전부 빌 때까지 pop해줍니다.

-> pop을 전부 다 해 준 다음 스택의 top이 현재 입력받은 프랫과 같다면 다음으로 넘어가고 같지 않다면 추가해줍니다.

3. 2번에서 push와 pop한 횟수의 누적을 출력해줍니다.

#include <iostream>

#include <stack>

using namespace std;

 

int N, P;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> P;

 

        stack<int> s[7]; //줄 1 ~ 6

        int result = 0;

 

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

        {

                 pair<int, int> temp;

                 cin >> temp.first >> temp.second;

 

                 if (s[temp.first].empty())

                 {

                         result++;

                         s[temp.first].push(temp.second);

                 }

                 else

                 {

                         //무조건 제일 높은 음만 난다

                         if (temp.second > s[temp.first].top())

                         {

                                 s[temp.first].push(temp.second);

                                 result++;

                         }

                         //이미 있으면 추가할 필요 X

                         else if (temp.second == s[temp.first].top())

                                 continue;

                         else

                         {

                                 //temp.second가 제일 높은 음이 나도록

                                 while (!s[temp.first].empty() && temp.second < s[temp.first].top())

                                 {

                                          s[temp.first].pop();

                                          result++;

                                 }

 

                                 //이미 temp가 있다면 추가 X

                                 if (!s[temp.first].empty() && s[temp.first].top() == temp.second)

                                          continue;

 

                                 s[temp.first].push(temp.second);

                                 result++;

                         }

                 }

        }

 

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~