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

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

프로그래머스

 

코딩테스트 연습 > Summer/Winter Coding(~2018)  > 모음사전

 

문제 설명

xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다.

먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다.
각 사원은 딱 한 번씩 경기를 합니다.
각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다.
만약 숫자가 같다면 누구도 승점을 얻지 않습니다.
전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 팀원들의 출전 순서를 정했습니다. 이때의 B팀이 얻는 승점을 구해주세요.
A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열 A와 i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열 B가 주어질 때, B 팀원들이 얻을 수 있는 최대 승점을 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

A와 B의 길이는 같습니다.
A와 B의 길이는 1 이상 100,000 이하입니다.
A와 B의 각 원소는 1 이상 1,000,000,000 이하의 자연수입니다.

 

문제 접근

개인적으로 상당히 당황스러운 문제였다. 

문제의 level을 보고 쫄았다고 해야 하나 level3니까 당연히 어려운 로직을 요구할 거라는 생각이 잘못이었다.

 

접근 방법1

먼저 A배열과 B배열을 오름차순으로 정렬 

링크드 리스트에 각각 집어넣었다. addFirst() 메서드를 활용해서 내림차순으로 넣었다.

 for문을 돌면서 2가지 조건으로 실행했다.

 1. A의 현재 숫자가 B의 제일 큰 숫자 보다 크면 B가 가진 숫자 중에서 A를 이길 경우는 없으니 B에서 가장 쓸모없는 제일 작은 숫자를 pollLast()를 통해서 빼주었다.

 2. A의 현재 숫자보다 B의 제일 큰 숫자가 더 크다면 B가 이기는 경우에서 가장 작은 숫자를 for문을 통해서 지웠다.  그리고 answer++

코드1(시간초과) 

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        Arrays.sort(A);
        Arrays.sort(B);
        LinkedList<Integer> list_A = new LinkedList<>();
        LinkedList<Integer> list_B = new LinkedList<>();
        
        // 둘다 내림차순으로 넣기 
        int size = A.length; 
        for(int i = 0; i < size; i++){
            list_A.addFirst(A[i]);
            list_B.addFirst(B[i]);
        }
        
        for(int i = 0; i < size; i++){
             int target = list_A.pollFirst();
             if(target >= list_B.peekFirst()){
                 list_B.pollLast();   
             }
             else{
                 answer++;
                 for(int j = 1; j < list_B.size(); j++){
                      if(target >= list_B.get(j)){
                          list_B.remove(j - 1);
                          break;
                      }
                 }
             }
        }  
        return answer;
    }
}

 

결과1

- 정확성 테스트 전부 통과

- 효율성 테스트 전부 실패 

- 85.7점 

100점이 아니라면 아무 의미 없다.. ㅋㅋ

 

접근 방법2

생각을 해보니까 아주 간단한 방법이 떠올랐다. 

1번 풀이랑 똑같이 오름차순으로 먼저 정렬을 하고 for문을 돌린다.

만약 A보다 현재 B가 더 크면 A의 다음 숫자를 테스트 하기 위해 cnt를 늘려주는 방식으로 검사를 진행하면 
B가 가장 많이 이기는 경우의수가 나온다는 방법이었다.

더 쉽게 설명하면 B의 숫자들이 A를 이기는 숫자들을 가장 작은 수부터 하나씩 확인해 나가는 방법인 것이다.

A가 더 크면 A는 그대로지만 B는 계속 커진다. (물론 1 1 1 1 1 이런 경우는 어차피 못 이긴다.)

코드2(통과)

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        Arrays.sort(A);
        Arrays.sort(B);
        int cnt = 0;    // A idx
        for(int i = 0; i < B.length; i++ ){
            if(A[cnt] < B[i]){
                answer++;
                cnt++;
            }
        }
        return answer;
    }
}

 

결과2

 

 100점!!