[프로그래머스] 탐욕법 1. 체육복

문제

출처: 프로그래머스

---

풀이

삽질을 많이 했다...

처음에 c++로 했는데, while문 안에서 인덱스를 두 개 사용하여 lost, reserve 배열의 값을 비교하려고 했다. c++의 find()나 python의 in을 사용하는것보다 시간복잡도가 줄어들 것이라고 예상했기 때문이다. 

그런데 과정이 너무 복잡해지고, c++을 사용하는 의미가 없이 c로도 가능한 풀이가 되어가고 있었다. 또 인덱스를 쓰다보니 헷갈려서 시간이 오래 걸리기에 그냥 접고 파이썬으로 새로 풀었다.

 

그렇게 푼 게 다음과 같다.

lost를 작은 쪽부터 시작했으니 reserve도 -1부터 차례로 비교했다. 

이렇게 푸니 두 개의 케이스에서 실패했다.

 

고민해본 끝에 다음 조건에서 틀렸다는 것을 알 수 있었다.

 

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

나는 for문 안에서 도난당한 학생이 여벌체육복을 가진 학생인 경우를 처리했는데, 애초에 체육복이 하나여서 다른 학생에게 빌려줄 수 없는 것이었다. 

처리했으니 상관없다고 생각했는데, 어떤 케이스에서는 순서가 뒤바뀌어 결과에 영향을 미쳤던 것이다.

def solution(n, lost, reserve):
    answer = n
    
    for i in lost:
        if i - 1 in reserve:
            reserve.remove(i - 1)
        elif i + 1 in reserve:
            reserve.remove(i + 1)
        elif i in reserve:
            reserve.remove(i)
        else:
            answer -= 1
    
    return answer

결과

검색해보니 차집합 연산을 아래와 같이 할 수 있었고, 통과했다.

def solution(n, lost, reserve):
    answer = n
    
    lost_ = set(lost) - set(reserve)
    reserve_ = set(reserve) - set(lost)
    
    for i in lost_:
        if i - 1 in reserve_:
            reserve_.remove(i - 1)
        elif i + 1 in reserve_:
            reserve_.remove(i + 1)
        else:
            answer -= 1
            
    return answer

결과

---

시간복잡도

차집합(difference)	first - second	O(len(first)+len(second))
in	list, tuple의 경우	Average: O(n)
in	set, dictionary의 경우 (내부 해시 사용)	Average: O(1), Worst: O(n)

 

참고자료: wiki.python.org/moin/TimeComplexity

TimeComplexity - Python Wiki

m.blog.naver.com/PostView.nhn?blogId=complusblog&logNo=221204308911&proxyReferer=https:%2F%2Fwww.google.com%2F