문제

Programmers, 체육복

핵심

• 입력의 크기가 $30$이라 구현에 초점을 맞춘다.
• 체육복이 있어야 체육 수업을 들을 수 있다. 여분 체육복을 가져온 학생과 체육복을 도난당한 학생이 있을 때 체육 수업을 들을 수 있는 최대 학생 수를 구해야 한다. 학생들의 번호는 체격 순으로 앞, 뒷번호 학생에게만 체육복을 빌려줄 수 있다.
• 먼저 1번 학생부터 차례로 체육복 여분이 있다면 앞 번호 학생부터 빌려주도록 한다. 그 이유는 예를 들어 1 2 3 4 학생 중 여분이 있는 학생이 1, 3 이고 도난 당한 학생이 2, 4라고 할 때 3번 학생이 2번 학생에게 빌려주었다면 1번 학생의 여분 체육복을 4번에게 빌려줄 수 없기 때문이다. 한 방향으로 빌려주어 중간에 있는 학생에게 효율적으로 빌려줄 수 있도록 구현한다.

개선

코드

시간복잡도

• $O(N)$

C++

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    vector<int> stu(n + 1, 1);
    for (auto e : lost)
        --stu[e];
    for (auto e : reserve)
        ++stu[e];
    for (int i = 1; i <= n; ++i) {
        if (stu[i] == 0) {
            if (i != 1 && stu[i - 1] == 2) { // 앞 번호 학생부터 빌려준다.
                --stu[i - 1];
                ++stu[i];
            } else if (i + 1 <= n && stu[i + 1] == 2) {
                --stu[i + 1];
                ++stu[i];
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (stu[i] >= 1)
            ++ans;
    }
    return ans;
}

Java

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        ArrayList<Integer> stu = new ArrayList<>(Collections.nCopies(n + 1, 1));
        for (var e : lost)
            stu.set(e, stu.get(e) - 1);
        for (var e : reserve)
            stu.set(e, stu.get(e) + 1);
        for (int i = 1; i <= n; ++i) {
            if (stu.get(i) == 0) {
                if (i != 1 && stu.get(i - 1) == 2) {
                    stu.set(i - 1, stu.get(i - 1) - 1);
                    stu.set(i, stu.get(i) + 1);
                } else if (i + 1 <= n && stu.get(i + 1) == 2) {
                    stu.set(i + 1, stu.get(i + 1) - 1);
                    stu.set(i, stu.get(i) + 1);
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            if (stu.get(i) != 0)
                ++ans;
        }
        return ans;
    }
}

태그 - algorithm, hash(사용한 자료구조), boj(플랫폼)