[백준_5430] AC with Python

백준(BOJ) 큐, 덱: AC(골드 5)

문제 출처: https://www.acmicpc.net/problem/5430

5430번: AC

 

1. 알고리즘

• 테스트케이스 만큼 반복하며, p(함수), n(배열의 요소 갯수), arr(배열) 입력받음
  • 이때, arr의 경우, '[x1, x2, ..., xn]'의 형태로 들어오기 때문에 전처리가 필요.
  • strip함수로 앞 뒤의 '[]'를 삭제, 맨 뒤의 '\n'를 삭제
  • try~except문을 사용, arr이 비어있을 때를 예외처리해줌
    • 비어있지 않을 경우, ','를 기준으로 수를 분리, deque 자료형으로 저장
    • 비어있는 경우, 비어있는 deque 자료형 선언
  • 정방향, 역방향을 표현하기 위한 flag와 error 발생을 확인하기 위한 flag 선언
    • forward_direction == True: 정방향. False이면 역방향
    • error_flag == True: D함수에서 에러 발생. False이면 에러 발생하지 않음
  • 입력받은 함수 p만큼 반복하며 함수 수행
    • R이면, forward_direction flag 값을 변경
    • D인 경우, 방향(forward_direction)을 확인하여 값을 삭제
      • 정방향이면, popleft()함수로 맨 앞의 값 삭제
      • 역방향이면, pop()함수로 맨 뒤의 값 삭제
      • 비어있는 경우, error_flag를 True로 변경
  • error_flag, forward_flag를 확인하여 결과값 출력
    • error 발생 시, 'error' 출력
    • error가 발생하지 않고 정방향일 경우, arr를 출력형태에 맞게 변형하여 출력
    • error가 발생하지 않고 역방향일 경우, arr를 출력형태에 맞게 변형하여 출력

 

2. 유의 사항

• 시간초과의 문제
  • 'R'함수 입력 시, 실제로 데이터를 뒤집어서는 안됨. ▶ reverse(), list[::-1] 사용 금지
  • pop(0)의 경우, 시간복잡도가 O(N)임에 주의
• 출력 형태의 문제
  • Python에서 list를 그대로 반환 시, 50%에서 분명 '틀렸습니다'가 떴음
  • Python의 list 출력 형태는 [A, B, C], 문제에서 요구하는 출력 형태는 [A,B,C]. 띄어쓰기가 없음에 주의해야 함

 

3. 어려웠던 점, 해결방안

• 배열을 입력받아 숫자를 분리할 때, 숫자를 인덱스 하나씩 분리함.
  • '42'를 입력받았을 때, '4, 2'로 분리되는 문제. ','를 기준으로 분리하는 것으로 해결
• reverse() 함수 사용으로 시간초과가 떴었음.
  • forward_flag 사용으로 방향을 표시하는 것으로 돌려주어 해결

 

4. 소스코드

상세 코드 설명은 주석

import sys
from collections import deque
 
 
input = sys.stdin.readline
if __name__ == '__main__':
    T = int(*map(int, input().split()))
 
    for _ in range(T):
        #함수, 배열 요소 갯수, 배열 입력
        p = str(*map(str, input().split()))
        n = int(*map(int, input().split()))
        arr = input().strip('[]\n')
        
        #빈 arr예외 처리(ex. arr = [])
        try:
            arr = deque(map(int, arr.split(',')))
        except:
            arr  = deque()
        
        #방향, error flag
        forward_direction = True
        error_flag = False
        #입력받은 함수만큼 반복, 데이터 처리
        for cmd in p:
            #'R'함수의 경우, 방향 flag를 변경
            if cmd == 'R':
                forward_direction = False if forward_direction else True
            #'D'함수의 경우, 방향에 맞는 맨 앞의 데이터 삭제
            elif cmd == 'D':
                try:
                    if forward_direction:
                        _ = arr.popleft()
                    else:
                        _ = arr.pop()
                except:
                    error_flag = True
        
        #함수 실행 결과 
        if error_flag:
            print('error')
        elif forward_direction:
            print_arr = str(list(arr)).replace(' ', '')
            print(print_arr)
        else:
            print_arr = str(list(reversed(arr))).replace(' ', '')
            print(print_arr)

 

5. 고민

• 'D'함수 실행 시, error가 발생하면 그냥 break로 빠져나왔으면 더 빨랐을 것...
• 함수 실행 결과 출력 시, arr 값을 변경해줄 때 더 간결하게 바꿀 수 있는 방법이 있지 않을까?