체육복Permalink

문제 링크Permalink

체육복

분석Permalink

여분이 있는 학생들은 체육복을 앞 번호와 뒷 번호에게만 빌려줄 수 있습니다.
하지만 여분을 가져왔지만 기존 체육복이 도난 당했다면 빌려줄 수 없습니다.

lost배열과 reserve배열은 정렬된 상태가 아닙니다.

체육복을 도난당한 학생과 여벌의 체육복을 가져온 학생은 최소 1명 이상입니다.

풀이Permalink

#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    // 학생들의 번호가 1부터 시작하므로 배열의 크기도 1 크게 생성
    vector<int> student(n + 1, 0);
    
    // 잃어버린 학생에 대한 값 설정
    for (int i = 0; i < lost.size(); ++i)
    {
        student[lost[i]] -= 1;
    }
    
    // 여분이 있는 학생에 대한 값 설정
    for (int i = 0; i < reserve.size(); ++i)
    {
        student[reserve[i]] += 1;
    }
    
    // 학생들의 번호가 1부터 시작하므로 i는 1부터 시작
    for (int i = 1; i < student.size(); ++i)
    {
        // 현재 학생이 잃어버린 학생인 경우
        if (student[i] == -1)
        {
            // 이전 번호의 학생에 여분이 있는 경우
            if (student[i - 1] == 1)
            {
                student[i] = 0;
                student[i - 1] = 0;
            }
            // 다음 번호의 학생에 여분이 있는 경우
            else if (student[i + 1] == 1)
            {
                student[i] = 0;
                student[i + 1] = 0;
            }
        }
        
        // 체육복을 가지고 있는 학생인 경우
        if (student[i] >= 0)
        {
            ++answer;
        }
    }
    
    return answer;
}

학생들이 체육복을 가진 상태에 대한 값을 가진 student배열을 하나 만들었습니다.
체육복이 없다면 -1의 값을 가지고, 체육복이 있다면 0값을 가지고, 여벌까지 가지고 있다면 1의 값을 가집니다.

이후 학생들을 순회하면서 체육복이 없는 학생의 경우 빌릴 수 있는지 확인하고 빌립니다.
빌린 학생은 체육복을 가지고 있는 값으로 수정하고, 빌려준 학생은 여분이 없다는 값으로 수정합니다.

다음으로 해당 학생이 체육복을 가졌는지 확인합니다.

성능 요약Permalink

시간 복잡도는 $O(n)$입니다.

• student배열 초기화 $O(n)$
• lost를 순회하는 반복문 $O(l)$
• reserve를 순회하는 반복문 $O(r)$
• student를 순회하는 반복문 $O(n)$
• $O(n) + O(l) + O(r) + O(n) = O(2n) + O(l) + O(r)$

공간 복잡도는 $O(n)$입니다.

• student배열의 크기 $O(n)$

테스트 1 〉 통과 (0.01ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 4.14MB)
테스트 4 〉 통과 (0.01ms, 4.15MB)
테스트 5 〉 통과 (0.01ms, 4.12MB)
테스트 6 〉 통과 (0.01ms, 4.14MB)
테스트 7 〉 통과 (0.01ms, 4.21MB)
테스트 8 〉 통과 (0.01ms, 4.15MB)
테스트 9 〉 통과 (0.01ms, 4.21MB)
테스트 10 〉 통과 (0.01ms, 4.16MB)
테스트 11 〉 통과 (0.01ms, 4.18MB)
테스트 12 〉 통과 (0.01ms, 3.67MB)
테스트 13 〉 통과 (0.01ms, 4.13MB)
테스트 14 〉 통과 (0.01ms, 4.13MB)
테스트 15 〉 통과 (0.01ms, 4.21MB)
테스트 16 〉 통과 (0.01ms, 3.66MB)
테스트 17 〉 통과 (0.01ms, 4.07MB)
테스트 18 〉 통과 (0.01ms, 4.02MB)
테스트 19 〉 통과 (0.01ms, 4.21MB)
테스트 20 〉 통과 (0.01ms, 4.21MB)
테스트 21 〉 통과 (0.01ms, 4.02MB)
테스트 22 〉 통과 (0.01ms, 4.21MB)
테스트 23 〉 통과 (0.01ms, 3.63MB)
테스트 24 〉 통과 (0.01ms, 3.67MB)
테스트 25 〉 통과 (0.01ms, 4.14MB)
테스트 26 〉 통과 (0.01ms, 4.21MB)
테스트 27 〉 통과 (0.01ms, 3.63MB)
테스트 28 〉 통과 (0.01ms, 3.63MB)
테스트 29 〉 통과 (0.01ms, 4.12MB)
테스트 30 〉 통과 (0.01ms, 4.18MB)