[알고리즘] 프로그래머스 | 체육복 lv.1

체육복

답: 

def solution(n, lost, reserve):
    real_lost = sorted(list(set(lost) - set(reserve)))
    real_reserve = sorted(list(set(reserve) - set(lost)))   
    
    # lost에 들어있는 요소 -1혹은 +1이 reserve에 있는지 확인
    for l in real_lost:
        if (l-1) in real_reserve:
            real_reserve.remove(l-1)
        elif (l+1) in real_reserve:
            real_reserve.remove(l+1)
        else:
            n -= 1
    return n

 

 

문제 분석 및 해석

 

일부 학생이 체육복을 도난 당함

여벌 체육복이 있는 학생이 빌려주기로 했는데, 체격 차로 바로 앞/뒤번호만 빌려줄 수 있다

 

전체 학생 수 n, 체육복 도난 학생 번호 lost, 여벌 체육복 학생 reserve

체육수업을 들을 수있는 학생의 최댓값 return

n.   lost.  reserve.   return

5 [2, 4] [1, 3, 5] 5

 

- 전체 학생 2명 이상 30명 이하

- 도난 1명 이상 n명 이하 (최소 1명 혹은 모든 학생이 도난당했을 경우도 있는 듯!)

- 여벌 체육복이 있는 학생은 중복 번호가 없다, reserve에 있어야만 빌려줄 수 있다

- 여벌 체육복이 있는 학생도 도난 학생일 수 있다 = 이 경우는 자신이 사용해야함

 

 

>> 풀이생각 1번

n명의 학생 dictionary를 만든다

 

lost 학생 중 reserve에 있는 학생을 빼서 진짜 lost를 구한다. 

마찬가지로 reserve에 있는 lost학생을 빼서 진짜 reserve학생을 구한다.

 

체육복이 있는학생은 1, 여벌인 학생은 2, 진짜 lost학생은 0으로 value를 설정

 

key값으로 value를 확인하여 빌려줄수 있는지 확인하고 값을 옮겨준다.

맨 앞 +1 -1

 

체육복이 1개 이상인 학생을 확인 해당 값을 return해준다

 

해당 풀이로 풀어보았는데, 런타임에러가 좌좌ㅏ작 뜨는것을 보고 풀이를 바꾸기로 생각함..

def solution(n, lost, reserve):
    answer = 0
    student = {}
    # n명의 학생 dictionary를 만든다
    for i in range(1, n + 1):
        student[i] = 1
    #print(student) #{1: 1, 2: 1, 3: 1, 4: 1, 5: 1}
    
    # lost 학생 중 reserve에 있는 학생을 빼서 진짜 lost를 구한다. 
    # 마찬가지로 reserve에 있는 lost학생을 빼서 진짜 reserve학생을 구한다.
    lost = list(set(lost) - set(reserve))
    reserve = list(set(reserve) - set(lost))   
    # print(lost) # [2, 4]
    # print(reserve) # [1, 3, 5]
    
    # 체육복이 있는학생은 1, 여벌인 학생은 2, 진짜 lost학생은 0으로 value를 설정
    for i in range(1, n + 1):
        if i in lost:
            student[i] -= 1
        if i in reserve:
            student[i] += 1
    # print(student) 
    # {1: 2, 2: 0, 3: 2, 4: 0, 5: 2}
    # {1: 1, 2: 0, 3: 2, 4: 0, 5: 1}
    
    # key값으로 value를 확인하여 빌려줄수 있는지 확인하고 값을 옮겨준다.
    # 맨 앞부터 +1값에 더해줄 수 있는지? 마지막은 -1
    
    ##다시 생각 0인 애를 찾아서 key-1 key+1 의 value가 2인지 확인하고 값 옮기기
    for key in student:
        if student[key] == 0:
            if student[key+1] == 2:
                student[key] += 1
                student[key+1] -= 1    
            elif student[key-1] == 2:
                student[key] += 1
                student[key-1] -= 1
    print(student)
    
    # 체육복이 1개 이상인 학생을 확인 해당 값을 return해준다
    for value in student.values():
        if value >= 1:
            answer += 1
    return answer

 

 

 

 

 

>> 풀이생각 2번

lost에 있는 값의 +1 혹은 -1 값이 있는지 if elif로 한 번에 묶어 확인,

진짜 여벌옷이 있는 학생 목록에서 지워주기.

else인 경우는 아예 없는 것이니 참가할 수 없음 = 전체 학생에서 -1

 

# lost에 들어있는 요소 -1혹은 +1이 reserve에 있는지 확인
for l in real_lost:
    if (l-1) in real_reserve:
        real_reserve.remove(l-1)
    elif (l+1) in real_reserve:
        real_reserve.remove(l+1)
    else:
        n -= 1
return n

 

 

 

 

리뷰.

 

lv.1은 너무 복잡하게 생각하지 않아도 된다는 사실...

dictionary고 depth가 깊어지지 않아서 될줄알았는데 런타임 에러 및 실패가 떠서 슬펐다..

 

고친 식이 훨씬 간결하고 작성하기도 쉬웠지만 뭔가 패배..

 

 

 

 

---

 

 

탐욕알고리즘이란 그때그때 상황에 맞는 최적의 선택을 하는 알고리즘을 말한다.

개념이므로 알고리즘 식은 없음! 알아두자!

 

 

 

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬