CodeWars 일백 한 번째 문제

Twice linear

public static int dblLinear (int n) {
    	
    List<Integer> ylist = new ArrayList<Integer>();
    ylist.add(1);
    int i = 0;
    int j = 0;

    while(ylist.size() <= n+1) {
        int y = 2 * ylist.get(i) + 1;
        int z = 3 * ylist.get(j) + 1;

        if(y < z) {
            i++;
        } else if(y > z){
            j++;
        } else {
            i++;
            j++;
        }

        ylist.add(Math.min(y, z));
    }

    return ylist.get(n);
}

• 문제도 간단하고 코드도 간단해보이지만 쉽지는 않은 문제였다.
• 두 개의 함수가 서로 같은 해 값을 가질 경우를 대비해서 나는 계속 마지막에 정렬을 하려고 했다.
• 그러나 이 자체가 잘못된 모순이었다.
• y와 z의 결과 값이 다시 x가 되는 구조였기 때문에 y와 z가 겹칠 수가 없었다.
• 그리고 y와 z가 같은 경우는 최소 값을 넣어주면 ylist에는 순서대로 넣을 수가 있었다.
• 나의 코드보다 조금 더 쉽게 푼 Best 코드를 보자.
• TreeSet은 중복은 허용하지 않고 알아서 정렬되어 들어가는 자료구조이다.
• 이를 이용하여 두 개의 함수 결과 값을 넣는데 n번 만큼 돌렸을 때 set에 가장 첫 번째 값(즉, 가장 작은 값)이 문제에서 원하는 n번째 수이다.
• 왜냐하면 알아서 n번째까지 들어가는 수들을 정렬해주면서 set에 들어 있는 가장 작은 수를 통해 두 함수의 결과 값을 만들어주기 때문이다.

public static int dblLinear (int n) {
    TreeSet<Integer> set = new TreeSet<Integer>();
    set.add(1);

    for(int i=0;i<n;i++) {
        int x = set.pollFirst();

        set.add(2*x + 1);
        set.add(3*x + 1);
    }

    return set.pollFirst();
}