[백준 BOJ] 13417번 카드 문자열 (C++/cpp)

문제 설명

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

 

 

접근 방법 - 덱을 활용한 문자 연산 문제

백준의 13417번 문제는 덱 자료구조를 활용하여 비교적 쉽게 해결할 수 있는 문자 연산 문제이다.

해당 문제는, 각 테스트 케이스마다 입력받은 순서대로 문자가 적힌 카드를 받아 배치한다고 할 때 조합할 수 있는 경우의 수 중에서 사전적으로 가장 앞서는 단어를 구하여 출력해야 하는 문제이다.

 

필자의 경우엔 덱 자료구조를 활용하여 문자를 적절히 배치하게끔 코드를 구성하였다.

덱이란 앞 또는 뒤로 모두 요소 삽입 및 삭제가 가능한 자료구조라 보면 된다.

만약 덱 자료구조가 어색하다면, 아래의 문제를 먼저 해결해 보고 해당 문제 해결을 시도해 보는 것이 더 수월할 것이다.

https://smary-it.tistory.com/80

[백준 BOJ] 10866번 덱 (C++/cpp)

 

더 자세한 설명은 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 코드와 설명을 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 테스트 케이스의 수(t)를 입력받는다.

 

2) t의 크기만큼, 반복문을 수행하여 아래의 연산을 취한다.

- 카드의 개수(n)를 입력받는다.

- 문자를 배치할 때에 활용할 덱(dq)을 미리 선언해 둔다.

- n의 크기만큼 문자를 입력받는다. 이때, 입력을 하나씩 받을 때마다 아래의 연산을 수행한다.

• 만약 dp가 비어있거나 dp의 가장 앞에 위치한 문자보다 입력값이 사전적으로 앞선다면, 이 문자를 통해 단어를 사전적으로 더 앞서게 할 수 있기 때문에 해당 문자를 dp의 앞에 배치한다.
• 다만 위 조건을 만족하지 않는다면, 이 문자를 앞에 배치하면 단어가 사전적으로 뒤처질 수 있음을 뜻하기 때문에 해당 문자를 dp의 뒤에 배치한다.

- 위처럼 문자 입력 및 배치가 끝났다면, dp에 저장된 문자의 배치를 순차적으로 출력하도록 한다.

dp가 빌 때까지 dp의 앞에서부터 출력을 수행하고, 하나씩 출력할 때마다 dp에서부터 해당 요소를 삭제하도록 한다.

(마지막에는 개행을 출력하여, 다음 테스트 케이스에 대한 정답과 구별 짓도록 한다.)

 

3) 2)의 연산을 모두 수행하였다면, 실행을 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <deque>
#define endl '\n'
using namespace std;

//백준 13417번 코드
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);
   
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n;
        cin >> n;
        cin.ignore();

        deque<char> dq;
        for (int j = 0; j < n; j++) {
            char c;
            cin >> c;

            if (dq.empty() || dq.front() >= c) {
                dq.push_front(c); 
            }
            else {
                dq.push_back(c);
            }
        }

        while (!dq.empty()) {
            cout << dq.front();
            dq.pop_front();
        }
        cout << endl;
    }
}

 

제출 결과

(2023.11.20 백준 13417번 문제 제출 결과)