Python

<Python> 요세푸스 문제

Su_Do 2020. 11. 23. 15:14

문제

[11866번] 요세푸스 문제 0 : www.acmicpc.net/problem/11866

요세푸스 순열을 구하는 문제였다.

이 문제를 풀면서 처음으로 요세푸스 순열을 알게되었고 흥미를 느껴 이 문제를 풀게되었다.

코드

[첫 번째 시도]

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())

list = [i for i in range(1, n + 1)]
lenList = len(list)
cnt = []
result = []
calK = k

while lenList != len(result):
    while calK > len(list):
        calK -= len(list)
    a = list[calK - 1]
    result.append(a)
    cnt.append(a)
    calK += k
    if calK > len(list):
        calK -= len(list)
        for j in range(len(cnt)):
            list.remove(cnt[j])
        cnt = []

print("<", end='')
for i in range(len(result)):
    if i == len(result)-1:
        print(str(result[i]), end='')
    else:
        print(str(result[i])+", ", end='')
print(">")

 

다행히 한 번에 맞았다. 기억이 나지 않지만 예전에 이 문제를 보고 구현해보려고 하다가 실패해서 코드도 남겨두지 않은 채 포기했었는데 이번에는 다행히 성공했다. 하지만 뭔가 내 코드가 복잡해 보였고 한 번 더 성장하기 위해 맞은 사람의 코드를 보기 시작한 뒤 공부하기 시작했다.

알게 된 점

[맞은 사람의 다른 코드]

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())

a = []
q = [i for i in range(1, n + 1)]
c = 0

while q:
    c += k-1
    c %= (len(q))
    a.append(q.pop(c))

print('<%s>' % ', '.join(map(str, a)))

 

맞은 사람의 코드를 본 뒤 내가 푼 방식으로 살짝 고쳤다.

그래도 배울 점이 많았다.

 

[1. while]

while q:
# while len(q) > 0:

 

처음으로 충격 받았던 것은 while문이었다.

while q만 썼는데 while문이 잘 돌아가는 것을 보고 신기했다.

q라는 리스트의 길이가 0이 될 때 break되는 while문이었다.

 

[2. pop]

a.append(q.pop(c))

 

어쩐지 내가 코드를 짜기 너무 힘들었다.

내가 쓴 remove 대신 pop을 써서 간단하게 코드를 짰다.

내가 코드를 짤 때 pop을 잘 쓰지 않고 remove를 쓰는 경우가 많아서 아마 코드가 더 길어지고 복잡해졌던 것 같다.

앞으로 pop을 자주 쓰도록 해야겠다는 반성을 했다.

 

[3. 출력]

print('<%s>' % ', '.join(map(str, a)))

 

내가 가장 궁금했던 부분이었다. 과연 사람들은 출력을 어떻게 했을까...

내 출력문은 되게 길고 복잡했다. 딱 한 줄로 쓰고 싶었다. 그래서 이 부분이 가장 궁금했다.

하나씩 분석해보았다.

 

먼저 join 함수에 대해서 알아보았다.

 

print(', '.join(['3', '6', '2', '7', '5', '1', '4']))
# 3, 6, 2, 7, 5, 1, 4

 

join 함수는 여러 개의 문자열을 하나로 결합해주는 함수다.

문자열을 결합하는데 Separator를 사용하는데 .join 앞에 있는 '' 부분 안에 있는 것이 Separator다.

또한 .join()의 괄호 안에는 String형태로 와야된다.

 

두 번째로는 map에 대해서 알아보았다.

 

map(str, a)
# [3, 6, 2, 7, 5, 1, 4] -> ['3', '6', '2', '7', '5', '1', '4']

 

 map(a, b)에서 a에는 자료형(str, int, double 등)이 오고 b에는 a로 바꿔줄 자료들을 넣는다.

그러면 b형태였던 자료들이 a형태로 바뀌게 된다.

 

n, k = map(int, sys.stdin.readline().rstrip().split())
# n = 첫 번째로 입력된 것을 int로 바꾼 것
# k = 두 번째로 입력된 것을 int로 바꾼 것

 

나는 이렇게 입력을 받을 때만 사용했는데 출력을 하기 위해서도 사용할 수 있다는 것을 알았다.

이렇게 나는 또 한 번 깨달았다.

 

마지막으로 '<%s>' % '문자열'을 알아보았다.

 

print('<%s>' % '안녕')
# <안녕>

 

이런 것을 '서식 지정자'라고 한다.

서식 지정자는 '%자료형' % '문자열'로 생겼다.

자료형은 d(정수), f(실수), s(문자) 등이 있다.

뒤에오는 '문자열'이 앞에 %자료형이 있는 자리에 들어가는 것이다.

 

서식 지정자를 알았으면 <,>를 따로 프린트 하지 않아도 되었다는 것을 깨닫고 성장하는 계기가 되었다.

 

또한 서식 지정자로 소수점을 넣는 경우도 알게되었다.

 

print('%f' % 1.2)
# 1.200000

print('%.2f' % 1.2)
# 1.20

print('%.3f' % 1.2)
# 1.200

 

그냥 %f를 쓸 경우 소수점 아래 6자리까지 표시하고 %.자릿수f를 할 경우 소수점 아래를 자릿수만큼 표시한다.

 

그리고 또 서식 지정자로 문자열을 정렬하는 방법도 알게되었다.

 

print('%10s' % 'hi')
# '        hi'

 

'%길이s' % '문자열'을 하면 문자열을 오른쪽 정렬해서 길이만큼 출력한다.

내가 위에 써 놓은 예시는 공백이 8칸이고 그 다음에 hi를 출력한 것이다.

참고로 공백을 보여주기 위해 ''를 표시했지 실제로는 나오지 않는다.

 

이렇게 서식 지정자를 알게되니 format 함수라는 것도 알게되었다.

물론 이전에 적은 글에서 format 함수를 공부했지만 이 format은 다른 형식의 format이었다. 

 

print('<{}>'.format(', '.join(map(str, a))))
# print('<%s>' % ', '.join(map(str, a)))

 

위의 코드는 서식 지정자로 출력한 것을 format으로도 출력할 수 있다는 것을 보여주는 코드다.

 

사실 format이 서식 지정자 방식보다 간단하다.

'{인덱스}'.format(값) 형태를 기본형태로 가진다.

인덱스는 넣어도 되고 안 넣어도 된다.

그렇기 때문에 들어갈 값이 많으면 인덱스를 넣어서 구분해도 되고 인덱스를 넣지 않으면 순서대로 출력된다.

아래가 예시다.

 

print('{}, {}'.format('a','b'))
# a, b

print('{1}, {0}'.format('a','b'))
# b, a

 

인덱스 대신에 변수로 지정해도 된다.

 

print('{second}, {first}'.format(first = 'a', second = 'b'))
# b, a

 

참고로 중괄호를 출력하려면 {{, }} 처럼 중괄호를 두 번 사용해주면 된다.

 

print('{{ {} }}'.format('hi'))
# { hi }

 

또한 format으로 문자열을 정렬하려면 '{인덱스:<길이}'.format(값) 을 사용하면 된다.

 

print('{0:<10}'.format('hi'))
# 'hi        '

print('{0:>10}'.format('hi'))

# '        hi'

 

<를 사용하면 왼쪽 정렬, >를 사용하면 오른쪽 정렬이다.

물론 이번에도 편이를 위해 ''를 사용했지 출력엔 나오지 않는다.

 

format을 공부하다가 신기한 것을 발견했는데 바로 금액을 출력할 때 천 단위로 ,를 출력할 수 있는 방법이다.

format(숫자, ',')를 사용하면 된다.

 

print(format(1234567890,','))
# 1,234,567,890

 

이렇게 공부를 하고 나니 요세푸스를 공부하다가 서식 지정자와 format에 대해서 더 공부했다.

그래서 더 풀어볼 문제를 뭘 선정해야할지 잘 모르겠다. ㅋㅋㅋㅋㅋㅋㅋ

일단은 요세푸스 문제를 더 풀어봐야겠다.

더 풀어볼 문제

[1158번] 요세푸스 문제 : www.acmicpc.net/problem/1158

[11025번] 요세푸스 문제 3 : www.acmicpc.net/problem/11025

저작자표시 (새창열림)