프로그래머스: [체육복]

📌 프로그래머스: [체육복]

🔗 문제 링크

---

문제 접근 방식 💡

• 체육복을 도난당한 학생(lost)과 여벌 체육복을 가진 학생(reserve)을 고려하여 최대한 많은 학생이 체육 수업을 듣게 해야 함.
• **도난당한 학생과 여벌이 있는 학생이 겹치는 경우(lost ∩ reserve)**를 먼저 처리.
• 앞뒤 학생에게 빌려줄 수 있도록 greedy 방식으로 해결.

---

Solution 💻

def solution(n, lost, reserve): 
    answer = [1 for _ in range(n)]
    
    for i in lost:
        answer[i - 1] -= 1
    for r in reserve:
        answer[r - 1] += 1
    
    for i in range(n):
        if answer[i] == 0:
            if i - 1 >= 0 and answer[i - 1] == 2:
                answer[i - 1] = 1
                answer[i] = 1
                continue
            if i + 1 < n and answer[i + 1] == 2:
                answer[i + 1] = 1
                answer[i] = 1
                
    result = sum(1 for i in answer if i >= 1)
    
    return result

시간 복잡도 분석 ⏲️

• 리스트 초기화: O(N)
• 도난 및 여벌 체육복 적용: O(N)
• 빌려주는 과정: O(N)
• 최종 연산: O(N)
• 총 시간 복잡도: O(N)

공간 복잡도 분석 🗄️

• 공간 복잡도: O(N),
  • answer 리스트가 필요.

---

리팩토링 🛠️

def solution(n, lost, reserve):
    lost_set = set(lost) - set(reserve)
    reserve_set = set(reserve) - set(lost)

    for r in sorted(reserve_set):
        if r - 1 in lost_set:
            lost_set.remove(r - 1)
        elif r + 1 in lost_set:
            lost_set.remove(r + 1)

    return n - len(lost_set)

리팩토링 후 시간 복잡도 분석 ⏲️

• set 연산(O(1))을 활용하여 중복 제거.
• reserve_set을 순회(O(N))하며 lost_set에서 제거.
• 최종적으로 O(N log N) (정렬 포함).

리팩토링 후 공간 복잡도 분석 🗄️

• 공간 복잡도: O(N),
  • set을 사용하여 lost_set과 reserve_set을 저장.

---

🔹 리팩토링 개선점

1. 리스트(answer)를 사용하지 않고 set으로 중복 제거 및 빠른 탐색 수행 (O(1))
2. 체육복 빌려주는 과정(for r in sorted(reserve_set))을 간결하게 처리
3. 마지막 반환값을 n - len(lost_set)으로 계산하여 추가 연산 제거