[ 이것이 코딩테스트다 ] 8일차

안영우·2021년 1월 4일

동빈나 코딩테스트

[ 이것이 취업을 위한 코딩 테스트다. with 파이썬 ]

목록 보기

8/39

✏️ 서론

2021년을 맞아 처음으로 글을 작성한다.
😃 올해는 취업을 꼭 해야겠다. 😃

✏️ 본론

이번시간에는 순열과 조합을 배워보자.
파이썬에서는 순열과 조합 라이브러리를 기본적으로 제공하고 있으므로 이를 간단히 이용할 수 있다.

순열과 조합은 실제 코딩 테스트에서 필요한 경우가 많기 때문에, 어떻게 사용할 수 있는지를 알고 있어야 한다.
사실 순열과 조합은 재귀 함수 혹은 반복문을 이용해서 직접 구현할 수 있지만, 실제 코딩테스트에서 이를 구현하는것은 매우 번거롭다.
다행히 파이썬3 버전 이상에서는 순열과 조합 기능을 제공하는 라이브러리를 기본으로 제공하고 있기 때문에 걱정하지 말자
(~~파이썬 쵝오~~)

순열이나 조합을 호출해 나온 결과의 원소들은 리스트 형태가 아니기 때문에 이를 손쉽게 다루기 위해서는 리스트로 바꿔줘야 한다.
마지막 결과에 list()를 붙여주자

📍 permutation

순열(permutation): 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것

nPr으로 불림

순서가 의미있을 때 사용함

참고영상: 수학삼촌

import itertools

data = [1, 2]

for i in itertools.permutations(data, 2):
    print(list(i), end= ' ')

👉🏽 [1, 2] [2, 1]

📍 combination

조합(combination): 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것

nCr으로 불림

순서에 의미가 없을 때 주로 사용함.

참고영상: 수학삼촌

import itertools

data = [1, 2, 3]

for i in itertools.combination(data, 3):
    print(list(i), end=' ')

👉🏽 [1, 2][1, 3][2, 3]

✏️ [ 예제 1 ] 백준 1759 (암호 만들기)

문제

조합을 사용하는 대표적인 문제이다.
길이가 l인 모든 암호 조합을 확인한 뒤
최소 1개의 모음과 최소 2개 이상의 자음이 있는 경우를 and로 묶어 출력하면 된다.

처음에 문제를 풀다 막히는 부분이 있었다.
list내의 특정 문자열을 포함 여부를 풀 때 if문을 사용해도 결과가 나오지 않았다.
구글링을 해보니 for문을 돌려 리스트를 벗겨 낸 다음 특정 문자열을 찾으면 된다.

알고리즘 문제를 풀면서 부족하다 느낀건 조건에 정답이 거의 주어져있는데 100% 활용하지 못한다는 점이다.
문제를 좀 더 꼼꼼히 읽어보고 풀어야겠다는 생각을 했다.

import itertools

vowels = ['a', 'e', 'i', 'o', 'u']
l, c = map(int, input().split())

array = input().split()
array.sort()

for password in itertools.combinations(array, l):
    count = 0
    for i in password:
        if i in vowels:
            count = count + 1
    print(count)
    if count >= 1 and count <= l - 2:
        print(''.join(password))

✏️ [ 예제 2 ] 백준 6603

문제

조합에 관한 문제를 하나 더 풀어봤다.
마찬가지로 기능구현은 어떻게 해야하는지 알았지만,
input값을 어떻게 줘야할지 막막했다.
그러던 중 list[0]값과 list[1:]값을 분리하는 식을 알았다.

예를 들어, list의 값이 [1, 2, 3, 4, 5]라고 하자.
그러면, [1]과 나머지 [2, 3, 4, 5]로 분류 할 수 있다.

더욱 쉽게 예를 들어보자.
k, *s = map(int, input().split())일때 input()값을 1 2 3 4 5로 넣게 된다면
k는 1, *s는 [2, 3, 4, 5]가 된다.

또 문제에서 입력 값이 0이면 입력을 더 이상 하지 않는데,
while True문을 사용하여 if의 값이 0 이면 더 이상 입력을 받지 않게 설정하면 된다.

마지막에 출력 값을 list를 벗겨내야하는데 이는, join함수를 사용해서 중간에 ' 공백 '을 넣어주었다.
다만, join을 int 형에 적용 할 수 없기 때문에 문자형(str)으로 바꿔줘야한다.

import itertools

while True:
    k, *s = map(int, input().split())
    s.sort()
    if k == 0:
        break
    for result in itertools.combinations(s, 6):
        print(' '.join(map(str, result)))
    print()