소프티어

300, 301~599, 600, 601~ 로 분리해서 생각

정렬 없이, 계수 정렬 개념 활용

const fs = require('fs');
const input = fs.readFileSync('input.txt', 'utf8').trim().split(/\n+/);
const tasksList = []
for (let i = 2; i < input.length; i += 2) {
    tasksList.push(input[i].trim().split(/\s+/).map(Number));
}


const output = []


tasksList.forEach((tasks) => {
    let serverCount = 0


    const array = Array.from({length: 901}, () => 0)


    tasks.forEach(task => {
        if (task > 600) {
            serverCount++
        }
        else {
            array[task]++
        }
    })
    let index1 = 449
    let count1 = 0
    let index2 = 451
    let count2 = 0


    // 450 처리
    if (array[450] > 0) {
        // 450 을 2개씩 짝 만들기
        serverCount += Math.floor(array[450] / 2)
        // 짝이 안된 것은 더하기
        count2 = array[450] % 2
        array[450] = 0
    }


    // 301~449 450~599 처리
    while (300 < index1 && index2 < 600) {
        // count1에 저장된 것은 새로 만난 count2와는 합쳐질 수 없다
        // 왜냐면 새로만난 count2는 새로 또는 그 이후에 만나는 count1 만 결합이 되기에
        count2 += array[index2]
        if (0 < count2 && 0 < array[index1]) {
            if (count2 <= array[index1]) {
                serverCount += count2
                array[index1] -= count2
                count2 = 0
            }
            else {
                serverCount += array[index1]
                count2 -= array[index1]
                array[index1] = 0
            }
        }
        // 남는 건 저장했다가 count1 끼리 합치기
        count1 += array[index1]
        index1--
        index2++
    }
    // 이것을 거치면 count1, count2 모두 0 이거나, 둘 중 하나만 0 이 되는 상태
    // count2 는 서로 합치는것 불가능.
    // 600을 count2에 추가
    // count2가 남아있는 상태
    count2 += array[600]
    if (count2 > 0) {
        // count2끼리는 합칠 수 없으니, 일단 서버를 1개씩 준다
        serverCount += count2
        // 300을 저 서버에 1개씩 추가 해준다.
        // 나머지 count2는 각자 서버로 설정
        if (count2 > array[300]) {
            // 300은 전부 사용 했으니 0
            array[300] = 0
        }
        // 300으로 커버가 된다
        else {
            // 커버 한 만큼 300 줄이기
            array[300] -= count2
        }
        count2 = 0
    }


    // count2는 다 처리 했음.
    // count1을 처리하기 전에 남은 300 처리
    // 남아있는 300이 3개 이상이면, 3개 묶어서 서버 1개 처리
    serverCount += Math.floor(array[300] / 3)
    array[300] = array[300] % 3
    count1 += array[300]


    // 나머지 301~449과 0 또는 1 또는 2개의 300
    // 어느 2개를 선택해서 서버 1개를 만들면됨. 2개 선택한건 무조건 900 이하
    if (count1 > 0) {
        // 나머지 몫과 혼자 있어야하는 1개
        serverCount += Math.floor(count1 / 2) + count1 % 2
    }
    output.push(serverCount)
})


console.log(output.join('\n'))






/*
# 입력 분석
테스트 케이스 개수 1 ~ 1,000
서비스의 개수 1 ~ 100,000
서비스의 크기 300 ~ 900
모든 테스트 케이스의 서비스의 개수 ~ 200,000


# 설계
서비스의 크기가 300~900사이
한 서버에 최대 3개, 이것은 300 300 300의 경우에만 가능
그 외에는 무조건 2개
따라서


 */