백준_5430_AC

문제

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

5430번: AC

풀이

1) two pointer

리스트를 직접 뒤집거나, 특정 원소를 제거하면 수행 시간이 오래 걸리므로 다른 방법을 생각했다.

• 리스트 뒤집기

리스트가 뒤집어 졌는지 여부를 저장하는 변수를 하나 두어, R이 나올 때 마다 이 값만 갱신했다.

• 원소 제거하기

리스트가 뒤집어지지 않았다면 왼쪽에서 원소를 꺼내고

리스트가 뒤집어졌다면 오른쪽에서 원소를 꺼낸다.

(deque를 활용해도 된다.)

 

직접 리스트를 수정하지 않고, start point와 end point를 두어

왼쪽에서 원소를 꺼내야 할 때는 start point += 1,

오른쪽에서 원소를 꺼내야 할 때는 end point -= 1

을 해주었다.

2) 예제 출력 형식

예제 출력을 보면 [2,1] 처럼 띄어쓰기를 포함하지 않도록 출력하고 있다. 

arr = [1, 2, 3, 4]
print(arr)

위 코드처럼 리스트를 그냥 출력하면 [1, 2, 3, 4]로 공백이 포함된다. 

(이걸 발견 못해서 오래 고생했다ㅠㅠ) 

코드

def sol(p, n, arr) :
    reverse = False
    s, e = 0, n

    for i in p : 
        if i=="R" : reverse ^= 1
        elif i=="D":
            if (s==e) : return "error"
            if reverse : e-=1
            else : s+=1

    if reverse : return arr[s:e][::-1]
    return arr[s:e]

import sys
T = int(input())
for _ in range(T) : 
    p = sys.stdin.readline().strip("\n")
    n = int(sys.stdin.readline().strip("\n"))

    arrinput = sys.stdin.readline().strip("\n").replace("[", "").replace("]", "").replace(" ", "")
    if arrinput==""  : arr = list()
    else : arr =  list(arrinput.split(","))

    ans = sol(p,n,arr)
    if ans== "error" : print(ans)
    else : 
        print("[", end = "")
        print(",".join(ans), end = "")
        print("]")

알고리즘

• 구현
• 자료 구조
• 문자열
• 파싱
• 덱