[프로그래머스] 체육복

문제

풀이

level1 문제답게 쉬운 문제입니다.

1. 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있으므로 중복된 요소는 제거합니다. 
2. 체육복을 빌릴 수 있는 학생을 찾습니다.
3. 최종적으로 수업을 들을 수 있는 학생 수를 구합니다.

 

 

코드

그리디 문제답게 처음에는 좀 멍청하게 풀고 이후에 개선하였습니다.

 

초기 풀이법

초기에는 lost와 reserve 리스트를 반복하면서 일치하는 항목을 제거하는 방식을 사용했었습니다.
그 후, lost 리스트의 학생들에게 체육복을 빌려줄 수 있는 학생을 reserve 리스트에서 찾아 제거하는 방식으로 문제를 해결했습니다.

def solution(n, lost, reserve):
    reserve.sort()
    lost.sort()
    remove_count = 0
    to_remove = []

    for i in lost:
        if i in reserve:
            to_remove.append(i)
            reserve.remove(i)

    for i in to_remove:
        lost.remove(i)

    for i in lost:
        if i - 1 in reserve:
            reserve.remove(i - 1)
            remove_count += 1
        elif i + 1 in reserve:
            reserve.remove(i + 1)
            remove_count += 1

    return n - len(lost) + remove_count

1. reserve.sort()와 lost.sort()
   • 각각 시간 복잡도는 O(n log n)
2. 첫 번째 for 루프: O(n^2)
   • i in reserve는 O(n)의 시간 복잡도를 가지며, reserve.remove(i)도 O(n)의 시간 복잡도를 가집니다. 따라서 이 루프의 전체 시간 복잡도는 O(n^2)
3. 두 번째 for 루프: O(n^2)
   • lost.remove(i)는 O(n)의 시간 복잡도를 가집니다. 따라서 이 루프의 전체 시간 복잡도는 O(n^2)
4. 세 번째 for 루프: O(n^2)
   • i - 1 in reserve와 i + 1 in reserve는 각각 O(n)의 시간 복잡도를 가지며, reserve.remove()도 O(n)의 시간 복잡도를 가집니다. 따라서 이 루프의 전체 시간 복잡도는 O(n^2)

총 시간 복잡도는 O(n^2)입니다

 

 

 

개선

1. set 자료형을 사용하여 lost와 reserve 리스트의 중복 항목을 제거합니다.
2. 이렇게 하면 여벌 체육복을 가져온 학생이 도난당한 경우를 먼저 처리할 수 있습니다.
3. set의 특성을 활용하여 체육복을 빌려줄 수 있는 학생의 번호를 효율적으로 찾아 처리합니다.

def solution(n, lost, reserve):
    set_lost = set(lost) - set(reserve)
    set_reserve = set(reserve) - set(lost)
    sorted_reserve = sorted(set_reserve)

    for r in sorted_reserve:
        if r - 1 in set_lost:
            set_lost.remove(r - 1)
        elif r + 1 in set_lost:
            set_lost.remove(r + 1)

    return n - len(set_lost)

개선된 풀이법의 시간 복잡도는 O(n log n)입니다.

1. set(lost) - set(reserve)와 set(reserve) - set(lost) : O(n)
   • set 초기화는 O(n)의 시간 복잡도
   • 집합의 차집합 연산도 O(n)의 시간 복잡도
   • => 두 연산의 시간 복잡도는 각각 O(n)
2. sorted(set_reserve) : O(n log n)
   • sorted` 함수는 O(n log n)

 

파이썬에서 Set활용법에 대한 글은 아래 링크에서 확인가능합니다.

Understanding and Using Sets in Python

[Python] Understanding and Using Sets in Python

 

 

참고

• 체육복