[Python] 백준 5397 키로거

 

문제 분석

• 입력한 문자는 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표
  
  
• 길이가 L인 문자열이 주어진다.
• '-' : 백스페이스 → 커서 바로 앞에 글자가 존재한다면 그 글자를 지운다.
• '<', '>' : 화살표 → 커서를 움직일 수 있다면, 왼쪽 또는 오른쪽으로 1만큼 움직인다.
• 나머지 문자는 비밀번호의 일부
• 나중에 백스페이스를 통해서 지울 수는 있다.
• 만약 커서의 위치가 줄의 마지막이 아니라면, 커서 및 커서 오른쪽에 있는 모든 문자는 오른쪽으로 한 칸 이동한다.

 

코드 설계

• 현재 커서의 위치 cursor : 커서는 문자의 다음에 위치
  • 가능한 커서의 위치는 0~문자
  • 0 : 맨 왼쪽
  • n : 맨 오른쪽
• 가능한 커서의 위치는 0~문자열 길이 n (총 n+1)
  
  
• 현재 문자가 있고, cursor가 0보다 크면 지울 수 있음
• 문자는 현재 커서 위치의 인덱스에 추가

 

정답 코드

1차 - 런타임 에러

import sys
input = sys.stdin.readline

tc = int(input())

for _ in range(tc) :
    keys = list(input().strip())
    cursor = 0
    ans = []

    for k in keys :
        if k == '<' :
            if cursor <= 0 :
                continue
            cursor -= 1
        elif k == '>' :
            if cursor >= len(ans) :
                continue
            cursor += 1
        elif k == '-' :
            if not ans[cursor-1] : # 값이 있다면
                continue
            del ans[cursor-1]
        else :
            if len(ans) == 0 or (cursor == len(ans)) : # 만약 커서가 맨 뒤에 있다면 append
                ans.append(k)
            else : # cursor의 인덱스에 값 insert
                ans.insert(cursor, k)
            cursor += 1

    print(''.join(ans))

 

2차 - 여전히 런타임 에러

import sys
input = sys.stdin.readline

tc = int(input())

for _ in range(tc) :
    keys = list(input().strip())
    cursor = 0
    ans = []

    for k in keys :
        if k == '<' :
            if cursor > 0 :
                cursor -= 1
        elif k == '>' :
            if cursor < len(ans) :
                cursor += 1
        elif k == '-' :
            if not ans and cursor > 0 :
                    # and not ans[cursor-1]) : # 값이 없으면 지울게 없음
                continue
            del ans[cursor-1]
            cursor -= 1
        # else :
        #     if len(ans) == 0 or (cursor == len(ans)) : # 만약 커서가 맨 뒤에 있다면 append
        #         ans.append(k)
        #     else : # cursor의 인덱스에 값 insert
            ans.insert(cursor, k)
            cursor += 1

    print(''.join(ans))

 

3차 - 시간초과

import sys
input = sys.stdin.readline

tc = int(input())

for _ in range(tc) :
    keys = list(input().strip())
    cursor = 0
    ans = []

    for k in keys :
        if k == '<' :
            if cursor > 0 :
                cursor -= 1
        elif k == '>' : 
            if cursor < len(ans) :
                cursor += 1
        elif k == '-' :
            if ans and cursor > 0 : # ans에 값이 있고 -
                del ans[cursor-1]
                cursor -= 1
        else :
            ans.insert(cursor, k)
            cursor += 1

    print(''.join(ans))

문자열은 최대 100만

 

다른 정답 코드 1

두 개의 스택을 선언해서 풀 수 있다. 커서를 기준으로 왼쪽 / 오른쪽을 나눠 스택을 구현하면 된다.

1.  기본적으로 문자는 입력되면 왼쪽 스택에 넣어준다.
2. 왼쪽 화살표 표시는 '<' 왼쪽 스택에 있는 문자를 오른쪽 스택에 옮겨준다. 단 왼쪽 리스트가 빈 리스트가 아니어야 실행 가능하다. 왼쪽 리스트가 비어있다면 아무 일도 일어나지 않는다.
3. 반대로 오른쪽 화살표 표시는 '>' 오른쪽 스택에서 왼쪽 스택으로 옮겨준다. 마찬가지로 오른쪽 리스트가 비어있다면 아무 일도 일어나지 않는다.
4.  '-' 왼쪽 스택에서 문자를 삭제해준다.
5. 이렇게 실행했을 시 오른쪽 리스트의 순서가 반대로 정렬되기 때문에 마지막 결과를 출력할 때는 reversed()를 이용해 오른쪽 리스트를 뒤집어주고 왼쪽 리스트와 합친다.

t = int(input())

for _ in range(t):
    l_list = []
    r_list = []
    data = input()
    for i in data:
        if i == '-':
            if l_list: #왼쪽 스택에 있을 경우
                l_list.pop()
        elif i == '<': # 왼스택에 있는 문자 오른쪽 스택으로
            if l_list:
                r_list.append(l_list.pop())
        elif i == '>': # 오스택에 있는 문자 왼쪽 스택으로
            if r_list:
                l_list.append(r_list.pop())
        else:
            l_list.append(i)
    l_list.extend(reversed(r_list)) # 오른쪽 스택에 있는 문자들은 뒤집어서 붙여야 한다.
    print(''.join(l_list))