[Java] 프로그래머스 - 숫자 게임

프로그래머스 숫자 게임 문제는 두 팀이 숫자 게임을 해서 한 팀이 얻을 수 있는 최대 승점을 구하는 문제다. 난이도는 레벨3이며 그리디 알고리즘를 통해 해결할 수 있다.

 

프로그래머스 - 숫자 게임 문제 정보

알고리즘 분류

- 그리디

난이도

- Level 3

 

문제 요약

• A팀 N명 vs B팀 N명 숫자 게임
• 모든 사원은 임의의 숫자를 하나씩 부여받는다. (1~10억)
• 모든 사원은 딱 한번씩만 경기한다.
• 경기
  • A 1명, B 1명이 나와서 숫자 비교를 한다.
  • 큰 팀이 1점. 비기면 점수 없음.

Q. A팀의 출전 순서가 공개되었을 때, B팀이 얻을 수 있는 최대 승점은?

 

 

문제 풀이 과정

• N이 10000 이하니까 O(NlogN)까지 가능함 → 정렬 가능
• 무조건 A팀과 차이가 적게 이겨야 한다.
• A팀과 B팀 모두 내림차순 정렬해서… A팀에 이기는 선수만 출전하기
  • 지는것과 비기는것이 동일함 (A팀 점수는 관심 없음)

코드

public int solution(int[] A, int[] B) {
    // 각 팀 선수들을 내림차순으로 정렬
    Integer[] teamA = Arrays.stream(A).boxed().toArray(Integer[]::new);
    Integer[] teamB = Arrays.stream(B).boxed().toArray(Integer[]::new);
    Arrays.sort(teamA, Comparator.reverseOrder());
    Arrays.sort(teamB, Comparator.reverseOrder());

    int playerA = 0, playerB = 0;
    int scoreB = 0;
    while(playerA < A.length && playerB < B.length) {
        // 1. B선수가 이김
        if (teamA[playerA] < teamB[playerB]) {
            scoreB++;
            playerA++;
            playerB++;
        }
        // 2. B선수가 지거나 비김
        // -> 현재 선수가 가장 센 선수. 이길때까지 기다림.
        else {
            playerA++;
        }
    }
    return scoreB;
}

• 시간복잡도: 정렬 O(NlogN) + 비교 O(N)
• 공간복잡도: 팀원들 정렬하는 배열 O(N)