[백준]AC

문제 이해하기

 선영이라는 친구가 새로운 함수를 만들었는데, 해당 함수는 "R"과 D로만 이루어져있다.

R은 reverse고 d는 delete다.

 

즉 R을 만나면 배열을 뒤집어야 하고, D를 만나면 해당 배열에서 젤 처음 숫자를 삭제해야한다.

문제 해결 방법 설명하기

1. R을 만나면 배열을 역순으로 변경해야할까?

그렇다 R을 만날 때 마다 매번 배열을 역순으로 변경한다면 시간초과가 나타난다. 따라서 우리는 배열이 뒤집어 졌다는 것을 기억하고, 실제로 연산은 수행하지 말아야 한다.

    for f in funcStr:
        if f == "R":
            direction = not direction

 

2. D를 만나면 배열에서 삭제를 진행해야 할까?

D의 연산의 경우 실제로 수행해도 상관은 없다 왜냐하면 O(1)이기 때문이다.

하지만 굳이 삭제를 할 필요성은 없다.  연산의 방향을 기억해서 처음 시작점이 어디고, 배열의 마지막이 어딘지를 기억하면 된다. 

    for f in funcStr:
        if f == "R":
            direction = not direction
        elif f == "D":
            count += 1
            if direction:
                left += 1
            else:
                right -= 1

 

3. 에러는 언제 반환할까?

배열에서 삭제 연산이 실패하는 경우는 배열의 원소 개수보다 D의 수행 횟수가 큰 경우임으로 D의 수행 횟수를 기억해서 error를 반환하도록 했다,

    if len(target) < count:
        return "error"

 

코드

def solution(funcStr, target):
    # R: reverse
    # D: delete
    # 빈 배열에서 D가 나오면 error
    
    direction = True
    left = 0
    right = len(target)
    count = 0
    
    for f in funcStr:
        if f == "R":
            direction = not direction
        elif f == "D":
            count += 1
            if direction:
                left += 1
            else:
                right -= 1
                
    if len(target) < count:
        return "error"
                
    if not direction:
        target = target[left:right][::-1]
        return target
    
    return target[left:right] 


if __name__ == "__main__":
    tc = input()
    
    for i in range(int(tc)):
        funcStr = input()
        _ = input()
        cand = input()
        
        if cand == "[]":
            target = []
        else:
            target = list(map(int, cand[1:-1].split(",")))
        ans = solution(funcStr, target)
        if ans == "error":
            print(ans)
        else:
            print("[" + ",".join(map(str, ans)) + "]")

코드 리뷰

양방향 링크리스트로 구현하면 훨씬 깔끔할 것 같다.