Lv.3 [시뮬레이션] - 숫자 게임

---

[ 문제 링크 ]

프로그래머스 Lv3. 숫자게임

 

[ 문제 설명 이미지 ]

 

숫자게임

A B 두 팀의 숫자를 순서대로 내서 큰 수를 낸 팀이 승점을 갖게 된다.
숫자가 같은경우 비기는경우는 승점이 없다.

 

A팀은 숫자와 순서가 정해져 있다.

(실제 게임상에서는 B팀이 A팀의 순서는 알지만 순서에 매핑되어있는 숫자는 모른다.)

B팀의 순서를 여러가지로 조합했을 때 얻을 수 있는 최대 승점이 몇인지 구한다.

B팀이 배열될 수 있는 모든 경우의 수를 다 비교해 보고 그 상황에서의 승점들을 구해서 최대값을 구하면 된다.
만약 전체 모든 경우의 수를 다 확인하고, 그 안에서 내가 원하는 값을 찾는 탐색 법으로 풀수 있다.

하지만 B가 최대 승점으로 이긴다는 조건이 있고, 이 조건에 맞는 조합을 재연해 낼 수가 있다.
특정 상황을 재연한다 - 시뮬레이션 한다 라고 한다.

B가 승점을 최대로 가질 수 있는 경우는 B의 숫자가 근소한 차이로 A를 이기는 조건이다.
A의 1을 이기기 위해서는 b의 2만으로도 이길 수 있는데 8이나 6을 사용하는것은 최대 승점을 구할수 없기 때문이다.
그래서 B의 작은 값부터 시작해서 A를 이길수 있는 값들을 하나씩 제거해가면서 승점을 계산하면 쉽게 답을 찾을수 있게 된다.

정렬

비교될 대상A / 비교할 대상B 두가지의 데이터 셋이 있다.

B의 숫자셋을 오름차순으로 정렬한다.

오름차순 정렬하게 되면 작은수부터 순차적으로 조회할 수 있기 때문이다.

A의 첫번째 순서에 해당하는 수를 B의 첫번째 순서부터 오름차순으로 비교해나가며

B의값이 최초로 값이큰 값이 바로 A의 현재 순서의 수 보다 큰 값 중 최소값이 되므로

점수를 증가시키고 다음 순서에서 쓸수 없으므로 해당 인덱스에서 값을 제거한다.

---

[풀이 1] 효율성 테스트 실패

class Solution {
    public int solution(int[] A, int[] B) {
        Arrays.sort(B); //B의 숫자를 오름차순 정렬
        int answer = 0;
        for (int i = 0; i< A.length; i++) {
            for(int j = 0; j< B.length; j++) {
                if(A[i] < B[j]) {
                    answer++;
                    B[j] = 0; // B의 값을 사용할수 없으므로 제거
                    break;
                }
            }
        }

        return answer;
    }
}

 

효율성 테스트 실패 원인은 데이터 원소 갯수가 1 이상 1000000000이하의 자연수 인데,

2중 for문이면 1000000000 * 1000000000 이 되기 때문이다.

---

[풀이 2] 두 비교대상 모두 정렬 

import java.util.stream.IntStream;

public class Solution {

   public int solution(int[] A, int[] B) {
        int answer = 0;
        Arrays.sort(A); //A의 숫자를 오름차순 정렬
        Arrays.sort(B); //B의 숫자를 오름차순 정렬
        int j = B.length-1; // 역순
        for (int i = A.length-1; i>= 0; i--) { // 역순
            if(A[i] < B[j]) {
            	answer++;
                j--
            }
        }
        return answer;
    }

}

두 비교대상을 모두 정렬한다면  2중 for문을 돌리지 않고도 결과를 구할 수 있게 된다.

두 수를 모두 오름차순으로 정렬한 뒤 두수에 대한 비교를 할때 모두 역순으로 비교를 한다면

큰 값부터 차례대로 비교하기 때문에 대상A를 기준으로 B의 값에 대한 `두 수의 차`가 게임에서  이길수있는 가장 근소한 값이 된다

우선 오름차순 된 비교할 대상 B를 역순으로 조회하도록 index로 사용될 변수 j에 B의 길이 -1만큼 저장한다.

다음으로 오름차순 된 비교될 대상 A를 역순으로 조회하도록 for문 조건의범위를 지정한다.

큰 값부터 차례대로 비교했을때 비교조건이 참이 된다면 승리point를 증가시키고 비교할 대상 B의 순서를 역순으로 줄여나간다.

---

[나의 풀이] 오답1 (단순 계산)

public class Solution {

static int answer = 0;
    public int solution(int[] A, int[] B) {
        /* a의 각 요소를 기준으로 B에서의 최소 승리 조건에 해당하는 값(차가 0보다 큰 최소값)을 제거한다. */

        for (int a : A ) {
            for (int b : B ) {
                if(a-b > 0) {
                    answer++;
                }
            }
        }
        List<Integer> collect = IntStream.of(B).mapToObj(Integer::valueOf).collect(Collectors.toList());
        System.out.println("collect.toString() = " + collect.toString());
        for (int a : A) {
            System.out.println("a = " + a);

            if (collect.size() > 0) {
                // 차이중 최소값
                AtomicBoolean result = new AtomicBoolean(false);
                Integer min = collect.stream().filter(b -> {
                    result.set((b - a) > 0);
                    return (b - a > 0);
                }).min(Integer::compareTo).orElse(a);
                if(result.get()) { // 양수이면 1증가
                    answer++;
                }
                System.out.println("min = " + min);
                collect.remove(min);
                System.out.println("collect = " + collect);
            } else {
                break;
            }
        }
        System.out.println("answer = " + answer);
        return answer;
    }
}

무슨 이상한 짓을 하려고 했는지 모르겠다.....

---