백준 알고리즘 문제_1406번

이번 시간에는 1406번 문제를 풀어보겠습니다.

 

백준 알고리즘 1874번: 1406번: 에디터 (acmicpc.net)

1406번: 에디터

 

문제 :

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

 

생각해보기 :

-. 입력을 list로 받아야 한다 -> list(input()) 사용하기

[list로 받으면 자동으로 나눠진다 ex) apple -> ['a', 'p', 'p', 'l', 'e']

-. 명령어 정의하기 커서 이동하는 횟수를 변수로 저장하고 P 또는 B와 결합하여 사용?

-. 리스트의 끝쪽에 도달하였을때 count를 계산 안 하기

 

<내가 짠 코드>----오답 ㅠㅠ

 

#첫 단어 및 싸이클 횟수 받기 (인덱스 넘버는 가장 끝으로 해줘야한다!!)
import sys
initial_word = list(sys.stdin.readline().split())
cycle_num = int(sys.stdin.readline())
cursor = len(initial_word)

for i in range(cycle_num):
  command = list(sys.stdin.readline().split()) #string으로 command받기!
  if "L" in command and cursor != 0:
    cursor -= 1
  elif "D" in command and cursor != len(initial_word):
    cursor += 1
  elif "B" in command and cursor != 0:
    initial_word.pop(cursor - 1)
    cursor -= 1
  elif "P" in command:
    initial_word.insert(cursor, command[1])
    cursor += 1

#최종 글자 만들기
final_word = ""
for alphbet in initial_word:
  final_word += alphbet

print(final_word)

 

처음에는 시간 초과로 나왔는데 command 입력을 sys를 사용하니 시간 초과는 안 나왔지만 오답이 나왔다.....ㅠㅠ

커서 위치를 설정해주면서 만들었는데 오답이 나와 당황스러웠다.. 조건문들을 이리저리 바꿨지만 끝까지 오답...ㅠㅠㅠ

 

개선 필요 사항 및 배운 점!

구글링을 하다 보니 내가 푼 방법은 시간 복잡도를 생각하지 않은 방식이라는 것을 알게 되었다.

list에서 B나 P로 인해 중간 값들이 빠지면서(insert(n, m) or remove(n))  시간 복잡도가 O(n)이 된다고 한다..

다른 분들의 풀이 방법을 보니 Deque와 투 스택을 주로 사용하셨다 -> 투 스택으로 한번 풀어봐야겠다...

 

<내가 짠 코드 Ver2> ----오답 ㅠㅠ

#첫 단어 및 싸이클 횟수 받기 
import sys
initial_word = list(sys.stdin.readline().split())
cycle_num = int(sys.stdin.readline())
#커서기준 오른쪽 글자들은 오른쪽 리스트로 보내주기
r_li = []

for i in range(cycle_num):
  command = list(sys.stdin.readline().split()) #리스트로 command받기!
#L인 경우-> 왼쪽 리스트의 요소가 있다면 오른쪽 리스트에 왼쪽의 마지막 요소 이동시켜주기
  if "L" in command:
    if initial_word: r_li.append(initial_word.pop())
    else: continue
#D인 경우-> 오른쪽 리스트의 요소가 있다면 왼쪽 리스트에 오른쪽의 마지막 요소 이동시켜주기
  elif "D" in command:
    if r_li: initial_word.append(r_li.pop())
    else: continue
#B인 경우-> 왼쪽 리스트의 요소가 있다면 왼쪽 리스트의 마지막 요소 삭제시키기
  elif "B" in command:
    if initial_word: initial_word.pop()
    else: continue
#P인 경우-> 왼쪽리스트의 마지막 항에 P뒤의 문자 추가
  elif "P" in command:
    initial_word.append(command[1])
    

#오른쪽 리스트는 나중에 들어간 것이 마지막 항에 있으므로 반대로 합쳐줘야한다.
print("".join(initial_word + r_li[::-1]))

 

문제에 있는 예제들을 실행하였을 때는 출력물들이 동일하게 나왔는데... 왜 틀렸는지 모르겠다....

 

 

개선 필요 사항 및 배운 점!

우선 나중에 써먹을 수 있을 것 같은(?) 잡기술을 배워왔다...

1. if 뒤에 조건문으로 리스트를 놓는 것 [리스트 안이 비워져 있으면 False, 리스트 안에 요소가 있으면 True]

 →나중에 리스트의 끝쪽에서의 동작들을 표현할 때 유용하게 사용할 수 있을 것 같다. 

2. 리스트의 요소를 빼면서(pop) 바로 다른 리스트로 더해줄 수(append) 있다.

 →코드 줄을 줄이는데 유용하지 않을까...?

3. join 함수 [리스트 요소들 간 구분자를 넣어 문자열로 합쳐준다] 

 →ex. a = ['나는', '직장인', '이다'] 리스트가 있을 때 print("_".join(a)) 을 실행하면 나는_직장인_이다가 출력된다.

 리스트 요소들을 문자열로 합칠 경우는 꽤 있을 것 같아 숙지하고 있어야겠다.

 

<내가 짠 코드 Ver3> ----정답!!

#첫 단어 및 싸이클 횟수 받기 
import sys
initial_word = list(sys.stdin.readline().strip())
cycle_num = int(sys.stdin.readline())
#커서기준 오른쪽 글자들은 오른쪽 리스트로 보내주기
r_li = []

for i in range(cycle_num):
  command = list(sys.stdin.readline().split()) #리스트로 command받기!
#L인 경우-> 왼쪽 리스트의 요소가 있다면 오른쪽 리스트에 왼쪽의 마지막 요소 이동시켜주기
  if "L" in command:
    if initial_word: r_li.append(initial_word.pop())
    else: continue
#D인 경우-> 오른쪽 리스트의 요소가 있다면 왼쪽 리스트에 오른쪽의 마지막 요소 이동시켜주기
  elif "D" in command:
    if r_li: initial_word.append(r_li.pop())
    else: continue
#B인 경우-> 왼쪽 리스트의 요소가 있다면 왼쪽 리스트의 마지막 요소 삭제시키기
  elif "B" in command:
    if initial_word: initial_word.pop()
    else: continue
#P인 경우-> 왼쪽리스트의 마지막 항에 P뒤의 문자 추가
  elif "P" in command:
    initial_word.append(command[1])
    

#오른쪽 리스트는 나중에 들어간 것이 마지막 항에 있으므로 반대로 합쳐줘야한다.
print("".join(initial_word + r_li[::-1]))

 

 

밑에 조건들은 다시 봐도 틀린 게 없고 출력문도 틀린게 없어서 입력을 가만히 보니 split이었다.

split()의 기본값은 띄어쓰기를 기준으로 나누는 것인데 하나의 단어가 들어오면 나눌 수 없지 않나라는 생각이 들었고 strip()으로 바꿔주니 정답이 되었다!

 

split과 strip의 차이는 간단히 아래 그림으로 나타내었다.

입력값을 리스트가 아닌 문자열로 받았을 경우

 

입력값이 리스트가 아니지만 띄어쓰기를 중간에 넣었을 경우

 

입력값을 리스트로 받았을 경우

 

입력값이 리스트로 받고, 띄어쓰기가 있는 경우

 

위에 정리한 것과 같이 split()을 사용하려면 기본적으로 리스트로 나타나지만, 입력값이 한 글자씩 띄어쓰기로 나눠져 있어야 ['a', 'p', 'p', 'l', 'e']를 얻을 수 있었다. [내가 짠 코드들은 전부 ['apple']로 받아서 실상 처음부터 꼬인 코드였다...]

 

반면 strip()을 사용하면 기본적으로는 띄어쓰기 유무와 상관없이 문자열로 나타나지만,

입력을 리스트로 설정해주고 apple를 넣어주면 ['a', 'p', 'p', 'l', 'e']를 얻을 수 있었다.

 

♠이 문제를 풀면서 느낀 점

 -. 시간 복잡도를 생각 못한 것과 리스트를 두 개 쓴다는 생각을 못했던 게 처음에 엄청 헤맨 이유였던 것 같다..

리스트의 중간 요소 삭제 및 삽입은 O(N) 인 것을 기억하자! + 리스트를 strip()으로 나눠 받으면 단어가 입력되었을 때 한 글자씩 리스트 요소로 받게 된다!