AC

 

5430번: AC

 

 

🤔생각해보기

꽤나 매콤한(?) 문제였습니다. 시간초과 제한이 상당히 타이트한데, 하나하나 짚어봅니다.

먼저 제시된 함수를 보면 뒤집는 것과 첫번째 숫자를 버리는 것입니다.

파이썬을 평소 즐겨 사용해왔다면 collections deque 모듈에 존재하는 다음과 같은 함수를 바로 떠올릴 수 있을 겁니다.

• reverse()
• popleft()

위 메소드만 잘 사용하면 "예제는" 통과하는 답을 나오게 할 수 있습니다.

하지만 위 메소드 중 어느 하나라도 사용한다면 얄짤없이 바로 시간초과가 발생합니다. 한마디로 함정카드인 것이죠.

 

효율성을 높이기 위해 떠올려야하는 아이디어는 여러가지가 있겠지만, 제가 풀어간 방법을 아래에 적어보겠습니다.

1. 배열 전체를 몇 번씩이나 뒤집어야할 필요가 있을까? 2번 뒤집으면 뒤집기 전과 똑같은데? → replace() 를 사용해서 연속된 "RR" 을 제거하자.
2. 첫 번째 숫자를 버려야만 하는데, 일반적으로 배열에서 첫번째 index를 빼면 O(N)의 시간복잡도가 발생한다. deque 를 쓰지 않고 숫자를 버리는 방향을 어떻게 조절할 수 있을까?
3. 애초에 반드시 뒤집어야만 하는가? 뒤집지 않고 버리는 방향을 조절할 순 없을까?

1번에서 연속된 "RR" 은 제거가 되었겠지만, "RDRDRDRDRDRD..." 과 같이 연속되지 않는 "R" 은 남아 있고 여전히 아주 많은 뒤집기를 실행해야합니다. 언뜻보면 뒤집기를 실행할 수 밖에 없어보입니다.

 

하지만 배열을 현재 뒤집은 횟수와 비교해서 앞뒤로 자른다면 어떻게 될까요?

 

2, 3번 아이디어를 해결하기 위해서는 큐나 덱의 관점을 버리고 문자열을 앞뒤로 슬라이스한다는 생각으로 간다면 방향을 찾을 수 있게 됩니다.

front, back, rev 변수를 만들어서 횟수를 저장해두고 이 변수들로 원래의 배열을 슬라이스하는 로직을 작성해봅니다. rev 가 홀수라면 뒤집혔으니 뒤에서 잘라야하고, 짝수라면 원상태로 돌아왔으니 앞에서 자르면 됩니다.

성공 코드

T = int(input())
for _ in range(T):
    p = input()
    n = int(input())
    nums = input()[1:-1].split(',')

    # 뒤집는 과정 1차 필터링
    p = p.replace('RR', '')

    front, back, rev = 0, 0, 0
    for i in p:
        if i == 'R':
            rev += 1
        else:
            if rev % 2 == 0:
                front += 1
            else:
                back += 1

    if front <= n - back:
        nums = nums[front:n - back]
        if rev % 2 != 0:
            print('[' + ','.join(nums[::-1]) + ']')
        else:
            print('[' + ','.join(nums) + ']')
    else:
        print("error")

수많은 도전의 흔적