[프로그래머스] 체육복 - 탐욕법(Greedy)

 

 

문제

 

 

 

작성한 코드

def solution(n, lost, reserve):
    
    students = [0] * (n+2)
    counts = 0
    
    for i in lost:
        students[i] -= 1
        
    for j in reserve:
        students[j] += 1
        
    for k in range(1, n+1):
        if students[k] == 1:
            if students[k-1] < 0:
                students[k-1] += 1
                students[k] -= 1
                
            elif students[k+1] < 0:
                students[k+1] += 1
                students[k] -= 1
    
    for l in range(1, n+1):
        if students[l] >= 0:
            counts += 1
            
    return counts

- n : 학생 수 / lost : 도난 당한 학생들 배열 / reserve : 여분의 체육복 갖고 있는 학생들 배열

- 체육복을 갖고 있다면 0 / 체육복을 갖고 있지 않다면 -1 / 여분의 체육복을 갖고 있다면 1 로 나타낸다.

 

- 학생 수에 +2를 하여 0으로 초기화된 리스트 students를 선언한다.

- 여분의 체육복을 갖고 있는 사람을 기준으로 양옆을 비교한다.

- 처음부터 리스트의 맨 앞, 맨 뒤를 고려하여 임의로 한칸씩 추가해준다.

- 체육복을 갖고 있는 사람 수인 counts를 0으로 초기화 시킨다.

 

- for i in lost:  for문을 통해 lost의 값을 students의 인덱스로 사용하여 1씩 감소시킨다.

- for j in reserve: for문을 통해 reserve의 값을 students의 인덱스로 사용하여 1씩 증가시킨다.

 

- for k in range(1, n+1): 1~n까지의 students 인덱스에 해당하는 값들을 for문으로 비교한다.

- if students[k] == 1: students[k]의 값이 1일 경우 (= 여분의 체육복을 갖고 있을 경우)

- if students[k-1] < 0: 이전 인덱스의 값이 0보다 작다면 (= 체육복을 도난 당한 학생이라면)

  → 인덱스 [k-1]의 값 + 1  /  인덱스 [k]의 값 -1

- elif students[k+1] < 0:  위의 조건을 만족하지 않고, 다음 인덱스의 값이 0보다 작다면 (= 체육복을 도난 당한 학생이라면)

  → 인덱스 [k+1]의 값 + 1  /  인덱스 [k]의 값 -1

 

- for l in range(1, n+1): 1~n까지 for문을 돌리면서 각 인덱스에 해당하는 값이 0보다 크거나 같을 경우 (= 체육복을 갖고 있을 경우) counts의 값을 1씩 증가시키고, counts를 return으로 반환해준다.

 

 

 

+ 다른 사람 코드

def solution(n, lost, reserve):
    reserve_set = set(reserve)-set(lost) 
    lost_set = set(lost)-set(reserve) 
    
    for reserve_person in reserve_set: 
        if reserve_person-1 in lost_set: 
            lost_set.remove(reserve_person-1) 
        elif reserve_person+1 in lost_set: 
            lost_set.remove(reserve_person+1) 
    
    return n-len(lost_set)

set을 사용해서 reserve와 lost에 겹치는 것을 먼저 제거를 한 뒤에 양옆을 비교하는 방식이다.