감전우 2019. 10. 2. 09:00

문제: Picking Numbers

난이도: Easy

 

문제 설명

 주어진 정수형 배열에서 둘의 차가 1이하인 정수 두 가지만을 요소로 갖는 배열 중 길이가 가장 긴 경우의 길이를 출력하여라.

 예를 들어 배열 a = [1, 1, 2, 2, 4, 4, 5, 5, 5]의 경우는 [1, 1, 2, 2], [4, 4, 5, 5, 5] 두 가지 배열이 만들어질 수 있다. 그리고 두 배열 중 가장 길이가 긴 경우는 [4, 4, 5, 5, 5]5이다.

 

문제 해결

소스 코드

    public static int pickingNumbers(List<Integer> a) {

        List<Integer> values = new ArrayList<Integer>();

        int max = 0;

        int maxTemp = 0;

        for(int i = 0; i < a.size(); i++) {

            if(!values.contains(a.get(i))) {

                values.add(a.get(i));

            }

        }

        for(int i = 0; i < values.size(); i++) {

            for(int j = 0; j < a.size(); j++) {

                if(Math.abs(values.get(i) - a.get(j)) <= 1 && values.get(i) >= a.get(j)) {

                    maxTemp++;

                }

            }

            if(maxTemp > max) {

                max = maxTemp;

            }

            maxTemp = 0;

        }

        return max;

    }

해설

 먼저 주어진 ArrayList a에서 값을 하나씩만 뽑아 중복을 제거한 새로운 ArrayListvalues를 만들었다. 그 후 values에 있는 각각의 값들과 a의 값들을 비교해 차가 1이하인 경우마다 maxTemp값을 1 증가시켰다.

 values의 한 값과 a의 모든 값의 비교가 끝날 때마다 maxmaxTemp를 비교하여 maxTempmax보다 크면 max의 값을 maxTemp의 값으로 갱신한다.

 values의 한 값과 a의 값들을 비교하는 if문에서 values의 값이 a의 값보다 크거나 같은 경우를 넣은 이유는 values의 한 값과 차이가 1이하인 조건만 있을 경우 세 가지 값이 선택될 수가 있기 때문이다. 예를 들어 values에서 꺼낸 값이 3이고 a = [2, 2, 3, 3, 3, 4, 5]일 경우 24 모두 3과의 차가 1 이하여서 원래 나와야 할 결과인 [2, 2, 3, 3, 3], 길이 5가 아닌 [2, 2, 3, 3, 3, 4], 길이 6으로 결과가 나올 수 있다.