문제

문제는 아래 링크를 가서 확인하시면 됩니다.
프로그래머스-체육복
(출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges)

어떻게 풀어나갈까?

입출력 분석

입력은 3가지 변수가 들어옵니다.

변수명타입설명
nint전체학생의 수
lost리스트(int)도난당한 학생
reserve리스트(int)여벌이 있는 학생

출력은 체육수업을 들을 수 있는 학생의 최대값(int)을 return 하면 됩니다.

문제분석

일단 결과값에 포함시킬 수 있는 그룹을 나누어 생각해 봅시다.
1. 체육복이 있고, 여벌이 없으며, 도난당하지 않은 학생.
2. 도난당했으나, 여벌의 체육복이 있는 학생.
3. 도난당했으나, 여벌이 없으며, 빌릴 수 있는 학생.

위 조건을 보니 구현할 내용이 매우 많아보입니다. 하지만 전체 집합에서 (1+2+3)의 조건을 가진 집합을 빼면 다음과 같이 정의가 가능합니다.

  1. 도난당했으나, 빌릴 수 없는 학생.

즉, 전체 학생수에서 4의 경우에 해당되는 학생 수를 빼면 됩니다.

프로그램으로 구현할 내용

  1. 도난당했으나, 여벌의 체육복이 있는 학생을 제외
    -> 전체 학생중에서 lost에도 있고 reserve에도 있는 숫자를 각 리스트에 제외 합니다. 그러면 잃어버린 학생과 여벌이 있는 학생의 교집합은 사라집니다.
not_reserve = set(lost) & set(reserve)
lost = set(lost) - set(not_reserve)
reserve = set(reserve) - set(not_reserve)
  1. 1번 과정에서 reserve에 빌려줄 수 있는 학생만 남았으므로 빌려 줄 수 있는 경우의 수를 구합니다. 1명의 학생은 왼쪽과 오른쪽 2가지 경우의 수를 가지며, n명의 학생이 빌려 줄 경우 n2 의 경우의 수를 가지게 되네요.

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)
  1. 이제 전체 학생수에서 빌릴 수 없는 학생이 가장 적은 경우를 빼고 결과를 return 합니다.
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
profile
다시 도약하려 노력해보자

0개의 댓글