[Python] 백준 5430 - AC

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

---

해결방법

문제에 나와있는 대로 따르면 충분히 풀 수 있는 문제이긴 하다.

하지만 곧이곧대로 따르기만 하면 여러 가지 문제로 해결이 불가능하다.

---

코드

tc = int(input())
for _ in range(tc):
    command = input()
    arr_len = int(input())
    input_raw_arr = input()

    raw_arr = list(map(str, input_raw_arr))
    raw_arr.pop(0);
    raw_arr.pop(-1)

    arr = (''.join(raw_arr)).split(',')

    error = False  # True: 에러 on, False: 정상작동중
    head = True  # True: 앞부터 읽기, False : 뒤부터 읽기
    for quri in command:
        if quri == 'R':
            head = not head
        elif quri == 'D':
            if arr != [] and arr != ['']:
                if head:
                    arr.pop(0)
                else:
                    arr.pop()
            else:
                print("error")
                error = True
                break

    if not error:
        if not head:
            arr = arr[::-1]
        ans = "["
        ans += ','.join(arr)
        ans += "]"
        print(ans)

---

코드 설명

1. 입력

    command = input()  # R과 D로 이루어진 문자열 명령어를 받아주는 변수.
    arr_len = int(input()) # 입력되는 배열의 길이 (다신 사용하지 않는다.)
    input_raw_arr = input() # 입력되는 배열
	
    #처음에 입력된 배열의 '[', ']' 을 없애기 위한 전처리 작업
    raw_arr = list(map(str, input_raw_arr))
    raw_arr.pop(0); # '[' 빼고,
    raw_arr.pop(-1) # ']' 도 마저 빼버린다.

    #그리고 다시 합쳐서 , 를 기준으로 찢어서 이제 제대로 된 배열을 만들었다.
    arr = (''.join(raw_arr)).split(',')

2.

    error = False  # True: 에러 on, False: 정상작동중
    head = True  # True: 앞부터 읽기, False : 뒤부터 읽기
    for quri in command:
        if quri == 'R':
            head = not head
        elif quri == 'D':
            if arr != [] and arr != ['']:
                if head:
                    arr.pop(0)
                else:
                    arr.pop()
            else:
                print("error")
                error = True
                break

error 가 발생하면 error를 True로 바꾸고, 더이상의 커맨드 수행을 종료한다.

head는 이 문제에서 핵심이라고 생각하는 역할을 한다. 문제에서 주어지는 'R' 이라는 명령은 배열을 뒤집는 명령인데 곧이곧대로 듣고 배열을 뒤집었다간 33%에서 시간초과에 걸리고만다.

그 이유는 python list를 뒤집는 함수인 reverse 함수의 시간복잡도에 있다. reverse 함수의 시간복잡도는 N인데, 문제에서 주는 조건을 보면 함수 p와 배열의 길이가 10만인 경우가 있고, 시간이 N*N 으로 증가할 수 있기 때문이다.

• 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.
• 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

극단적인 경우로, 만약 문제에서 주는 최대 리스트길이인 10만과, 명령 길이 10만. 모두 R로만 주어진다고 가정하면 10만*10만 = 10^(10) 만큼의 시간이 들 것이다.

이 링크를 누르면 reverse 이외에 다른 함수들의 시간복잡도도 확인할 수 있다. 아니면 구글에 검색해보자.

시간복잡도를 떠올리고나서 조금 고민해보니 굳이 배열을 뒤집는 수행을 할 필요가 없었다. 뒤집는다면 그냥 배열의 맨 뒤에서 주어진 명령을 수행하면 그만이기 때문. 그래서 boolean 타입의 head라는 변수를 선언한 것이다.

만약 head가 True 이면 앞에서부터 배열을 읽어내면 된다는 뜻이고, False는 반대로 뒤에서부터 배열을 읽어낸다는 의미이다.

3.

    if not error:
        if not head:
            arr = arr[::-1]
        ans = "["
        ans += ','.join(arr)
        ans += "]"
        print(ans)

error 가 False이면 에러가 발생하지 않았다는 의미이므로, 문제에서 요구하는 결과를 출력한다.

근데 왜 굳이 "[" + ','.join(arr) + "]" 를 출력토록 했는지 의문이 생길 수 있다.

처음엔 주어진 배열은 정수배열이라는 말을 보고선 'list(map(int, arr)))' 이 코드를 사용했으나, 왜인지 모르게 자꾸 에러가 났다.

그래서 하는 수 없이 위 코드를 사용했더니, 해결되었다.

내가 겪은 에러와 시간초과를 정리해보았다.

• 시간초과 : R 수행이 들어올때마다 리스트를 뒤집기
• TypeError : 리스트 안에 들어있는 모든 원소들을 int 로 바꾸려할때 (코드는 아래와 같다.)

 list(map(int, arr))

• ValueError : 아직 발견하지 못했다...