문제는 아래 링크를 가서 확인하시면 됩니다.
프로그래머스-체육복
(출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges)
입력은 3가지 변수가 들어옵니다.
변수명 | 타입 | 설명 |
---|---|---|
n | int | 전체학생의 수 |
lost | 리스트(int) | 도난당한 학생 |
reserve | 리스트(int) | 여벌이 있는 학생 |
출력은 체육수업을 들을 수 있는 학생의 최대값(int)을 return 하면 됩니다.
일단 결과값에 포함시킬 수 있는 그룹을 나누어 생각해 봅시다.
1. 체육복이 있고, 여벌이 없으며, 도난당하지 않은 학생.
2. 도난당했으나, 여벌의 체육복이 있는 학생.
3. 도난당했으나, 여벌이 없으며, 빌릴 수 있는 학생.
위 조건을 보니 구현할 내용이 매우 많아보입니다. 하지만 전체 집합에서 (1+2+3)의 조건을 가진 집합을 빼면 다음과 같이 정의가 가능합니다.
즉, 전체 학생수에서 4의 경우에 해당되는 학생 수를 빼면 됩니다.
not_reserve = set(lost) & set(reserve)
lost = set(lost) - set(not_reserve)
reserve = set(reserve) - set(not_reserve)
0~(n2-1)까지를 이를 이진숫자로 표현하여, 0일 경우 x-1, 1일 경우 x+1로 리스트를 만들어 줄 수 있습니다.
만약, 2번과 4번이 여벌의 체육복이 있다고 한다면
이진 경우의수 | 빌려줄 수 있는 학생 |
---|---|
00 | [1, 3] |
01 | [1, 5] |
10 | [3, 3] |
11 | [3, 5] |
이를 위해 이진 경우의수 리스트를 작성해봅시다.
cases = [format(i, "b").zfill(len(reserve)) for i in range(2 ** len(reserve))]
그리고, 경우의 수를 이용하여 가능한 집합을 모두 만들어 봅시다.
for case in cases:
can_lent = set([ x - 1 if bool(int(y)) else x + 1 for x, y in zip(reserve, case) ])
이제 모든 경우의 수를 만들었으니, 각 경우마다, 빌릴 수 없는 학생을 계산해 봅시다.
for case in cases:
can_lent = set([ x - 1 if bool(int(y)) else x + 1 for x, y in zip(reserve, case) ])
not_lent = lost - can_lent
not_lent에는 각 경우마다 빌릴 수 없는 학생이 들어갑니다. 제일 적은 개수가 들어가는 결과를 찾기 위해 min_lost 를 설정하고 해당 값보다 작을경우 변경합니다.
min_lost = len(lost)
for case in cases:
can_lent = set([ x - 1 if bool(int(y)) else x + 1 for x, y in zip(reserve, case) ])
not_lent = lost - can_lent
if len(not_lent) < min_lost:
min_lost = len(not_lent)
answer = n - min_lost
return answer
def solution(n, lost, reserve):
answer = 0
# 여별을 가져왔으나 도난당한 학생을 lost와 reserve에서 제외
not_reserve = set(lost) & set(reserve)
lost = set(lost) - set(not_reserve)
reserve = set(reserve) - set(not_reserve)
# 빌려줄 수 있는 경우의 수
cases = [format(i, "b").zfill(len(reserve)) for i in range(2 ** len(reserve))]
# 빌릴 수 없는 학생이 가장 적은 경우를 계산
min_lost = len(lost)
for case in cases:
can_lent = set([ x - 1 if bool(int(y)) else x + 1 for x, y in zip(reserve, case) ])
not_lent = lost - can_lent
if len(not_lent) < min_lost:
min_lost = len(not_lent)
# 전체학생에서 빌릴 수 없는 학생이 가장 적은 경우를 제외
answer = n - min_lost
return answer