[프로그래머스/Day 18] 체육복 - bool에서 int 연산까지, 알고리즘 최적화 과정

오늘은 프로그래머스 '체육복' 문제를 풀기 위한 알고리즘 최적화 과정을 정리해 보았습니다.

1. 문제 개요

이 문제는 체육복을 도난당한 학생들에게 여벌 체육복을 빌려주어, 체육 수업을 들을 수 있는 학생 수의 최댓값을 구하는 문제입니다.

체육복은 바로 앞번호나 뒷번호 학생에게만 빌려줄 수 있습니다. 이때, "앞 번호 학생에게 빌릴 수 있으면 바로 빌리고 넘어가는 것"처럼, 매 순간 최적이라고 생각되는 선택(눈앞의 이익)을 하는 것이 전체 결과의 최적해를 보장하기 때문에 그리디(Greedy) 알고리즘으로 분류됩니다.

---

2. 알고리즘 선택 과정

2-1. 첫 번째 접근: bool 자료형

처음 문제를 접했을 때, 가장 직관적인 생각은 "학생이 체육복을 가지고 있는가? (True/False)"였습니다.

• 초기 아이디어: vector을 사용하여 체육복이 있으면 true, 없으면 false로 관리.
• 문제점: 이 문제는 단순히 '있다/없다'의 이분법이 아니라, 3가지 상태가 필요했습니다.
  1. 체육복이 없음 (0개)
  2. 체육복이 있음 (1개) -> 본인만 입음
  3. 여벌이 있음 (2개) -> 빌려줄 수 있음
  • bool로는 '빌려줄 수 있는 학생'과 '그냥 입는 학생'을 구별할 수 없어 자료형을 int로 변경해야 했습니다.

2-2. 두 번째 접근: int 고정 값 할당

세 가지 상태를 표현하기 위해 vector를 사용하고, reserve와 lost 배열을 순회하며 값을 대입(Assignment)하는 방식을 생각했습니다.

• 로직:
  • 기본값 1로 초기화.
  • reserve에 있으면 totalStudent[i] = 2 (고정)
  • lost에 있으면 totalStudent[i] = 0 (고정)
• 직면한 한계 (Critical Case): 문제의 제한사항 중 "여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다." 라는 조건이 발목을 잡았습니다.
  • 만약 3번 학생이 여벌도 있고(reserve), 도난도 당했다면(lost), 실제로는 1벌(본인이 입음)이 되어야 합니다.
  • 하지만 값을 고정으로 대입해버리면, reserve를 먼저 처리하든 lost를 먼저 처리하든, 순서에 따라 덮어씌워져서 0 또는 2라는 잘못된 결과가 나옵니다.
  • 이를 해결하려면 복잡한 조건문(if)을 추가해야 해서 코드가 지저분해집니다.

2-3. 최종 해결: 상태의 상대적 연산 (덧셈/뺄셈)

값을 덮어쓰는 방식이 아니라, 상태를 누적하는 방식으로 관점을 바꿨습니다.

• 해결책:
  1. 모든 학생은 기본 1을 가짐.
  2. reserve 학생은 +1을 수행.
  3. lost 학생은 -1을 수행.
• 이 방식의 장점:
  • 여벌이 있는데 도난당한 학생은 1 (기본) + 1 (여벌) - 1 (도난) = 1이 되어 자연스럽게 '본인 옷만 남은 상태'가 됩니다.
  • 별도의 if 문이나 중복 검사 로직(set 등) 없이, 단순 사칙연산만으로 모든 예외 케이스가 처리됩니다.

단계	인덱스 0	인덱스 1	인덱스 2	인덱스 3	인덱스 4	설명
1. 초기화	1	1	1	1	1	모든 학생 기본 1벌
2. 여벌(+1)	2	1	2	1	2	reserve 반영
3. 도난(-1)	2	0	2	0	2	lost 반영
4. 빌려주기	2	1	1	1	2	1번→2번, 3번→4번 대여

---

3. 구현 코드

#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;

    // 1. 전체 학생을 배열로 받는다.
    // 각 원소는 다음과 같이 저장한다.
    // - 체육복이 있는 학생은 1
    vector<int> totalStudent(n, 1);

    // - 여벌 체육복까지 있는 학생은 +1
    for (int two : reserve)
    {
        ++totalStudent[two - 1];
    }

    // - 체육복을 도난당한 학생은 -1
    for (int zero : lost)
    {
        --totalStudent[zero - 1];
    }

    // 2. 전체 학생을 순회하며 체육복을 도난당한 학생이 있다면,
    const int TOTAL_STUDENT_SIZE = totalStudent.size();
    int lostCount = 0;
    for (int i = 0; i < TOTAL_STUDENT_SIZE; ++i)
    {
        if(totalStudent[i] == 0)
        {
            // - 앞 번호가 여벌 체육복이 있다면 나눠 받는다.
            if(totalStudent[i - 1] == 2)
            {
                totalStudent[i - 1] = 1;
                totalStudent[i] = 1;
                continue;
            }

            // - 뒷 번호가 여벌 체육복이 있다면 나눠 받는다.
            else if(totalStudent[i + 1] == 2)
            {
                totalStudent[i + 1] = 1;
                totalStudent[i] = 1;
                continue;
            }

            // - 빌릴 체육복이 없어 수업을 듣지 못하는 학생 수를 체크한다.
            else
            {
                ++lostCount;
            }
        }
    }

    // 3. 원소값이 0인 원소를 찾아 전체 학생 수에서 뺀다.
    answer = TOTAL_STUDENT_SIZE - lostCount;

    return answer;
}

"체육복을 빌릴 때 '나보다 앞 번호 학생(i-1)'을 먼저 확인하는 것이 중요합니다.

• 우리는 1번부터 n번까지 순차적으로 탐색을 진행합니다. 내 차례(i)가 지나가면, 나보다 앞 번호(i-1) 학생은 더 이상 체육복을 빌려줄 대상이 없거나 빌릴 기회가 사라집니다. 따라서, 이미 지나온 방향(왼쪽)의 자원을 먼저 소모하고, 아직 기회가 남은 뒷 방향(오른쪽)의 자원은 아껴두는 것이 전체적으로 더 많은 학생을 구제할 수 있는 최적의 선택(Greedy Choice)이 됩니다."

---

4. 회고

처음에는 단순히 상태를 표시하려고 했지만, 문제의 특이 조건(여벌+도난)을 처리하기 위해 데이터를 어떻게 모델링하느냐가 중요하다는 것을 깨달았습니다. 값을 '지정'하는 것이 아니라 '연산'함으로써 로직의 복잡도를 획기적으로 줄일 수 있었습니다.

 

시간 복잡도: O(N)

• totalStudent 배열 초기화 및 reserve, lost 순회: O(N)
• 전체 학생 순회하며 빌려주기: O(N)
• 총합: O(N) + O(N) = O(N)

공간 복잡도: O(N)

• 학생 수만큼의 배열(vector) 하나만 사용하므로 메모리 효율적입니다.