[JS] 숫자게임

그리디 알고리즘을 활용해서 해결하였다.

 

 

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

프로그래머스

 

 

A와 B를 우선 정렬해준다. 이후 각 팀의 가장 쌘놈부터 결투를 시킨다. 

 

문제가 승점의 차가 최대의 격차로 나게하는 것이 아닌 절대적인 승점 자체를 가장 많이 받게 하는 방식이기 때문에 이게 가능하다.

 

B에서 가장 쌘놈을 뽑아서 A에서 가장쌘놈과 싸우면서 이길수 있는 상대가 나올 때까지 선수를 교체시키면서 싸우면 된다. 

 

 

 

조금 생각할 점은 A의 나머지 애들 다 B보다 강한경우에는 승점을 못얻어서 빨리 끝내야 한다. 이를 위해 이중 반복문에서 상위 반복문을 종료시킬 수 있는 JS의 문법을 활용하였다.

 

 

 

 

function solution(A, B) {
    A = A.sort((a,b) => a-b)
    B = B.sort((a,b) => a-b)
    let ret = 0
    
    outer : while(B.length && A.length){
        const bScore = B.pop()
        while(A.pop() >= bScore)
            if(!A.length) break outer //남은 A가 b보다 모두 큰경우
        ret ++
    }
    return ret
    
}