사용자 도구

사이트 도구


ps:problems:boj:5430

AC

ps
링크acmicpc.net/…
출처BOJ
문제 번호5430
문제명AC
레벨골드 5
분류

기초

시간복잡도O(p+n)
인풋사이즈p<=700,000, n<=700,000
사용한 언어Python
제출기록42996KB / 168ms
최고기록120ms
해결날짜2021/08/09

풀이

  • 그냥 시키는 대로 구현한다고 생각해보자. R명령에 대해서 진짜로 리스트를 다 뒤집으려면 거기에만 O(n)의 시간이 필요하고, 그렇게 하면 시간복잡도는 최대 O(pn)까지도 걸린다.
  • 실제로 뒤집는 대신에, 현재 뒤집어진 상태인지 안뒤집어진 상태인지를 저장하는 변수를 만들어서 그 값만 바꿔주는 식으로 처리하자. D명령을 처리할때에는 거기에 따라서 앞에서 또는 뒤에서 삭제시키는 것으로 처리하면 되고, 최종적으로 출력할때에만 최대 한번 뒤집어주면 된다. 앞이나 뒤에서 삭제하는 것은 덱을 쓰면 O(1)에 처리 가능하므로 전체 명령을 처리하는 것은 O(p)에 해결된다
  • 위의 방법으로 처리하면 시간복잡도상으로는 최적이지만, 사실 굳이 덱을 써서 하나씩 삭제하는 것조차도 필요없기는 하다. 실제로 원소를 삭제하는 대신, 전체 리스트에서 남아있게되는 원소들의 시작과 끝 인덱스만 업데이트해주는 것으로 처리하자. 마지막에 출력할때에만 인덱스를 갖고 해당하는 구간만 한번 잘라내서 출력해주면 된다
  • 총 시간 복잡도는, 각 테스트 케이스별로 O(n_i+p_i) 이다. 모든 테스트에 대해서 n_i와 p_i를 더한 값을 각각 n과 p라고 하면, 그냥 O(n+p)로 쓸수 있다

코드

"""Solution code for "BOJ 5430. AC".

- Problem link: https://www.acmicpc.net/problem/5430
- Solution link: http://www.teferi.net/ps/problems/boj/5430
"""


def main():
    T = int(input())
    for _ in range(T):
        p = input()
        n = int(input())          
        nums = input()[1:-1].split(',')
        
        if p.count('D') > n:            
            print('error')
            continue        
        beg, end = 0, n         
        is_reversed = False
        for func in p:
            if func == 'R':
                is_reversed = not is_reversed
            elif is_reversed:
                end -= 1
            else:
                beg += 1
        sublist = reversed(nums[beg:end]) if is_reversed else nums[beg:end]
                
        print(f'[{",".join(sublist)}]')
                        

if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
M H D D Y
 
ps/problems/boj/5430.txt · 마지막으로 수정됨: 2021/08/09 13:16 저자 teferi