백준 27497번 [알파벳 블록](C++) -yes6686- 티스토리

백준 문제 풀이: 27497 (알파벳 블록)

---

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

문제 설명:

알파벳 블록을 이용해 다음과 같은 작업을 수행합니다:

• 1번 명령: 알파벳 c를 **오른쪽 끝**에 추가합니다.
• 2번 명령: 알파벳 c를 **왼쪽 끝**에 추가합니다.
• 3번 명령: 양 끝의 알파벳 중에서 먼저 들어온 블록을 제거합니다.

주어진 명령어를 처리한 후, 남아 있는 블록들을 출력하고, 블록이 없다면 0을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <deque>
using namespace std;

deque> dq; // 블록을 저장할 덱 (알파벳, 순서)

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

    int n; // 명령어 개수
    cin >> n;
    int cnt = 0; // 블록 추가 시 순서를 저장하는 변수

    for (int i = 0; i < n; i++) {
        int x; // 명령 번호
        char c; // 알파벳
        cin >> x;

        if (x == 1) { 
            cin >> c; // 블록을 오른쪽에 추가
            cnt++;
            dq.push_back({c, cnt});
        } 
        else if (x == 2) { 
            cin >> c; // 블록을 왼쪽에 추가
            cnt++;
            dq.push_front({c, cnt});
        } 
        else { 
            // 양 끝 중 순서가 빠른 블록 제거
            if (!dq.empty()) {
                if (dq.front().second < dq.back().second) {
                    dq.pop_back();
                } else {
                    dq.pop_front();
                }
            }
        }
    }

    // 결과 출력
    if (dq.empty()) {
        cout << 0; // 블록이 비어 있으면 0 출력
    } else {
        while (!dq.empty()) {
            cout << dq.front().first; // 덱의 앞에서부터 출력
            dq.pop_front();
        }
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘:
  • 덱(deque)을 사용하여 양 끝에서 블록을 추가하거나 제거합니다.
  • 각 블록에 순서를 부여하여 3번 명령에서 양 끝의 블록 중 먼저 추가된 블록을 제거합니다.
• 구현 세부사항:
  • push_back(): 블록을 오른쪽에 추가.
  • push_front(): 블록을 왼쪽에 추가.
  • pop_front()와 pop_back(): 3번 명령에 따라 양 끝 중 먼저 추가된 블록을 제거.
  • 덱이 비어 있으면 0을 출력합니다.
• 시간 복잡도 분석:
  • 덱의 **양 끝에서의 삽입과 삭제**는 O(1) 시간 복잡도를 가집니다.
  • 명령이 n개 주어질 때, 전체 시간 복잡도는 O(n)입니다.

---

결과

주어진 명령에 따라 블록을 조작한 후 결과를 출력합니다.

• 블록이 남아 있으면: 남아 있는 블록을 왼쪽에서 오른쪽으로 출력
• 블록이 비어 있으면: 0 출력

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!