[SWEA] 암호문 3

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AV6kld8aisgDFASb&contestProbId=AV14zIwqAHwCFAYD&probBoxId=AV-4MojKLNADFATz&type=PROBLEM&problemBoxTitle=%5BD2%7ED3+%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4%5D+%EA%B8%B0%EC%B4%88+%EB%8B%A4%EC%A7%80%EA%B8%B0+Part4&problemBoxCnt=14 

SW Expert Academy

위의 문제를 요약하자면

기존 암호문 문자열(이하 PWs) 하나를 받고

그 다음 명령어 문자열(이하 COMs)을 하나 받는다.

 

명령어 문자열은 다음의 명령어들로 구성된다.

I x y s : "I"는 insert로 PWs의 x 위치 다음에 숫자들의 배열 s를 입력받는다 (y는 s의 길이)

D x y : PWs의 x 위치 다음의 y 만큼의 숫자를 삭제한다.

A y s : PWs의 마지막에 s를 입력한다 (y는 s의 길이)

 

나는 처음에 문자열의 길이가 4천자 정도 되고 명령어가 400개정도 되길래 

'아 이거 그냥 풀면 시간 초과 나는거 아니야?' 라고 생각이 들어서 연결리스트로 풀려고 했다.

 

연결리스트 풀이 방법 (실패함)

PWs와 COMs의 다음 Index를 가리키는 배열 ll_p, ll_c를 생성한다.

즉, ll_p[0]의 값은 ['p', 1]로 이는 PWs[0]의 다음 노드가 PWs[1]을 가리킨다는 것이다.

만약 명령어 'I'를 만나면 x번째 노드가 가리키는 다음 노드를 COMs의 주어진 문자열 시작지점을 가리킨다.

즉, I 2 3 c1 c2 c3 이런 문자열을 만나면 ll_p[2] = ['c', 4] 가 되는 것

벌써 말로만 설명해도 뇌에서 과부하가 일어났다

 

그런데 이 방식의 최대 문제점은 그다지 속도가 빠르지 않다는 것이다.

왜냐하면 x번째 노드를 찾기 위해서는 처음부터 다음 노드를 찾아가야 하기 때문

뭐 CD의 KMP 알고리즘처럼 기준 노드를 정하고 움직일 수도 있겠지만, 문제당 약 30분 정도밖에 주어지지 않는 코딩 테스트 환경에는 적합하지 않은 방식인 것 같다.

 

따라서 그냥 일반적으로 구현해보았다.

배열 내장함수 사용

배열 내장함수를 사용하여 구현했다.

Array.insert(ind, target)의 경우는 target을 그대로 Array[ind] 자리에 넣기때문에 반복문을 이용했고

del은 범위 지정이 가능해 그냥 사용했으며

Array.append(target)과 Array.extend(target)은 insert와 비슷한 이유로 extend()를 사용했다.

for T in range(10):
  n = int(input())
  pws = list(input().split())
  nc = int(input())
  coms = list(input().split())
 
  nextComInd = 0
  while nextComInd < len(coms):
    command = coms[nextComInd]
    if command == 'I':
      x = int(coms[nextComInd+1])
      y = int(coms[nextComInd+2])
      t_Array = coms[nextComInd+3: nextComInd+3+y]
      for i in range(len(t_Array)):
        pws.insert(x+i, t_Array[i])
      nextComInd += 3+y
    elif command == 'D':
      x = int(coms[nextComInd+1])
      y = int(coms[nextComInd+2])
      del pws[x:x+y]
      nextComInd += 3
    elif command == 'A':
      y = int(coms[nextComInd+1])
      s = coms[nextComInd+2:nextComInd+2+y]
      pws.extend(s)
      nextComInd += 2+y
  print(f'#{T+1}', *pws[:10])