C++으로 카드 문자열 문제 해결하기: 데이터 구조의 활용법

C++로 재미있는 데이터 구조 활용하기: 카드 문자열 편

안녕하세요, 프로그래밍을 사랑하는 여러분! 오늘은 C++을 이용해 흥미로운 카드 문자열 문제를 풀어보겠습니다. 이 문제는 주어진 카드로부터 사전 순으로 가장 앞서는 문자열을 만들어내는 도전입니다. 그렇게 어렵지 않지만, 데이터 구조를 활용하는 것이 관건이죠!

문제 이해하기

우리는 N장의 카드 중에서 첫 번째 카드를 선택하고 이후 카드들은 현재의 문자열 앞이나 뒤에 붙여서 최종적으로는 사전 순으로 가장 앞서는 문자열을 구하는 방법을 고민해야 합니다. 여기에 필요한 것이 바로 deque입니다! deque는 양쪽 끝 모두에서 원소를 추가하거나 제거할 수 있어서 이 문제에 잘 어울리죠.

코드 살펴보기

우선 주어진 문제를 해결하기 위한 코드를 작성해볼까요? 아래는 그 코드입니다:

#include <iostream>
#include <deque>

using namespace std;

int main() {
    int T, N;
    char c;
    
    cin >> T;
    
    for (int i = 1; i <= T; i++) {
        deque<char> dq;
        cin >> N;
        
        for (int j = 0; j < N; j++) {
            cin >> c;

            if (j == 0) {
                dq.push_back(c);
            }
            else if (c <= (dq.front())) {
                dq.push_front(c);
            }
            else {
                dq.push_back(c);
            }
        }
        
        for (int j = 0; j < dq.size(); j++) {
            cout << dq[j];
        }
        
        cout << "
";
    }
    
    return 0;
}

코드 설명

1. 변수 초기화: T는 테스트 케이스의 개수, N는 카드의 수를 저장하며, c는 입력받을 카드의 문자입니다.
2. 입력 처리: 반복문을 통해 T번 만큼 테스트 케이스에 대해 카드 수와 문자를 입력받습니다.
3. deque 활용:

• 첫 번째 카드는 무조건 deque의 뒤에 추가합니다.
• 이후의 카드들은 현재 deque의 제일 앞 카드와 비교하여 결정합니다.
  • 만약 새 카드가 앞 카드보다 작거나 같으면, deque의 앞에 추가하고,
  • 그렇지 않다면 뒤에 추가합니다.

4. 결과 출력: 모든 카드를 처리한 후, deque에 저장된 문자열을 차례로 출력합니다.

실행 예시

이 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다:

2
3
CAB
CBA

위의 입력은 두 개의 테스트 케이스가 있으며, 각 케이스에서 제공된 카드로 만들어진 문자열을 출력한 것입니다.

마무리

오늘 포스트에서는 카드 문자열 문제를 해결하는 방법을 살펴보았습니다. deque를 활용한 점이 꽤 흥미롭지 않나요? 이 코드를 개선하는 방법으로는 사용자 인터페이스 개선, 더 복잡한 카드 처리 로직 추가 등이 있을 수 있습니다.

여러분도 이 코드를 바탕으로 다양한 문제를 해결해보세요. 프로그래밍의 재미는 무궁무진하니까요! 또 다른 궁금증이나 질문이 있다면 언제든지 댓글로 남겨 주세요. 다음 포스트에서 만나요!