프로그래머스 Lv.3) 숫자 게임

Summer/Winter Coding(~2018)

숫자 게임

코딩테스트 연습 - 숫자 게임

풀이

처음에 문제가 쉽다고 생각하고 대충 풀었을 때, 30점 정도 나왔다. 처음 풀고 한 다섯시간 지나서 다시 풀기 시작했는데, 같이 공부하는 형이 풀어던 문제였고, B 배열이 정렬이 안되어 있다는 것을 알았다. ( 물론 혼자 풀었어도 눈치 챘을거다 ^^)

아무튼, 배열 정렬만 해주니까 바로 70점이 되었고, 나머지 30점이 시간 초과였다.

다시 수정하기가 귀찮아서, LinkedList에서 ArrayList로 바꿔주었다. 그러니까 90점이 되었다. 효율성 문제만 다 시간초과가 뜨는 것이다.

 

어떻게 해야하나 생각 중에 인덱스를 저장해놓으면, 검사 시간을 줄일 수 있다는 힌트를 또 들었다.

그래서 인덱스를 저장해주니까 바로 합격이 되었다.

근데, 생각보다 효율이 너무 안좋았고, 인덱스를 저장한다면 승리하는 경우만 체크해도 문제를 풀 수 있다는 생각이 들었다.

그래서 리스트를 지우고, 그냥 배열만 돌면서 확인했다.

결과는 통과했고, 문제의 조건을 다시 생각해보니까 최대 점수만 구하면 되는 문제기 때문에 이기는 최대 경우만 체크하면 되는 것이었다.

덕분에 문제를 바라보는 시각이 조금은 바뀔 수 있을 것 같다.

리스트를 안쓰고도 쉽게 풀 수 있는 방법이 있다면 훨씬 좋기 때문에, 배열로 생각하는 루트도 하나 더 생기게 되었다.

 

로직

 

1. A와 B 배열 모두 오름차순 정렬을 해준다.

2. A 배열을 순차적으로 탐색하면서 하나의 숫자를 가져온다.

3. B 배열을 순차적으로 탐색하면서 최소한의 차이로 이길 수 있는 인덱스의 숫자를 가져오고, 다음 인덱스를 저장하여 다음 탐색에 저장된 인덱스 번호부터 탐색을 시작한다. 

4. 2와 3에서 저장된 answer 리턴

 

 

코드 1

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    public int solution(int[] A, int[] B) {
        ArrayList<Integer> bList = new ArrayList<>();
        Arrays.sort(B);
        for(int num : B) {
            bList.add(num);
        }
        int answer = 0;
        int idx=0;
        for(int a : A) {
            if(bList.get(0) > a) {
                bList.remove(0);
                if(idx-1 >=0) {
                    idx--;
                }
                answer++;
            } else if(bList.get(bList.size()-1) > a) {
                for(int i=idx; i<bList.size(); i++) {
                    if(bList.get(i) > a) {
                        idx =i;
                        bList.remove(i);
                        break;
                    }
                }
                answer++;
            } else {
                if(idx-1 >=0) {
                    idx--;
                }
                bList.remove(0);
            }
        }
        return answer;
    }
}

 

코드 2

import java.util.Arrays;

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

        return answer;
    }
}