[구현] 프로그래머스 '숫자 게임' - js

1. 문제

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

프로그래머스

2. 코드

처음엔 이걸 dp로 풀어야하나, dfs로 풀어야하나 삽질을 하고 있었다...ㅋㅋㅋㅋ A팀의 순서에 목매달아서...

이 문제는 A팀의 순서에 연연할 필요가 없었다. 중요한 개념은 큰 수는 큰 수로 막아야 가장 효율적이라는 것, 이거 하나다.

그래서 내림차순을 하여 비교를 시작하는 것이다.

내림차순 순서대로 비교할 때, 현재 B팀이 가지고 있는 수(B[j])가 A팀이 가지고 있는 수(A[i])보다 작으면 뒤에 남아 있는 B팀 숫자들은 비교 하나 마나 져서 점수를 얻지 못할테니까.

function solution(A, B) {
    A.sort((a, b) => b - a);
    B.sort((a, b) => b - a);

    let j = 0; 
    let answer = 0; 

    for (let i = 0; i < A.length; i++) {
        if (A[i] < B[j]) { // B가 더 클 때 
            answer++; // 점수 증가
            j++; // B를 가리키는 인덱스 증가
        }
        // B[j]가 A[i]보다 크지 않으면 B[j]뒤에 있는 요소들도 A[i]보다 작아서 점수 획득 x
    }

    return answer;
}

 

이해에 참고한 블로그)

https://velog.io/@front/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%88%AB%EC%9E%90-%EA%B2%8C%EC%9E%84

프로그래머스 - 숫자 게임