[프로그래머스] Lv.1 체육복

Python3

문제

제한 사항

입출력 예시

나의 풀이 (시도)

• n에서 lost 배열의 개수만큼을 뺀다 (이 사람들은 무조건 수업 들을 수 있음)
• lost와 reserve 배열 원소를 서로 빼고 절댓값 1이면 +1 카운트한다
• 카운트된 총 사람 수를 리턴한다

→ 문제점: lost, reserve 배열의 크기가 같지 않은 경우도 있어 문제 발생

def solution(n, lost, reserve):
    answer = 0
    
    for i in range(len(reserve)-1):
        print(reserve[i], lost[i])
        if abs(reserve[i] - lost[i]) == 1:
            answer += 1
            print(answer)
    
    answer = answer + n - len(lost)
    return answer

주요 포인트

중복이 없다

→ lost와 reserve 내 원소값이 unique하다. ( [1, 1, 3], [3, 3, 4, 5] 불가)

여벌의 체육복이 있는 학생도 도난당했을 수 있다

→ lost에 reserve값이 공통적으로 존재할 수 있다. lost에 있는 reserve 학생은 체육복을 빌려줄 수 없다. 그래서 둘이 같은 값이 있으면 제외시켜야 한다.

set_reserve = set(reserve) - set(lost)
set_lost = set(lost) - set(reserve)

lost=[2, 4] reserve=[3, 5] 면 누구한테 줘야 할까

오른쪽 사람한테 준다고 가정하면, 3번은 4번에게 주고 5번은 아무에게도 주지 못하며 2번은 아무에게도 받지 못한다.

한편 왼쪽 사람에게 주면 2, 4 모두가 받을 수 있음!

→ 그리디 알고리즘을 사용해야 함을 알 수 있음
왼쪽 사람(reserve의 i-1 요소)에게 주고 없으면 오른쪽으로

최종 코드

def solution(n, lost, reserve):    
    # 여벌 체육복 가져온 학생도 도난당했을 수 있음 전처리
    set_reserve = set(reserve) - set(lost)
    set_lost = set(lost) - set(reserve)
    
    for i in set_reserve:
        # 왼쪽부터 판단
        if i-1 in set_lost:
            set_lost.remove(i-1)
        # 왼쪽을 못 주면 오른쪽 판단
        elif i+1 in set_lost:
            set_lost.remove(i+1)
    
    # 줄 수 있을 만큼 주고 전체 학생 수에서 못 빌린 학생 수를 빼면 체육 수업을 들을 수 있는 총 학생 수 출력
    return n - len(set_lost) 

.
.
.
(이거 근데 왜 예쁘게 정리가 안 되는 거지 .. 어렵다)