일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- 완전탐색
- 알고리즘
- Scaling Laws
- English
- LLM
- 데이터분석
- peft
- Generative AI
- 코드트리
- 프로그래머스
- 판다스
- bfs/dfs
- 코딩테스트실력진단
- 이분탐색
- Study
- 파이썬
- 최단경로
- Python
- Coursera
- Fine-Tuning
- 스터디
- 머신러닝
- DP
- 코딩테스트
- 파인튜닝
- speaking
- paper review
- 그래프이론
- 플로이드와샬
- Lora
- Today
- Total
생각하는 아져씨
[BOJ] 1406번 - 에디터 본문
문제
1406번: 에디터
첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수
www.acmicpc.net
🚦 문제 유형
- 자료구조
- 스택
- 연결 리스트
✏️ Solution
이 문제는 시간제한이 0.3초로 매우 짧아서 시간복잡도를 생각하면서 풀어야 한다.
풀이 방법은 3가지를 생각해 볼 수 있다.
- 입력 문자열 리스트에 커서를 추가해서 명령어 대로 수행
- 스택 사용 - 커서를 따로 추가하지 않고 2개의 스택으로 명령어 수행
- 덱 사용 - 커서를 따로 추가하지 않고 1개의 리스트와 1개의 덱으로 명령어 수행
1. 입력 문자열 리스트에 커서를 추가해서 명령어 대로 수행
입력 문자열이 'abcd' 라고 하면 커서를 ' _(underbar)' 로 설정하고 리스트에 추가한 뒤 커서의 현재 위치를 기준으로 명령어를 수행한다.
명령어 L, D, P, P 마다
- 현재 커서 위치 반환(cursor)
- 커서 위치 조건과 비교
- L, D, B, P 명령어 수행
이런 식으로 생각해서 코드를 짰고 코드는 다음과 같다.
# 시간초과
# 주의할 점: 리스트의 insert, delete, remove의 시간복잡도는 O(N) 이다.
from collections import deque
import sys
s = list(sys.stdin.readline().rstrip())
n = int(sys.stdin.readline().rstrip())
order = [sys.stdin.readline().rstrip().split(' ') for _ in range(n)]
order_q = deque(order)
s.append('_')
while order_q:
o = order_q.popleft() # 명령어
if o[0] == 'L':
cursor = s.index('_') # 현재 커서가 위치하는 곳
if cursor == 0: # 현재 커서가 문장의 맨 앞이면
pass
else: # 커서를 왼쪽으로 한 칸 옮김('_'의 위치를 바꿈)
tmp = s[cursor-1]
s[cursor-1] = '_'
s[cursor] = tmp
elif o[0] == 'D':
cursor = s.index('_')
if cursor == len(s)-1: # 현재 커서가 문장의 맨 뒤이면
pass
else: # 커서를 오른쪽으로 한 칸 옮김('_'의 위치를 바꿈)
tmp = s[cursor+1]
s[cursor+1] = '_'
s[cursor] = tmp
elif o[0] == 'B':
cursor = s.index('_')
if cursor == 0:
pass
else:
del s[cursor-1] # 커서 왼쪽에 있는 문자를 삭제함.
else: # P
cursor = s.index('_')
s = s[:cursor] + list(o[1])+ s[cursor:]
s.remove('_')
print(''.join(s))
코드는 잘 돌아가지만 문제점은 시간초과이다.
틀린 곳은 없어보였기에 입력 개수에 따른 리스트 처리의 문제라고 생각했고 의심되는 del, index 함수의 시간복잡도를 찾아보니 O(N) 인 것을 알았다. 이 문제에서는 시간이 0.3초로 매우 짧기 때문에 요소를 삭제, 추가하는 부분에서 시간을 많이 줄여야 한다.
2. 스택 사용 - 커서를 따로 추가하지 않고 2개의 스택으로 명령어 수행
1번의 문제를 해결할 수 있는 방법은 자료구조를 사용하는 것이다.
커서를 나타내는 어떤 문자열을 추가하는 것 없이 2개의 스택 사이에서 append, pop 하는 것만으로도 구현할 수 있다.
스택 1과 스택 2 중간에 투명다리 위치가 커서라고 보면 이해가 훨씬 쉽다.
코드는 다음과 같다.
# 한개의 리스트 대신 2개의 스택을 사용.
import sys
st1 = list(sys.stdin.readline().rstrip())
n = int(sys.stdin.readline().rstrip())
command = [sys.stdin.readline().rstrip().split(' ') for _ in range(n)]
st2 = []
for cmd in command:
if cmd[0] == 'L':
if st1: # 현재 커서가 문장의 맨 앞이면
st2.append(st1.pop())
elif cmd[0] == 'D':
if st2: # 현재 커서가 문장의 맨 뒤이면
st1.append(st2.pop())
elif cmd[0] == 'B':
if st1:
st1.pop()
else:
st1.append(cmd[1])
st1.extend(reversed(st2)) # 스택의 순서 고려
print(''.join(st1))
주의할 점: 스택은 LIFO 구조로 원래 순서로 돌려줘야 하므로 스택 2를 reverse 함수를 부르고 스택 1, 2를 붙여야한다.
만약 reverse를 쓰고 싶지 않다면 deque(덱)을 쓰는 방법도 있다.
3. 덱 사용 - 커서를 따로 추가하지 않고 1개의 리스트와 1개의 덱으로 명령어 수행
방법은 스택과 비슷한데 원소의 삽입, 삭제 명령어만 다르다.
- pop() -> popleft()
- append() -> appendleft()
# 덱(deque) 사용
import sys
from collections import deque
st1 = list(sys.stdin.readline().rstrip())
n = int(sys.stdin.readline().rstrip())
command = [sys.stdin.readline().rstrip().split(' ') for _ in range(n)]
dq = deque([])
for cmd in command:
if cmd[0] == 'L':
if st1: # 현재 커서가 문장의 맨 앞이면
dq.appendleft(st1.pop())
elif cmd[0] == 'D':
if dq: # 현재 커서가 문장의 맨 뒤이면
st1.append(dq.popleft())
elif cmd[0] == 'B':
if st1:
st1.pop()
else:
st1.append(cmd[1])
print(''.join(st1 + list(dq)))
⚙️ Review
난이도 실버 2인데도 정답 비율이 26% 정도인 것을 보니 생각보다 쉽게 풀 수 있는 문제는 아니었다.
문제 설명대로 코드를 구현하는 것은 어렵지 않았지만 시간초과 문제를 해결하는 것은 조금 어려웠다. 아마 자료구조를 활용하는데 익숙치 않아서 그런 것 같다.
이 활용 방법을 잊지말고 다음에 꼭 써먹자
💡 기억할 것 💡
- 리스트의 insert, delete, remove의 시간복잡도는 O(N)이다.
리스트를 다루는 문제에서 시간초과가 난다면 이 부분을 확인해보자. - 리스트의 원소 삽입/삭제는 스택큐를 적절히 사용하면 처리 시간을 줄일 수도 있다.
어느 문제든 자료구조를 잘 활용해보자. - append()는 리스트에 object를 추가하는 것
extend()는 리스트에 객체(리스트, 튜플, 딕셔너리)의 element를 리스트에 appending 시키는 것
헷갈리지 않고 사용하기!
x = [1,2,3]
x.append([4, 5])
print(x)
>>> [1, 2, 3, [4, 5]]
-----------------------
x.extend([4, 5])
print(x)
>>>[1, 2, 3, 4, 5]
'Study > Algorithm' 카테고리의 다른 글
[BOJ] 1012번 - 유기농 배추 (0) | 2023.02.14 |
---|---|
[BOJ] 2075번 - N번째 큰 수 (0) | 2022.10.07 |
[BOJ] 14888 - 연산자 끼워넣기 (1) | 2022.09.08 |
[BOJ] 2615번 - 오목 (0) | 2022.09.08 |
[BOJ] 19598번 - 최소 회의실 개수 (0) | 2022.08.19 |