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

💡문제 설명 및 예시

 

• 학생 번호는 체격 순으로 매겨져 있으며, 체육복을 도난당한 학생들과 여벌 체육복을 가진 학생들이 주어집니다.
• 여벌 체육복을 가진 학생은 바로 앞번호나 뒷번호 학생에게만 체육복을 빌려줄 수 있습니다.
• 공통적으로 도난당했지만 여벌을 가진 학생은 우선적으로 제거합니다.
• 남은 여벌 체육복을 가진 학생들이 도난당한 학생들에게 체육복을 빌려줍니다.
• 최대한 많은 학생이 체육수업을 들을 수 있도록 하여 최종적으로 수업을 들을 수 있는 학생 수를 반환합니다.

💡작성코드 1 (오답)

1. 정렬 : lost와 reserve 배열을 정렬하여 번호 순서대로 정렬합니다.

2. 공통 요소 제거: reserve 배열을 순회하면서, 만약 해당 번호가 lost 배열에도 있다면, 두 배열에서 모두 제거합니다. 이는 여벌 체육복을 가져왔지만 도난당한 학생을 제외하기 위함입니다.

3. 체육복 빌려주기: reserve 배열을 순회하면서, 여벌 체육복을 가진 학생이 앞번호나 뒷번호 학생에게 체육복을 빌려줄 수 있는지 확인합니다. 앞번호 학생이 체육복을 도난당했으면 lost에서 제거하고, 그렇지 않으면 뒷번호 학생을 확인하여 제거합니다.

4. 결과 반환: 전체 학생 수 n에서 여전히 체육복을 잃어버린 학생 수 len(lost)를 빼서 체육수업을 들을 수 있는 학생의 최댓값을 반환합니다.

 

코드의 문제점

1. 리스트 수정 중 순회:
   • for i in reserve 루프 내에서 reserve.remove(i)를 사용하여 리스트를 수정하면, 순회 중에 리스트의 크기가 변해 예상치 못한 동작을 초래할 수 있습니다. 예를 들어, 리스트를 수정하면 루프 인덱스가 변경되어 일부 요소를 건너뛰거나 제대로 처리하지 못할 수 있습니다.
2. 효율성 문제:
   • remove 메소드는 리스트에서 요소를 찾고 제거하는 데 O(n)의 시간이 걸립니다. 이 작업이 중첩 루프에서 반복되면 시간 복잡도가 비효율적으로 증가할 수 있습니다.
3. 논리적 결함:
   • 공통 요소를 제거하는 과정에서 두 리스트 모두에서 요소를 제거하면, 다음 체육복 빌려주는 과정에서 이중 제거가 발생할 수 있습니다. 이로 인해 앞번호나 뒷번호 학생에게 체육복을 빌려주는 로직이 제대로 작동하지 않을 수 있습니다.

def solution(n, lost, reserve):
    # 정렬
    lost.sort()
    reserve.sort()

    # lost, reverse 에 공통으로 있는 요소 제거
    # 잃어 버린 학생이 여벌의 체육복을 가져온 학생이면 빌려줄 수 없음
    # 왜 ? 빌려줄 수 없는 학생들을 제거하기 위함
    for i in reserve : 
        if i in lost : 
            lost.remove(i)
            reserve.remove(i)

    # 체육복 빌려주기 (앞번호부터)
    for i in reserve : # 여벌의 체육복을 가져온 학생들
        if i-1 in lost : # 앞번호 학생이 잃어버린 학생이면
            lost.remove(i-1) # True 이면 elif 로 넘어가지 않고 다시 for 문으로 돌아감
        elif i+1 in lost : # 뒷번호 학생이 잃어버린 학생이면
            lost.remove(i+1)
            
    return n - len(lost)

 

💡작성코드 2

1. 집합으로 공통 요소 제거:

• reserve와 lost 배열을 집합으로 변환한 후, reserve와 lost에 모두 있는 요소를 제거합니다.
• reserve_set은 여벌 체육복을 가지고 있지만 도난당하지 않은 학생들만 남깁니다.
• lost_set은 도난당했지만 여벌 체육복을 가지고 있지 않은 학생들만 남깁니다.

2. 체육복 빌려주기:

 

• reserve_set을 순회하면서, 여벌 체육복을 가진 학생이 앞번호(r-1) 또는 뒷번호(r+1) 학생에게 체육복을 빌려줄 수 있는지 확인합니다.
• 빌려줄 수 있다면 lost_set에서 해당 학생을 제거합니다.

3. 결과 반환:

• 전체 학생 수 n에서 여전히 체육복을 잃어버린 학생 수 len(lost_set)를 빼서 체육수업을 들을 수 있는 학생의 최댓값을 반환합니다.

 

 

def solution(n, lost, reserve):
    reserve_set = set(reserve)-set(lost)
    lost_set = set(lost)-set(reserve)
    
    for r in 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)

개선된 코드의 장점

1. 효율성:
   • 집합(set)을 사용하여 공통 요소를 제거하고 체육복을 빌려주는 작업을 수행합니다. 집합의 remove 연산은 평균적으로 O(1) 시간 복잡도를 가지므로, 리스트에서 remove를 사용하는 것보다 훨씬 빠릅니다.
2. 명확한 논리:
   • 공통 요소를 제거한 후 남은 학생들만을 고려하기 때문에, 리스트를 순회하면서 요소를 수정하는 문제를 피할 수 있습니다. 이를 통해 논리적 오류를 방지할 수 있습니다.
3. 코드 간결성:
   • 코드가 간결하고 직관적입니다. 집합을 사용하여 공통 요소를 제거하는 과정이 명확하게 드러나며, 체육복을 빌려주는 과정도 쉽게 이해할 수 있습니다.
4. 안전성:
   • 리스트를 순회하면서 수정하는 문제를 피할 수 있기 때문에, 요소가 누락되거나 중복 제거되는 문제를 방지할 수 있습니다. 이를 통해 코드의 안정성을 높일 수 있습니다.

---

Python 및 Coding적으로 배울 수 있는 것들

1. 집합(set) 연산

집합 자료형을 사용하여 교집합과 차집합 등의 연산을 통해 공통 요소를 쉽게 제거할 수 있습니다. 이는 리스트보다 효율적인 방법으로 요소를 관리할 수 있습니다.

2. 리스트와 집합의 차이점 이해

리스트와 집합의 시간 복잡도 차이를 이해하는 것은 중요합니다. 예를 들어, 리스트에서 remove 연산은 O(n)의 시간이 걸리지만, 집합에서의 remove 연산은 평균적으로 O(1)입니다. 이는 데이터 구조 선택이 성능에 얼마나 큰 영향을 미치는지 잘 보여줍니다.

3. 조건문과 루프 활용

조건문과 루프를 사용하여 문제를 해결하는 과정도 중요한 학습 포인트입니다.

4. 정렬의 필요성

정렬이 필요한 경우와 그렇지 않은 경우를 이해하는 것도 중요합니다. 이 문제에서는 정렬이 필요하지 않지만, 많은 문제에서 정렬은 중요한 전처리 단계가 됩니다.

5. 변수의 범위 및 스코프 이해

함수 내에서 변수의 범위와 스코프를 이해하는 것도 중요한 코딩 스킬입니다. 지역 변수와 전역 변수의 차이를 이해하게 됩니다.

---

알고리즘 문제 종류

1. 그리디 알고리즘 (Greedy Algorithm)

이 문제는 그리디 알고리즘의 좋은 예입니다. 각 단계에서 최적의 선택을 하여 전체 문제의 최적해를 구하는 방법을 배우게 됩니다.

2. 정렬 (Sorting)

비록 이 문제에서는 정렬이 직접 사용되지 않았지만, 다른 많은 문제에서는 정렬이 중요한 역할을 합니다. 정렬 알고리즘을 이해하고 활용하는 능력을 기르게 됩니다.

3. 해시 테이블 (Hash Table)

집합(set)은 해시 테이블을 기반으로 구현되므로, 해시 테이블의 이해와 사용법을 배우게 됩니다. 해시 테이블은 빠른 조회, 삽입, 삭제를 가능하게 합니다.

4. 탐욕법 (Greedy Method)

그리디 알고리즘의 한 예로, 문제를 해결하기 위해 각 단계에서 가능한 최선의 선택을 하는 방법을 배울 수 있습니다.

5. 문자열 및 배열 조작 (String and Array Manipulation)

문자열이나 배열을 조작하여 문제를 해결하는 방법을 배울 수 있습니다. 이는 많은 알고리즘 문제에서 기본적인 기술입니다.

6. 조건부 로직 (Conditional Logic)

조건부 로직을 사용하여 다양한 조건에 따라 다른 동작을 수행하는 방법을 배울 수 있습니다.