[Python] 백준, 5430 (구현)

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

5430번: AC

 

개요

• 구현의 어려움보다는 시간 초과의 해결이 더 메인이었던 문항
• 어찌저찌 정답이 뜨긴 했는데 이유를 잘 모르겠음

 

해결 방법

1. 첫 줄에 입력받는 n 만큼 순회
2. 세번째 입력이 리스트 타입으로 보이지만, 문자열의 형태로 들어오는 것이므로 추가적인 변환 필요
   • rstrip(), split() 메서드는 꾸준히 활용됨
3. error_flag 는 빈 배열에서 "D" 명령을 내릴 시 error를 발생시킬지 유무를 나타냄
4. reverse_cnt 는 두번째, 세번째 해결 코드 작성 시 활용
   • 내부 for 문을 순회할 때마다 reverse() , [::-1] 메서드를 호출하는 건 너무 비효율적이며 시간 초과
   • 앞 뒤로 뒤집는 일은 짝수 횟수가 될 때마다 원래 상태로 돌아오므로 이를 고려하여 cnt 를 세어줌
5. 입력받은 명령 배열 (ex. RDD) 을 순회하며 조건 나눠줌
6. result 배열에 정답을 담아놓고 하나씩 print
   • 이 또한 시간 초과의 이슈로 join 메서드 활용하는 쪽으로 마무리
   • join 메서드는 [1,2,3] 에서는 작동 안됨 ["1", "2", "3"] 같은 문자열 요소에서만 사용 가능

 

참고 사항

리스트 주요 메서드 시간 복잡도

주요 배열 메서드 시간 복잡도

deque 모듈

• pop(0)의 시간 복잡도를 고려해서라도 이번 문항에서는 deque의 popleft() 메서드를 활용하는 것이 나을듯
• deque의 경우, 특정 인덱스로의 접근은 O(n)의 복잡도를 지니지만, popleft, pop 메서드는 O(1)의 효율을 보임

 

Python Code : 실패 코드

import sys

n = int(sys.stdin.readline())

result = []

for _ in range(n):
    def_seq = sys.stdin.readline().rstrip()
    # def_seq = [s for s in def_seq]
    m = int(sys.stdin.readline())
    arr_seq = sys.restdin.readline().rstrip()
    if arr_seq == '[]':
        arr_seq = list()
    else:
        arr_seq = arr_seq[1:-1].split(',')
        arr_seq = [int(i) for i in arr_seq]

    error_flag = False

#     print(def_seq)
#     print(arr_seq)

    for s in def_seq:
        if s == "R":
            arr_seq = arr_seq[::-1]
        else:
            if len(arr_seq) == 0:
                error_flag = True
                break
            else:
                arr_seq = arr_seq[1:]

    if error_flag:
        result.append("error")
    else:
        result.append(arr_seq)

for s in result:
    print(s)

 

Python Code : 정답 코드

import sys

n = int(sys.stdin.readline())

for _ in range(n):
    # 초기화 부분
    def_seq = sys.stdin.readline().rstrip()
    m = int(sys.stdin.readline())
    arr_seq = sys.stdin.readline().rstrip()

    if arr_seq == '[]':
        arr_seq = list()
    else:
        arr_seq = list(arr_seq[1:-1].split(','))

    # error_flag : error를 표시할지 아닐지, reverse_cnt : 뒤집어주는 횟수 카운트
    error_flag = False
    reverse_cnt = 0

    for s in def_seq:
        if s == "R":
            reverse_cnt += 1
        else:
            if len(arr_seq) == 0:
                error_flag = True
                break
            else:
                if reverse_cnt % 2 == 0:
                    arr_seq.pop(0)
                else:
                    arr_seq.pop()
    if error_flag:
        print("error")
    else:
        if reverse_cnt % 2 == 1:
            arr_seq.reverse()
            print("[" + ','.join(arr_seq) + "]")
        else:
            print("[" + ','.join(arr_seq) + "]")