[level 1] 체육복 - 42862

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

 

설계

학생 전체 수의 +2 인 사이즈의 int 타입 벡터 변수 students를 선언한다. n+2사이즈인 이유는 나중에 여벌을 빌려주기위해 순회를 할 때 여벌을 가진 학생의 ±1 위치를 확인해야 하기 위함이다. 

 이제 students를 순회 하면서 0이 나온다면 앞자리와 뒷자리 학생을 조회하여 2이면 여벌학생을 1로, 도난당한 학생을 1로 변경한다. 여기서 앞에 사람을 먼저 조회 해야하는데 이유는 그래야 최대한 많은 인원들에게 빌려주는 로직이 되기 때문이다.

 

구현

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int> students(n+2, 1);
    
    for(int l : lost)
    {
        students[l]--;
    }
    
    for(int r : reserve)
    {
        students[r]++;
    }
    
    for (int i = 1; i <= n ; i++)
    {
      if(students[i] == 0)
      {
          if(students[i-1] == 2)
          {
              students[i-1]--;
              students[i]++;
          }
          else if(students[i+1] == 2)
          {
              students[i+1]--;
              students[i]++;
          }
      }
    }

    for(int i = 1; i <= n; i++)
    {
        if(students[i] > 0)
        {
            answer++;
        }
    }
    
    return answer;
}

 

리펙토링 코드

#include <vector>

using namespace std;

// 1. 매개변수 최적화: 배열 복사 비용을 없애기 위해 'const 참조자(&)'를 사용합니다.
int solution(int n, const vector<int>& lost, const vector<int>& reserve) {
    
    // 2. 발상의 전환: 일단 전체 학생(n)이 모두 수업을 들을 수 있다고 가정하고 시작합니다.
    int answer = n; 
    
    // 패딩을 포함한 학생 배열 초기화
    vector<int> students(n + 2, 1);
    
    // 잃어버린 학생과 여벌이 있는 학생의 상태를 기록합니다.
    for(int l : lost) {
        students[l]--;
    }
    for(int r : reserve) {
        students[r]++;
    }
    
    // 메인 로직: 1번부터 n번까지 순회하며 체육복을 빌립니다.
    for (int i = 1; i <= n ; i++) {
        
        // 내가 체육복이 없을 때
        if(students[i] == 0) {
            
            // 앞사람에게 빌리기 시도
            if(students[i - 1] == 2) {
                students[i - 1]--;
                students[i]++;
            }
            // 앞사람이 안 되면 뒷사람에게 빌리기 시도
            else if(students[i + 1] == 2) {
                students[i + 1]--;
                students[i]++;
            }
            // 앞뒤 모두에게 체육복을 빌리는 데 실패했다면?
            else {
                // 3. 최종 루프 생략: 이 학생은 확실히 수업을 못 듣게 되었으므로 정답에서 1을 뺍니다.
                answer--; 
            }
        }
    }
    
    // 별도의 카운팅 루프 없이 바로 정답 반환
    return answer;
}

코딩 테스트를 위한 추가 리팩토링 포인트

1. 매개변수 상수 참조(const vector<int>&)로 메모리 오버헤드 제거

• 이유: 프로그래머스가 기본 제공하는 템플릿은 vector<int> lost처럼 '값 복사(Call by Value)' 형태로 되어 있습니다. 데이터가 작을 땐 상관없지만, 코딩 테스트에서 배열의 크기가 10만, 100만 개로 커지면 함수가 호출될 때마다 배열 전체를 통째로 복사하느라 엄청난 시간과 메모리를 낭비하게 됩니다.
• 해결: 이를 const vector<int>& lost로 바꿔주면, 복사 없이 원본의 주소만 참조하여 속도를 극대화할 수 있습니다. (코딩 테스트의 기본 소양 중 하나입니다.)

2. 변수 추적으로 불필요한 루프(for) 제거

• 이유: 현재 코드는 배열을 세팅하고, 빌려주는 루프를 돈 다음, 마지막에 정답을 세는 루프를 또 돌고 있습니다.
• 해결: 발상을 조금 바꿔서 **"처음에는 N명 모두가 수업을 들을 수 있다"**고 가정(answer = n)해 봅니다. 그리고 체육복을 빌리는 메인 루프에서 끝내 체육복을 빌리지 못한 학생이 발생할 때만 answer에서 1을 빼면 마지막 카운팅 루프를 아예 삭제할 수 있습니다.

---

회고

오늘은 제한사항에 여벌을 가진 학생도 도난을 당할 수 있다는 부분을 확인하지 못하고 빙빙 돌고 말았다. 문제가 길다고 대충보고 제한사항을 간략히 보고 넘어갔는데 이제는 제한사항은 정독 할 필요가 있다고 생각했다.