[백준/Python] 5397. 키로거 & 17087. 숨바꼭질 6

1. 백준 5397. 키로거

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

5397번: 키로거

문제

창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다.

키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다. 

강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오. 강산이는 키보드로 입력한 키는 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표이다.

 

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입력했다면, '-'가 주어진다. 이때 커서의 바로 앞에 글자가 존재한다면, 그 글자를 지운다. 화살표의 입력은 '<'와 '>'로 주어진다. 이때는 커서의 위치를 움직일 수 있다면, 왼쪽 또는 오른쪽으로 1만큼 움직인다. 나머지 문자는 비밀번호의 일부이다. 물론, 나중에 백스페이스를 통해서 지울 수는 있다. 만약 커서의 위치가 줄의 마지막이 아니라면, 커서 및 커서 오른쪽에 있는 모든 문자는 오른쪽으로 한 칸 이동한다.

출력

각 테스트 케이스에 대해서, 강산이의 비밀번호를 출력한다. 비밀번호의 길이는 항상 0보다 크다.

import sys
from collections import deque

input = sys.stdin.readline

T = int(input())
for _ in range(T):
    passwords = list(input().rstrip())
    left, right = deque(), deque()

    for p in passwords:

        if p == '-':
            if left:
                left.pop()
        elif p == '<':
            if left:
                right.appendleft(left.pop())
        elif p == '>':
            if right:
                left.append(right.popleft())
        else:
            left.append(p)

    left.extend(right)
    print(''.join(list(left)))

• 접근이 어려워서 황선생님 블로그를 참고했다.
• 투 스택이라는 문제 풀이 방식을 배울 수 있었다.

 

---

 

2. 백준 17087. 숨바꼭질 6

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

17087번: 숨바꼭질 6

문제

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.

수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.

모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 105)과 S(1 ≤ S ≤ 109)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 109)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

출력

주어진 민겸 수가 십진수로 변환되었을 때 가질 수 있는 값 중 가장 큰 값과 가장 작은 값을 두 줄로 나누어 출력한다.

가능한 D값의 최댓값을 출력한다.

import sys
import math

input = sys.stdin.readline


def GCDofTwoNumbers(a, b):  # GCDofTwoNumbers라는 이름의 함수와 매개변수 a, b 정의하기
    while b != 0:  # b가 0이 아닌 동안 반복
        a, b = b, a % b  # a에 b를, b에 a와 b를 나눈 나머지를 교환하여 저장(스왑)
    return a  # 반환되는 a가 두 수의 최대공약수


N, S = map(int, input().split())

young = list(map(int, input().split()))

if N == 1:
    print(abs(S-young[0]))
else:
    for i in range(N):
        young[i] = abs(young[i] - S)

    GCDarr = young[0]  # 리스트의 첫 번째 항목(0번 방)을 GCDarr에 저장
    for i in range(N):  # i가 0부터 리스트의 길이만큼 반복
        GCDarr = GCDofTwoNumbers(GCDarr, young[i])  # GCDarr에 GCDarr과 list[i]의 최대공약수를 저장

    print(GCDarr)  # 반환되는 GCDarr이 리스트의 최대공약수

• 이 문제의 포인트는 여러 숫자에 대한 최대공약수를 구하는 것이었다.
• 최대공약수 구하는 방식을 공부하고 적용하여 해결했다.