[Python][C++] 5430번 AC

문제

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

 

 

코드

1. Python

import sys
from collections import deque

input = sys.stdin.readline

for _ in range(int(input())):
    try:
        s = input().rstrip()
        n = int(input())
        idx = 1  # 배열의 순서를 관리하는 변수 (1이면 정방향, -1이면 역방향)
        
        nums = deque(input()[1:-2].split(','))  
        
        if nums[0] == '':  # 만약 배열이 비어있는 경우 처리 (빈 배열의 경우)
            nums.pop()  # 빈 문자열을 제거
        
        # 명령어 문자열을 하나씩 처리
        for ss in s:
            if ss == 'R':  # 'R' 명령어가 들어오면
                idx *= -1  # 배열의 순서를 뒤집기 위해 idx의 부호를 반전
            elif ss == 'D':  # 'D' 명령어가 들어오면
                if idx < 0:  # 역방향일 때
                    nums.pop()  # 배열의 뒤쪽에서 하나 제거
                else:  # 정방향일 때
                    nums.popleft()  # 배열의 앞쪽에서 하나 제거
        
        # 최종적으로 배열을 출력
        if idx > 0:  # 정방향일 경우
            print("[" + ",".join(list(nums)) + "]")
        else:  # 역방향일 경우
            print("[" + ",".join(reversed(list(nums))) + "]")
    
    # 예외 발생 시 (예: 배열이 비어있는 상태에서 'D' 명령어를 사용할 때)
    except:
        print("error")  # 'error' 출력

 

2. C++

#include <iostream>
#include <deque>
#include <string>
#include <sstream>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        try {
            string s;
            cin >> s;

            int n;
            cin >> n;

            string arr;
            cin >> arr;

            deque<int> nums;  // 숫자들을 저장할 덱(deque)
            string num;
            stringstream ss(arr.substr(1, arr.size() - 2));  // '['와 ']'를 제거하고 나머지 부분을 스트림으로 처리
            while (getline(ss, num, ',')) {  // 콤마(,)를 기준으로 숫자를 분리
                if (!num.empty()) {
                    nums.push_back(stoi(num));  // 분리된 숫자를 정수로 변환하여 덱에 추가
                }
            }

            int idx = 1;  // 방향을 나타내는 변수 (1: 정방향, -1: 역방향)
            for (char cmd : s) {  // 명령어 문자열의 각 문자에 대해 반복
                if (cmd == 'R') {  // 'R' 명령어일 경우
                    idx *= -1;  // 방향을 반대로 변경
                } else if (cmd == 'D') {  // 'D' 명령어일 경우
                    if (nums.empty()) {  // 덱이 비어있다면
                        throw "error";  // 예외 발생시켜 에러 출력
                    }
                    if (idx < 0) {  // 역방향일 경우
                        nums.pop_back();  // 덱의 마지막 요소 제거
                    } else {  // 정방향일 경우
                        nums.pop_front();  // 덱의 첫 번째 요소 제거
                    }
                }
            }

            // 결과 출력
            cout << "[";
            if (idx > 0) {  // 정방향일 경우
                for (size_t i = 0; i < nums.size(); i++) {
                    cout << nums[i];
                    if (i < nums.size() - 1) {  // 마지막 요소가 아니면 콤마 출력
                        cout << ",";
                    }
                }
            } else {  // 역방향일 경우
                for (size_t i = nums.size(); i-- > 0;) {
                    cout << nums[i];
                    if (i > 0) {  // 첫 번째 요소가 아니면 콤마 출력
                        cout << ",";
                    }
                }
            }
            cout << "]" << endl;  // 결과 끝부분에 닫는 대괄호와 줄 바꿈 출력

        } catch (...) {  // 예외가 발생하면
            cout << "error" << endl;  // 에러 메시지 출력
        }
    }

    return 0;
}

 

 

풀이 

주어진 명령어를 배열에 적용해 결과를 출력하는 문제. 리스트를 사용하면 시간 초과가 난다.

 

 

1. 명령어 분석:
   • R 명령어는 배열을 뒤집는 명령. 배열을 매번 뒤집는 것은 비효율적이므로, 실제로 뒤집는 대신 배열이 뒤집혀 있는 상태인지 여부를 기록하는 방식으로 처리
   • D 명령어는 배열의 첫 번째 요소를 삭제하는 명령. 배열이 뒤집혀 있을 경우, 마지막 요소를 삭제
2. 효율적인 처리 방법 (덱 사용):
   • 플래그를 이용한 뒤집기 처리: 실제로 배열을 뒤집지 않고, 뒤집힌 상태인지 아닌지를 나타내는 플래그를 사용
   • 덱(Deque) 사용: D 명령어를 효율적으로 처리하기 위해 양방향에서 요소를 제거할 수 있는 덱을 사용
   • 최종 출력: 모든 명령어를 처리한 후, 플래그 상태에 따라 덱을 그대로 출력하거나 뒤집어서 출력
3. 에러 처리:
   • D 명령어가 배열이 비어있을 때 실행되면 "error"를 출력