[백준][파이썬] 16943번 숫자 재배치

문제 번호 : 16943
문제 출처 : https://www.acmicpc.net/problem/16943

Code

from itertools import permutations

def to_int(t):
    if t[0] != '0':
        pos = 10 ** (len(t)-1)
        tmp = 0
        for i in t:
            tmp += int(i) * pos
            pos = pos // 10
        return tmp
    return -1


a, b = input().split()
b = int(b)
c = -1

numbers = list(permutations(a)
for number in numbers:
    if number[0] == '0':
        continue
    num = int(''.join(number)) # to_int(number)
    if num < b:
        c = max(num, c)

print(c)

Idea

1. a를 순열을 사용해서 만들기 편하게 하기 위해서 int형으로 변환하지 않고 문자열로 입력받는다. (문자열도 iterable이기 때문에)
2. b는 미리 int형으로 형변환을 한다.
3. permutations(a) r 이 생략되었으므로 a의 길이를 인자로 갖는다.
4. 문자로 이루어져 있는 튜플을 숫자로 변환한다.
5. b와 비교해서 작으면 다시 max()로 비교한 후 저장한다.

for 문에서 number 가 튜플 자료형이기 때문에 int(number)를 사용할 수 없어서 처음에는 to_int()라는 함수를 만들어서 사용했다. 그러다가 튜플을 문자열로 바꾸는 방법이 있어서 적용해봤다. 내가 만든 to_int()로 프로그램을 돌렸을 때 시간이 1288ms 가 나왔고 int(''.join(number))를 사용했을 때 432ms 가 나왔다.

''.join(iterable) 은 iterable 자료형의 값들을 모두 이어붙여서 반환해준다. 값들 사이에 문자를 넣고 싶다면 따옴표 사이에 넣으면 된다. 예를 들어'-'.join(['a', 'b','c']) 라는 함수가 있으면 'a-b-c'를 반환한다.

Itertools 순열 조합 라이브러리

알고리즘 문제를 풀다보면 순열이나 조합을 사용해서 문제를 풀 때 더 간단하게 풀 수 있는 경우가 많다. 그럴 때에는 itertools 라이브러리를 사용한다.
itertools 라이브러리에는 사실 순열과 조합 외에도 iterable 자료형을 처리하는 다른 함수들이 존재하지만 가장 자주 쓰이는 것이 순열과 조합이기 때문에 여기서는 순열, 조합을 사용하는 법만 확인한다.
다른 기능을 알고 싶으면 https://docs.python.org/ko/3/library/itertools.html 를 확인하길 바란다.

1. 순열 Permutation

itertools.permutations(iterable, r = None)
순열은 iterable 자료형에서 r 개의 데이터를 뽑아 순서가 있는 형태로 나타낸다.
각각의 sub sequence는 길이가 r 이고 튜플로 이루어진다. 반환형태는 클래스이기 때문에 사용하기 힘들 수 있기 때문에 주로 리스트로 변환을 해주는 것이 편하다. (필수는 아니다.)

from itertools import permutations

data = ['a', 'b', 'c']

result = list(permutations(data))
result2 = permutations(data)
# 두 번째 인자를 넣어주지 않으면 자동으로 r = len(data) 가 된다.
print(result)
print(result2)
for i in result2:
    print(i, end=' ')

| [('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]
<itertools.permutations object at 0x0000020AD7E80EA0>
('a', 'b', 'c') ('a', 'c', 'b') ('b', 'a', 'c') ('b', 'c', 'a') ('c', 'a', 'b') ('c', 'b', 'a') |
| --- |

코드에서 처럼 for 문에서 튜플을 하나씩 가져와서 사용하는 것은 가능하지만 result2[0]같이 직접적으로 객체에 접근하는 것은 불가능하다. 그래서 list로 변환을 해주는 것이 편하다는 것이고 앞으로 나올 combinations, product, combinations_with_replacement 에서는 설명을 생략한다.

2. 조합 Combination

itertools.combinations(iterable, r =None)
조합은 순열은 iterable 자료형에서 r 개의 데이터를 뽑아 순서가 없는 상태로 나열한다.

from itertools import combinations

data = ['a', 'b', 'c']
result = list(combinations(data, 2))    # r = 2 로 설정

print(result)

3. 데카르트 곱(cartesian product)

itertools.product(iterable, repeat = 1)
데카르트 곱은 iterable 자료형에서 repeat 개 만큼을 중복을 허용해서 순열을 만든다고 책에 쓰여져 있기도 하지만 사실 product는 여러개의 iterable 자료형을 입력으로 받아서 가능한 모든 곱을 나타내는 것이다. 다음은 3가지 예시를 보여준다.

from itertools import product

data = ['a', 'b', 'c']
data2 = ['x', 'y']
data3 = range(2)    # [0, 1]
result = list(product(data, repeat=2))

print(result)
print(list(product(data, data2)))
print(list(product(data3, repeat=3)))

| [('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'b'), ('b', 'c'), ('c', 'a'), ('c', 'b'), ('c', 'c')]
[('a', 'x'), ('a', 'y'), ('b', 'x'), ('b', 'y'), ('c', 'x'), ('c', 'y')]
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)] |
| --- |
| 'product(data, repeat=2) 는 사실 product(data, data) 이다. 두 번째 예시에서 보듯이 data에서의 값과 data2에서의 값으로 만들 수 있는 모든 순열을 만들어 내는 것이다. |
| 세 번째 예시는 나중에 이진수를 만들어 낸다면 유용하게 쓰일 것 같아서 적어봤다. |

4. 중복 조합

** itertools.combinations_with_replacement(iterable, r = None)**
중복 조합은 말 그대로 중복을 허용해서 조합을 완성시키는 것이다. 바로 예시로 넘어간다.

from itertools import combinations_with_replacement

data = ['a', 'b', 'c']

result = list(combinations_with_replacement(data, 2))

print(result)

마무리

파이썬 개념 정리는 처음으로 글을 썼다. 백준닷컴 문제를 풀다보니 순열, 조합을 사용하는 것이 많아서 정리가 필요해서 글을 썼다. 파이썬 라이브러리를 직접 찾아보면서 글을 적다보니 시간이 많이 걸렸지만 대충 알고 있던 정보도 올바르게 알게 되어서 시간이 날 때면 라이브러리를 찾아 봐야할 것 같다.
오늘 공부한 내용 중에서 중요했던 것을 되짚어보면서 마무리 하겠다.

• itertools를 import해서 만들어져있는 순열, 조합 함수를 쓰면 쉽게 코드를 작성할 수 있다.
• 순열, 조합의 반환형은 class이기 때문에 list로 변환하면 편하게 쓸 수 있다. 하지만 필수는 아니다.
• product는 단순히 중복 순열만을 위한 함수가 아니지만 알고리즘 상 중복 순열을 만들어내는 능력이 있는 것이다.
• 함수를 제대로 공부하고 싶으면 라이브러리를 참고하자.