문제
[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
