[프로그래머스][완전 탐색] 인사고과

     

목차

 

 

문제

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

프로그래머스

 

 

문제 구현 방향

이중순회를 하면 시간 초과로 틀리기 때문에 o(n)으로 해결해야 한다.

그래서 아이디어는 다음과 같다.

 

1. a를 기준으로 내림차순 정렬한다. 

2. b를 기준으로 오름차순 정렬한다.

 

이런식으로 정렬했기 때문에

나는 b만 계속해서 최고값을 갱신해주고 비교해 주면 된다.

예시

4 2 / 4 1 /  3 1 / 3 2 / 3 4 / 2 3

-> 4일때 최대값이 2이므로 3 1은 탈락

-> 3일때 최대값이 4이므로 2 3은 탈락

 

그 후 탈락하지 않은 합만 배열에 추가해 갯수를 세어주면 순위 계산을 할 수 있다.

 

포인트

-> 정렬을 통해 단일 순회 최적화를 할 수 있다.

-> 순위 계산 시 배열에 넣고 계산해 주면된다.

 

코드 구현

function solution(scores) {
    var answer = 0;
    const wonho = scores[0];
    scores.sort((a, b)=> {if(a[0] === b[0])return a[1] - b[1]
    else return b[0]- a[0]});
    let scoreIdx = new Array(200001).fill(0)
  
  
    let maxSum =0;
    let m_b = 0;
    for(let i=0; i< scores.length; i++){
        if(m_b > scores[i][1]){
            if(wonho.join(',') === scores[i].join(','))return -1;
            continue;
        }
        else{
            m_b = Math.max(m_b, scores[i][1]);
        }
        let sum = scores[i][0] + scores[i][1];
        scoreIdx[sum]++;
        maxSum = Math.max(maxSum, sum);
        
    }
    let wSum = wonho[0] + wonho[1];
   
    for(let i=maxSum; i> wSum; i--){
        if(scoreIdx[i]===0)continue;
        answer += scoreIdx[i];
    }
    answer++;
    return answer;
}