[프로그래머스] Level1 | 체육복 - 파이썬(Python) | 그리디(greedy)

 

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

코딩테스트 연습 - 체육복

오늘도 쉬운 문제 하나 풀고 프로그래머스에서 '체육복' 문제를 풀었다.

해당 문제는 탐욕 알고리즘인 그리디(greedy) 알고리즘을 사용하여 푸는 문제이다.

그리디(greedy)알고리즘은 최적해를 구하는 방법으로 여러 경우 중 하나를 결정할 때 그 순간이 최적이라고 생각되는 것을 선택하는 방식이다. 때문에 항상 최적해를 보장해주진 않지만 대부분의 경우 최적해를 찾기 적합한 알고리즘이기도 하다.

 

---

가장 먼저 제한사항 마지막에 적혀있던

• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

이 문장을 먼저 처리해야 할 것 같았다.

 

다음으로 도난당한 번호의 앞 뒤로 여분을 가지고 있는지 없는지 확인하고,

있다면 그 번호에게서 체육복을 빌려 빌린 번호를 lost 리스트에서 제거하는 방식으로 진행했다.

 

첫번째 시도

def solution(n, lost, reserve):
    answer = 0
    
    lost_len = len(lost)
    
    for i in lost :
        if i in reserve :
            reserve.remove(i)
            lost.remove(i)
            lost_len -= 1

    for i in lost :
        if (i-1) in reserve :
            reserve.remove(i-1)
            lost_len -= 1
            
        elif (i+1) in reserve :
            reserve.remove(i+1)
            lost_len -= 1
     
    answer = n - lost_len
               
    return answer

처음 시도했던 방법은 위와 같다. 

lost를 for문으로 반복하여 lost의 원소가 reserve에도 있다면(여벌을 가져온 번호가 도난을 당한 경우) reserve와 lost에서 제거한 후 lost의 길이를 하나 빼주었다.

생각해보니 길이를 굳이 빼주지 않아도 remove로 원소가 제거되면서 줄어들었을텐데 불필요한 부분인 것 같다.

 

같은 원소(여벌을 가져온 번호가 도난을 당한 경우)를 제거했다면,

다시 lost를 for문으로 반복하며 해당 번호의 앞 뒤에 여벌을 가져온 번호가 있는지 if문으로 구분하였다.

해당 조건에 해당하면 여벌을 빌려줬으므로 reserve에서 해당 번호를 제거하고 lost의 길이를 하나 뺐다.

 

코드 실행 시 테스트 케이스 3개(하나 추가 함)는 모두 통과했지만 

채점 후 제출을 눌렀을 땐 테스트 7, 13, 14에서 실패가 떴다.

 

 

두번째 시도

def solution(n, lost, reserve):
    answer = 0
    
    lost_len = len(lost)
    lost_copy = lost[:]
    
    for i in lost_copy :
        if i in reserve :
            reserve.remove(i)
            lost.remove(i)
            lost_len -= 1
        
    
    for i in reserve :
        if (i-1) in lost :
            lost.remove(i-1)
            lost_len -= 1
            
        elif (i+1) in lost :
            lost.remove(i+1)
            lost_len -= 1
    
    answer = n - lost_len
            
    return answer

처음 for문에서 lost에서 remove를 해주면서 lost의 값이 달라지는 것 같았고 이를 방지하기 위해 lost를 copy하여 사용했다. for문을 사용할 땐 copy한 lost_copy로 반복했으며 lost에서 remove를 해주었다.

 

이번에는 reserve에서 for문으로 반복하며 reserve에서 remove를 해주는 것이 아니라 lost에서 바로 remove하도록 했다.

 

코드 실행 시 테스트 케이스 3개 모두 통과했지만 이 코드 또한 채점 후 제출을 했을 땐 테스트 케이스 18, 19가 실패했다.

 

더이상 내가 짠 코드에서 반례를 찾지 못했고 놓치고 있는 것이 뭔지 찾질 못했다. ㅠ...

 

그러다 다른 사람의 풀이를 보면서 set을 이용한 풀이가 있길래 유심히 봤다.

 

 

세번째 시도

set은 공통 요소를 제거해주는 집합이다.

set은 집합이기 때문에 연산이 가능하며, 여기서는 공통 요소 제거하기 위해 집합 연산을 사용한다.

위의 사진처럼 a와 b의 공통요소를 ' - ' 연산자를 사용하여 제거할 수 있다.

이를 lost와 reserve에 적용하면 아래 코드와 같이 사용할 수 있다.

def solution(n, lost, reserve): 
    answer = 0 
    
    reserve_del = set(reserve)-set(lost) 
    lost_del = set(lost)-set(reserve) 
    
    for i in reserve_del: 
        if i-1 in lost_del: 
            lost_del.remove(i-1) 
            
        elif i+1 in lost_del: 
            lost_del.remove(i+1) 
            
    answer = n - len(lost_del)
    
    return answer

공통 요소를 제거해 준 뒤로는 위의 두 코드들과 같은 방법으로 진행된다.

 

이렇게 하니까 모든 케이스가 통과되었고 제출도 되었다.

 

위의 두 코드들과 set을 이용한 코드와 차이점이 무엇일까...? 아직도 찾지 못했다...

어떤 부분에서 틀렸기에 테스트 케이스가 몇 개만 실패했던걸까.... 🤔

 

---

해당 문제 풀이 코드

GitHub - YOOHYOJEONG/algorithm_practice: 알고리즘 공부 및 코딩테스트 준비