[백준] 1406번 (feat. reverse와 reversed의 차이점)

[백준] 1406번 (feat. reverse와 reversed의 차이점)

 

https://www.acmicpc.net/problem/1406

1406번: 에디터

 

<기존의 코드> => 시간초과 뜸.

import sys

alpha = list(input())
num = int(input())
cur = len(alpha)

for i in range(num):
	line = sys.stdin.readline().split()
	if line[0] == 'P':
		alpha.insert(cur, line[1])
		cur = cur + 1
	elif line[0] == 'L':
		if cur == 0:
			continue
		cur = cur - 1
	elif line[0] == 'B':
		if cur == 0:
			continue
		alpha.pop(cur - 1)
		cur = cur - 1
	elif line[0] == 'D':
		if cur == len(alpha):
			continue
		cur = cur + 1

print("".join(alpha))

 

---

 

흔히 백준에서는 입력에 대한 부분만 어느정도 잡아주면 시간초과는 해결되는 것으로 알고 있었다. 

분명 sys.stdin.readline()으로 여러 줄을 입력 받았는데 왜 안 될까...?

 

그래서 질문 게시판과 다른 사람들이 써놓은 글을 봤는데, 이 문제가 특히 시간복잡도(Big-O)에 대해 까다롭게 잡는다는 사실을 알아챘다.

 

위의 코드에서 insert와 pop(index) method의 경우 시간복잡도가 O(N)이다.

그 위에 for문으로 감싸고 있으므로 사실상 이 메인문은 O(N^2)의 시간복잡도를 가진다고 할 수 있다.

(파이썬 함수, 메소드의 시간복잡도를 다룬 블로그: https://wayhome25.github.io/python/2017/06/14/time-complexity/)

 

결국은 for문안에서는 O(1)의 시간복잡도를 가질 수 있도록 코드를 구현해야 한다.

 

 

이를 어떻게 해야 할까.... 고민하다가 아이디어가 떠오르지 않아 다른 사람들은 어떻게 했는 지 확인해봤다.

 

다른 사람들은, append()와 pop()만을 가지고 어찌어찌 구현을 했더라.

(이 두 method는 시간복잡도가 O(1)이다. 매번 맨뒤에 붙이거나 맨뒤의 것을 빼기 때문)

 

 

이전 코드의 경우, 하나의 list만을 만들어서 처리를 했는데

 

다른 사람들은 이 append와 pop만을 사용하기 위해 별도의 list를 하나 더 생성하여 그 곳에 append()와 pop()으로 넣었다가 뺐다가를 반복하더라.

 

오호.... 별도의 리스트를 만들 생각은 전혀 못했는데 대단...

 

alpha = list(input())
lst = []

num = int(input())
cur = len(alpha)

for i in range(num):
	line = sys.stdin.readline().split()
	if line[0] == 'P':
		alpha.append(line[1])
	elif line[0] == 'L':
		if len(alpha) == 0:
			continue
		lst.append(alpha.pop())
	elif line[0] == 'B':
		if len(alpha) == 0:
			continue
		alpha.pop()
	elif line[0] == 'D':
		if len(lst) == 0:
			continue
		alpha.append(lst.pop())

alpha.extend(reversed(lst))
print("".join(alpha))

 

---

파이썬의 reverse와 reversed 차이에 대해 간단하게.

 

reverse는 list형식에 쓸 수 있는 method라고 생각하면 될 것 같고

reversed는 sequential한 자료형(ex. 리스트, 튜플, 문자열...)에서 사용할 수 있는 "내장함수"라고 보면 될 것 같다.

 

ex. lst.reverse()

ex. l = reversed(lst)

 

근데 조금 주의해야 할 게, return값이 다르다.

 

reverse()는 return값이 없다. 그냥 뒤집어주고 끝.

근데 reversed()는 return값으로 그 객체를 반환한다.

 

이 차이만 잘 인지하면 헷갈릴 일은 없을 것 같다.

 

 

(나는 너무 대충 한 듯.... https://itholic.github.io/python-reverse-reversed/ 이 블로그를 참고하여 더 자세하게 보면 좋을 것 같다.)

(+ return값에 대한 논의는 https://velog.io/@chae-heechan/Python-reverse-reversed-%EC%B0%A8%EC%9D%B4 여기서 체크)

 

 

-끝-