2018. 08. 11 백준 저지 알고리즘 정리(파이썬)

문제 - 1158번 조세퍼스 순열

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

문제

조세퍼스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3)-조세퍼스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ M ≤ N ≤ 5,000)

출력

예제와 같이 조세퍼스 순열을 출력한다.

소스코드

import sys


class Queue():

    def __init__(self, size):
        self.maxSize = size
        self.size = 0
        self.arr = ['']*size
        self.front = -1
        self.rear = -1

    def enqueue(self, data):
        if not self.isFull():
            self.rear = (self.rear+1) % self.maxSize
            self.arr[self.rear] = data
            self.size += 1

    def dequeue(self):
        if not self.isEmpty():
            self.front = (self.front + 1) % self.maxSize
            self.size -= 1
            return self.arr[self.front]

    def isEmpty(self):
        return self.size == 0

    def isFull(self):
        return self.size == self.maxSize

    def __bool__(self):
        return self.isEmpty()



a, b = map(int, sys.stdin.readline().strip().split())

people = Queue(a)

for i in range(1, a+1):
    people.enqueue(str(i))

result = '<'

while not people.isEmpty():
    for i in range(b-1):
            people.enqueue(people.dequeue())
    result += str(people.dequeue())
    if not people.isEmpty():
        result += ', '
    else:
        result += '>'


sys.stdout.write(result)

코멘트

queue를 구현할 때, dequeue를 pop(0)으로 구현했었는데, pop(0)을 사용하면 결국 list 전체가 대이동(?)을 하게 되므로 O(N)의 시간복잡도가 발생한다. 절대로 사용하면 안 된다고 함. 그리고 collections에 deque가 구현되어 있으므로 이걸 사용해도 무난할 듯하다.

이번에 알게 된 사실인데, 파이썬에서 input() 사용은 최대한 피해야 한다. 상당한 시간 차가 난다고. 대용량의 입력이 들어갈 것을 생각하면 stdin.sys.readline()을 쓰는 것을 추천한다. 이 경우엔 뒤의 \n까지 같이 들어가버리니 strip() 혹은 rstrip()을 사용해주면 개행문자가 제외된 입력값을 얻을 수 있다. 단, 이는 공백값까지 전부 날려버리니 상황을 잘 보고 사용할 것.

문제 - 10820번 문자열 분석

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

문제

문자열 N개가 주어진다. 이 때, 문자열에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하는 프로그램을 작성하시오.

각 문자열은 알파벳 소문자, 대문자, 숫자, 공백으로만 이루어져 있다.

입력

첫째 줄부터 N번째 줄까지 문자열이 주어진다. (1 ≤ N ≤ 100) 문자열의 길이는 100을 넘지 않는다.

출력

첫째 줄부터 N번째 줄까지 각각의 문자열에 대해서 소문자, 대문자, 숫자, 공백의 개수를 공백으로 구분해 출력한다.

소스코드

import sys


def check_ord(x):
    global huddle
    for (i, cmp) in enumerate(huddle):
        if x >= cmp:
            return i
    return 3


result = ''
huddle = [ord('a'), ord('A'), ord('0')]

for l in sys.stdin:

    character = [0] * 4
    for e in list(l):
        if e == '\n':
            break
        character[check_ord(ord(e))] += 1
    character = list(map(str, character))
    sys.stdout.write(character[0] + ' ' + character[1] + ' ' + character[2] + ' ' + character[3] + '\n')

코멘트

이상하게 stdin 때문에 시간초과가 자꾸 났던 이상한 문제다. 원래 sys.stdin.readline()으로도 해결이 되었었는데, 고민끝에 sys.stdin()으로 바꾸니 통과가 됐다.

sys.stdin()을 for문과 같이 쓰게 되면, pc에서 실행할 때는 애플리케이션이 강제종료 될 때까지 계속 작동하며 input을 기다리게 된다. 그러나 백준 저지에서는 입력이 끝나자마자 stdin이 닫히므로 프로그램이 정상적으로 종료가 되는 듯하다. 그러나 이 방법이 다른 알고리즘 테스트에서도 먹힐지는 의문이다. 도대체 readline()과 아닌 것의 차이가 뭔지 모르겠다.

문제 1406 - 에디터

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

문제

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

L 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)

D 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)

B 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)

삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임

P $ $라는 문자를 커서 왼쪽에 추가함

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 N(1≤N≤500,000)이 주어진다. 셋째 줄부터 N개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

소스코드

import sys

left = []
right = []

word = list(sys.stdin.readline().strip())
num = int(sys.stdin.readline())

left = word

for i in range(num):
    line = sys.stdin.readline().split()

    if line[0]=='L':
        if left:
            right.append(left.pop())
    elif line[0]=='P':
        left.append(line[1])
    elif line[0]=='D':
        if right:
            left.append(right.pop())
    elif line[0]=='B':
        if left:
            left.pop()

right.reverse()
sys.stdout.write(''.join(left) + ''.join(right))

코멘트

input() 사용했다가 시간초과 뜨고 대차게 말아먹었던 첫 케이스다. 원래는 join 사용이나 reverse 사용 때문에 시간 초과가 생겼던 게 아닐까 하는 의문이 들었으나, stdin 부분만 해결하고 나니 바로 통과가 됐다. 물론 join을 안 쓰고 다른 방법을 찾으면 더 빨라질 수는 있을 것이다.