파이썬 알고리즘 20일차

드디어 20일차다! 꽤나 꾸준히 하는걸...? 좋아 좋아 ~~~ 오늘 문제도 못 맞췄다 ^_^ 그럴 수도 있지...

1406: 에디터

1. 내 풀이: 실패

import sys

string = list(sys.stdin.readline().strip())
N = int(sys.stdin.readline())

loc = len(string)
present_loc = loc

for _ in range(N):
    order = sys.stdin.readline().strip().split()
    if order[0] == 'L': # 뒤로 가기
        if present_loc == 0:
            continue
        else:
            present_loc -=1
    elif order [0] == 'D': # 앞으로 가기
        if present_loc == loc:
            continue
        else:
            present_loc += 1
    elif order [0] == 'B': # 왼쪽에 있던 문자 삭제
        if present_loc == 0:
            continue
        else:
            string.remove(string[present_loc-1])
            present_loc-=1
    else:
        if present_loc == loc: ## 예제 1을 위해서 이걸 고쳐야 함
            string.append(order[1])
            present_loc+=1
        else: 
            string.insert(present_loc, order[1]) #loc 왼쪽에 추가함
            present_loc+=1
    loc = len(string)

for str in string:
    print(str, end='')

오늘은 오류는 안 났고 시간 초과가 났다. 지금 보니 시간 초과날 수 밖에 없네... 사실 이것도 되게 오래 고민해서 푼 거라 시간 초과 문제를 해결할 엄두가 안났다 ^^

일단 문제 접근 방식은 커서의 위치를 present_loc로 설정했다. 예를 들어 문자열 abc가 입력이 된 상태라면 커서는 제일 마지막, c 뒤에 있을 것이고 이는 len(문자열)이다. 그리고 반복문이 끝날 때마다 string이 변하므로 이를 다시 loc에 할당했다. 왜냐하면 P 연산이나 D 연산을 할 때 present_loc와 loc를 비교해줘서 거기에 맞게 if-else 구문을 따라가야하기 때문이다...

틀린 풀이는 여기까지 보는 걸로 하고 ~...

2. 다른 풀이

해당 풀이는 아래의 블로그에서 참고했다.
(출처: https://bnzn2426.tistory.com/112)

from sys import stdin 
stk1 = list(stdin.readline().strip()) 
stk2 = [] 
n = int(input()) 

for line in stdin: 
	if line[0] == 'L': 
		if stk1: stk2.append(stk1.pop()) 
   	else: continue 
    elif line[0] == 'D': 
    	if stk2: stk1.append(stk2.pop()) 
        else: continue 
    elif line[0] == 'B':
    	if stk1: stk1.pop() 
        else: continue 
    elif line[0] == 'P': 
    	stk1.append(line[2]) 
        
print(''.join(stk1 + list(reversed(stk2))))

이 분은 스택이 2개 있다고 생각하셨다. 어짜피 커서는 한 자리씩만 옮겨갈 수 있다. 그러므로 스택으로 생각할 수 있는 것이다. 만약 문자열 abc가 들어왔다고 해보자. 이때 커서는 c 뒤에 있을 것이다.

이 문자열을 stk1에 넣어준다. 만약 여기서 L 연산을 한다면 뒤로 가야한다. 그럼 c를 stk2에 넣어주는 것이다. 이렇게 두 개의 스택을 이용하면 커서의 움직임을 표현할 수 있다.

역시 사람은 배운 걸 써먹어야 한다... 나처럼 맨땅에 헤딩 ㄴㄴ...

오늘도 신기한 알고리즘의 세계 끝!

좋은 웹페이지 즐겨찾기