[백준::5430 python3] AC

최근 계속 하루에 하나씩 문제를 풀고있는데, 그 중 나름 짜증났거나 재밌었던 문제들을 가져오는 중이다.

이 문제는 짜증의 유형에 속하는데, 문제 자체는 간단한데 난해한 테스트케이스 뭐 좋게 말해야 난해한거고

사실 지랄맞은것이다. 그래서 이 문제를 풀이한사람들은 한번씩 욕한 흔적이 있다.

 

잡소리

이 문제는 장단점이 명확하다.

우선 장점의 경우, 겉보기에 간단해 보이는 문제지만 간과할 수 있는 실수와 경우가 생각보다 더 있고, 그걸 탐구하는 방법을 스스로 학습할 기회가 됐다.

 

그리고 단점은 문제 자체에 있는게 아니라, 사람에 있는거 같은데.. 굳이 출력까지 저렇게 걸러야했나 싶다.

문제를 만들어본 입장에서 테스트케이스 20개로 정답 걸러내는 프로세스만드는게 생각보다 쉽진 않지만 그렇다고 그렇게 어렵지도 않던데.. 그냥 유저 엿먹이는것으로 보일정도로 악랄했다.

게다가 문제 풀이 방식이 굉장히 한정적이다. 이런문제는 굉장히 주입식교육같은 프로그래밍이라고 생각해서 암튼 좀 별로다.

 

---

본론으로 넘어가서 문제를 간단하게 요약하면 R = Reverse / D = Delete인데,

 

첫째줄에 테스트케이스의 T를 받고

둘째줄은 문자열로 이루어진 명령어 S,

셋째줄은 몇개의 숫자 N이 올 것인지,

넷째줄은 입력 할 숫자를 list의 형태로 입력하면 된다 (DATA).

 

각 변수를 T,S,N,DATA로 명명해서 설명하겠다.

신경을 써야하는 여러 조건을 요약하면 이러하다.

1. DATA가 비었을때 D 입력시, error출력 / R 입력시는 제외

2. 입력 받는 데이터의 크기를 감안해야한다.

3. 까먹었다.

 

뭐 대충 이러하다!

일단 테스트케이스 부터 알려주겠다.

스페이스는 \n으로 알아서 알잘딱깔센

테스트케이스는 알아서

input : D 0 [] R 0 [] R 0 []

output : error [] []

 

input : RRDDDDDRRRRRDRDDDRRRRRDRRDRRRR 18 [65,14,87,67,55,58,23,51,85,41,69,25,31,63,70,64,59,21]

output:  [70,63,31,25,69,41,85]

 

input : RRRDDDRRR 4 [1,2,3,4,5,6]

output : [1,2,3]

 

그 외 질문게시판으로

 

대표적으로 위 세개의 테스트케이스를 보면 된다.

참고로 시간초과가 걸린 사람들이 굉장히 많은데, 이건 리스트의 크기 때문이다.

시간의 경우 코드 중간중간 print로 로그를 계속찍어주면 프로그램이 미친듯이 돌아가는걸 볼 수 있는데, 여기서 대충 짐작해서 코드를 요약하거나 논리를 엎고 새로 만들면 된다.

 

풀이 방식은 이렇다.

원래 이런식의 쉬워보이는 문제들은 속임수가 있는데, 그건 바로 reverse이다.

c++로 풀던, python으로 풀던 라이브러리 가져와서 풀면되는데, reverse는 계속 돌면서 O(1)인것처럼 보이지만 그게 아니라서 수가 늘면 늘수록 굉장히 연산수가 늘어난다.

그래서 시간 초과 한번보고 딱! 촉이 왔다.

 

안풀릴땐 사람의 관점에서 바라본걸 코드로 한줄한줄 풀면 된다.

[1,2,3,4]가 있을때 RRRDDD라면,

R - [4,3,2,1] - R - [1,2,3,4] - R - [4,3,2,1] - D - [3,2,1] - D - [2,1] - D - [1]

이렇게 1이 나온다.

이때 R을 보면 R이 짝수번/홀수번으로 나뉘게 되는걸 볼 수 있다.

 

이때 파이썬의 경우 더 쉽게 풀 수 있다.

strip을 쓰면 되는데, strip,lstrip,rstrip이 있다.

strip()은 양쪽 ()안에 있는 데이터를 지워버리는것이고, lstrip은 앞에서 부터 ()안에 내용을 찾고 아닌 내용이 나올때까지 지우는걸 반복하는것이다. 예로들어 RRRDDRR인 문자에 lstrip('R')이면, DDRR만 남게된다.

rstrip은 그 반대다.

 

정리하면 이렇다.

1. 입력된 첫번째 명령어가 R인가 D인가?

1-1. D라면 데이터의 맨 앞 하나를 삭제한다.

1-2. R이라면 R이 총 몇개인가? 힌트) 총 크기 - lstrip('R')한 크기 = R의 개수

2. 1이 아닐경우 D혹은 R일경우

2-1. R이라면, 1-2로

2-2. D라면, 맨 앞 삭제

 

대충 이러면 된다.

살짝 더 자세하게 말하면

0번인덱스에 D가 있다면, DATA의 맨 앞 하나를 지운다. 루프를 끝내기 전 명령어 S의 맨 앞을 제외한 나머지를 슬라이싱으로 마치 맨 앞 하나만 떼어진것처럼 복사한다.

 

반면, 0번 인덱스에 R이 있다면, R의 개수를 구하고 홀인지 짝인지, 그리고 그걸 구분해줄 변수 등이 필요하다.

왜냐하면, [1,2,3,4]에 DRD라는 명령어가 오면, [2,3,4]에서 한번 뒤집어 다음 루프에서 [4,3,2]가 된 채로 시작해야하기 때문이다.

이건 단순히 isReverse와 같은 변수를 밖에 빼준 후 정의하고 초기화를 안하면 된다.

 

 

 

마지막으로 풀이 방법은 크게 두가지다.

queue를 만들어서 하던가, collections에서 deque를 사용하던가

 

파이썬이 미묘하게 c++과 달라서 인덱스 접근에 대해서 이게 뭐야했었는데, 라이브러리를 뒤져보다가 deque를 우연히 발견했는데, deque에 대한건 예전에 들어봤기에 썼다. 분명히 leftpop이였던거 같은데... 아님말고

 

popleft는 맨 앞 수를 잘라내주는애다.

 

나머지는 코드를 참고하거나 위 논리를 보고 머리를 써보길 바란다.

사실 이정도까지 코드를 이해할 정도면 이 문제는 풀 수 있다.

그럼에도 불구하고 코드를 보는건, 과제거나, 머리를 쓰기 싫어서 대충 처리하려는것.

 

후자의 경우 최악의 선택이란걸 알아두길바란다.

 

 

 

 

 

 

코드주의

 

 

 

 

 

 

 

import sys
from collections import deque

def main():
    inputTestCase = int(sys.stdin.readline())
    
    for i in range(inputTestCase):
        inputCommand = sys.stdin.readline().replace('\n','') # R = REVERSE , D = DELETE
        inputSize = int(sys.stdin.readline())
        if inputSize > 0 :
            inputData = deque(map(int,sys.stdin.readline().replace('[','').replace(']','').split(',')))
        else:
            inputData = sys.stdin.readline().replace('[','').replace(']','').replace('\n','')

        result = '['
        isError = False
        isReverse = False # D의 경우를 생각해서 초기값은 false
        for k in range(len(inputCommand)):
            if inputSize == 0 and inputCommand[0] == 'D': 
                isError = True
                break
            if len(inputCommand) == 0 or len(inputData) == 0: break
            temp = len(inputCommand.lstrip('R')) #맨 앞부터 차례대로 R이있으면 삭제 후 길이 리턴
            temp = len(inputCommand)-temp # 총 길이 - 수정된길이 = R의 개수 없으면 당연히 0 temp가 1 이상이면 있다는 뜻
            if temp > 0: # R이 있느냐? - 있으면 홀이냐 짝이냐?
                # RRRDDDRRR 4 [1,2,3,4] -> [1]
                if temp % 2 == 1: # 홀이면 한번 뒤집혀야함
                    if isReverse:
                        isReverse = False
                    else:
                        isReverse = True # 실제론 뒤집지 않음.
                inputCommand = inputCommand.lstrip('R')
            if len(inputCommand) < 1:
                break
            if isReverse: # [1,2,3,4]에서 뒤집힌 채로 D가 들어온다면 4를 지워야함
                # 위에서 R이 무조건 걸러지니, 오는 명령어는 무조건 D
                inputData.pop()
            else: # 뒤집지 않은채로 삭제 -> 맨앞삭제 -> popleft
                inputData.popleft()
            inputCommand = inputCommand[1:]
        if len(inputCommand) > 0:
            if inputCommand.count('D'):
                isError = True
        if isReverse:
            for k in range(len(inputData)-1,-1,-1):
                result+='{0:}'.format(inputData[k])
                if k != 0:
                    result+=','
        else:
            for k in range(len(inputData)):
                result+='{0:}'.format(inputData[k])
                if len(inputData)-1 != k:
                    result+=','
                    
        result+=']'
        if not isError:
            print(result)
        else:
            print('error')
        
            


main()
#3

# D 0 [] 

# R 0 []

# R 0 []