프로그래머스 [탐욕법(Greedy)] 체육복(C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 탐욕법 - 체육복

---

문제 링크: 문제 보기

문제 설명:

체육복이 없는 학생이 다른 학생으로부터 체육복을 빌릴 수 있는 최대 학생 수를 구하는 문제입니다. 빌릴 수 있는 조건은 양옆 학생이 여분의 체육복을 가지고 있는 경우로 제한됩니다.

---

문제 해결 코드

#include <string>
#include <vector>

using namespace std;

int arr[31]; // 학생별 체육복 상태를 저장하는 배열

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    // 모든 학생이 체육복을 하나씩 가지고 있다고 초기화
    for (int i = 1; i <= n; i++) {
        arr[i] = 1;
    }
    
    // 체육복을 잃어버린 학생의 체육복 수를 감소
    for (int i : lost) {
        arr[i]--;
    }
    
    // 여분의 체육복을 가진 학생의 체육복 수를 증가
    for (int i : reserve) {
        arr[i]++;
    }
    
    // 학생별로 체육복 상태를 확인하고 대여 처리
    for (int i = 1; i <= n; i++) {
        if (arr[i] > 0) { // 체육복이 있는 학생
            answer++;
            continue;
        }
        // 체육복이 없는 경우, 앞이나 뒤 학생에게 대여 요청
        if (i > 1 && arr[i - 1] == 2) {
            arr[i - 1]--; // 앞 학생의 체육복 사용
            arr[i]++;
            answer++;
        } else if (i < n && arr[i + 1] == 2) {
            arr[i + 1]--; // 뒤 학생의 체육복 사용
            arr[i]++;
            answer++;
        }
    }
    
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 탐욕법(Greedy)을 사용하여 각 학생이 체육복을 최적으로 빌릴 수 있도록 처리합니다. 양옆 학생을 우선적으로 확인하며 대여 여부를 결정합니다.
• 구현 세부사항:
• `arr` 배열은 각 학생이 가진 체육복의 수를 저장합니다. 초기 상태에서 모든 학생은 체육복을 1개씩 가지고 있습니다.
• `lost`에 해당하는 학생은 체육복 수를 1 감소시키고, `reserve`에 해당하는 학생은 체육복 수를 1 증가시킵니다.
• 각 학생을 순회하며 체육복이 없는 경우 양옆 학생에게 대여 요청을 처리합니다. 대여에 성공하면 대여한 학생의 체육복 수를 감소시킵니다.
• 시간 복잡도 분석:
• 체육복 상태 초기화: O(n)
• `lost` 및 `reserve` 처리: O(l + r), 여기서 l과 r은 각각 `lost`와 `reserve`의 크기
• 학생 순회 및 대여 처리: O(n)
• 총 시간 복잡도: O(n + l + r)

---

결과

이 코드는 주어진 입력에서 체육복을 빌릴 수 있는 최대 학생 수를 정확히 계산합니다. 탐욕법을 적용하여 간결하고 효율적으로 문제를 해결합니다.

다른 접근 방식으로, 정렬과 투 포인터를 사용하여 `lost`와 `reserve` 배열을 효율적으로 매칭하는 방법도 고려할 수 있습니다. 이 방식은 선형 탐색을 통해 불필요한 중복 검사를 줄일 수 있습니다.