백준 (1946) - 신입 사원

 

위 문제는 다음의 조건을 따른다

• 적어도 다른 지원자보다 서류 심사 성적과 면접 성적 순위보다 떨어지지 않아야 한다

예를 들어 위의 예제 입력1같이 주어졌다고 가정하면 

서류 심사 성적	면접 성적
1	4
2	3
3	2
4	1
5	5

 

3등이 합격하려면 서류 심사 성적 1,2등보다 면접 성적이 높아야 한다

 

즉 합격하려면 자신보다 서류 심사성적이 높은 사람의 면접 성적보다 높으면 합격임을 알 수 있다

 

이러한 알고리즘을 적용하기 위해 서류 심사 성적에 대해 오름차순 정렬을 수행하였다.

 

function compare(a, b)
{
    return a[0] - b[0];
}
for (let tc = 0; tc < t; tc++)
{
    let n = Number(input[currentLine]);
    let arr = [];
    let arrY = [];
    let cnt = 1;
    for(let i = 0; i < n; i++)
    {
        arr.push(input[currentLine + 1 + i].split(' ').map(Number));
    }
    arr.sort(compare);
    
    //...

 

그다음 해당 인덱스 사람의 면접 성적과 이제까지 검사한 모든 참여자의 면접 성적을 비교했다

    arrY.push(arr[0][1])
    for(let i = 1; i < arr.length; i++)
    {
        let check = false;
        for(let j = 0; j < arrY.length; j++)
        {
            if(arr[i][1] < arrY[j])
                check = true;
            else
                check = false;
        }
        if(check)
        {
            cnt++;
        }
        arrY.push(arr[i][1]);
    }

 

이렇게 작성하니

위와 같은 시간초과가 발생하였다

 

생각해보니 모든 참여자의 면접 성적을 비교하지말고 여태까지 검사한 사람들 중 가장 작은 면접 성적만을 비교하면 된다는 것을 깨달았다

이를 위해서 우리는 오름차순 정렬을 수행한 것이다

어차피 오름차순 정렬으로, 현재 인덱스 이후의 면접성적은 나의 합격에 상관이 없기 때문에, 이전까지 검사한 사람들의 면접 성적보다 하나라도 크면 불합격이기 때문에

    let minY = arr[0][1];
    for(let i = 1; i< arr.length; i++)
    {
        if(arr[i][1] < minY)
        {
            minY = arr[i][1];
            cnt++;
        }
    }

 

다음과같이 O(1)의 비교를 통해 합 / 불을 판단하도록 하였다