[프로그래머스] [Python] Level1_체육복

https://programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복

풀이 유형 : 탐욕법(Greedy) 알고리즘

- 내 주변의 것들만 우선 검사하여 답 도출

- 전체 결과의 효율성이 부분 결과의 효율성과 같을 때 사용 가능

1차 시도

def solution(n, lost, reserve):
   	uniform = [1 for i in range(n+2)]
    cnt = 0
    reserve.sort()
    
    for i in lost:
        uniform[i] -= 1
    for i in reserve:
        uniform[i] += 1
    
    for i in range(1,n+1):
        if uniform[i-1] == 0 and uniform[i] == 2: uniform[i-1:i+1] = [1,1]
        if uniform[i+1] == 0 and uniform[i] == 2: uniform[i:i+2] = [1,1]
    
    for i in range(1,n+1):
        if uniform[i] == 0 : cnt +=1          
    return n-cnt

1. uniform이라는 배열을 하나 선언해서 처음엔 전부 1로 초기화

  (이때 앞뒤로 bufffer용도의 1을 넣어줌 <- out of range 에러 방지)

2. lost에 있으면 도난당한 것이니 1 빼고  reserve에 있으면 여분이 있는 것이니 하나 더함

3. uniform초기화 후 앞에가 0이고 내가 2일때, 뒤에가 0이고 내가 2일때 빌려줄 수 있는 경우니 uniform배열 update

4. 마지막 uniform 배열에 값이 0인 애들은 참가 못하는 애들이니 0 갯수를 세서 전체 n에서 빼줌

2차 시도

def solution(n, lost, reserve):
   	uniform = [1]*(n+2)
    reserve.sort()
    
    for i in lost:
        uniform[i] -= 1
    for i in reserve:
        uniform[i] += 1
    
    for i in range(1,n+1):
        if uniform[i-1] == 0 and uniform[i] == 2: uniform[i-1:i+1] = [1,1]
        elif uniform[i+1] == 0 and uniform[i] == 2: uniform[i:i+2] = [1,1] 
    return len([i for i in uniform[1:-1] if x>0])

몇몇 표현을 fancy하게 바꿈

3차 시도

def solution(n, lost, reserve):
    inter = set(lost) & set(reserve)
    lIdx = set(lost) - inter
    rIdx = set(reserve) - inter
    
    for i in sorted(rIdx):
        if i-1 in lIdx: lIdx.remove(i-1)
        elif i+1 in lIdx: lIdx.remove(i+1)
    
    return n-len(lIdx)

set 활용

- inter : 여분 있는데 도난 (체육복 1벌)

- lIdx : 여분 없고 도난 (체육복 0벌)

- rIdx : 여분 있고 도난X (체육복 2벌)

rIdx에 있는 학생 앞뒤에 lIdx에 있는지 확인하여, 있으면 lIdx에서 remove

마지막의 lIdx는 여분 없고 도난당했으나 도와줄 학생이 없는 경우 = 수업 못듣는 학생들