[이코테] 만들 수 없는 금액

Python으로 코테 준비를 하다가 Java 실력이 너무나 부족한 것 같아서 그냥 Java로 바꿨다.
꽤나 오랫동안 코딩 테스트 준비를 했는데 발전이 없다. 이것은 분명 방법이 잘못 됐다.
기존에 풀고 풀이를 읽고 넘어가는 방식을 벗어나 블로그에 문제 리뷰를 작성하려고 한다.
하루에 적어도 1시간 30분 이상은 알고리즘에 대해 생각하는 시간을 갖자.

첫 문제는 '이코테 p.314 만들 수 없는 금액'이다.
이 문제는 난이도가 낮음에도 불구하고 풀지 못했다.
알고리즘 자체를 이해 못한 것 같다.
이번에도 풀지 못해서 이렇게 리뷰를 적게 되었다.

소스 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        Main main = new Main();
        System.out.println(main.solution());
    }

    private int solution() {
        int n = scanner.nextInt();
        List<Integer> arrayList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            arrayList.add(scanner.nextInt());
        }

        Collections.sort(arrayList);

        int target = 1;
        for (int i = 0; i < n; i++) {
            if (target < arrayList.get(i)) {
                break;
            }
            target += arrayList.get(i);
        }
        return target;
    }
}

코드 리뷰

오름차순으로 정렬하는 것까지는 생각했다.
하지만 그 이후 조합을 사용해서 풀어야하나 고민하다가 아닌 것 같아 결국 답을 봤다.

1부터 순차적으로 증가하는 target을 하나 두고 입력 받은 arraylist와 비교한다.
(target은 우리가 만들 수 있는 금액인가를 확인해주는 변수이다.)

1. target > arraylist.get(i)
   입력 받은 arraylist들로 target을 만들 수 있다.
   이후 target을 증가시킨다.

2. target == arraylist.get(i)
   arraylist.get(i) 하나로 target을 만들 수 있다.
   이후 target을 증가시킨다.

3. target < arraylist.get(i)
   target보다 arralist 값이 크므로 만들 수 없다.
   break

이렇게 조건을 나누어 생각해보면 문제를 풀 수 있다.
생각하기 쉽지 않다...
솔직히 아직도 알고리즘 자체가 완벽하게 이해되지 않는다.
또 다시 돌아와서 풀어보자.

기억할 것

// Arraylist 오름차순 정렬
Collection.sort(arraylist);

// Arraylist 내림차순 정렬
Collection.sort(arraylist, Comparator.reverseOrder());