[프로그래머스][Java][Lv.2] 숫자의 표현 - 투포인터

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/12924

프로그래머스

 

첫번째 풀이

정확성: 70.8

효율성: 25.0

합계: 95.8 / 100.0

 

1을 안더해줘도 되게끔 sum에 lt변수를 넣어서 초기화 해줬는데,

 

n이 1로 들어올 경우 연속된 수열의 합의 경우의 수를 제대로 못찾는 것 같다. 그래서 두번째 코드로 변경했다

예를 들어서, N이 1이면 1로 1을 만들 수 있으므로 경우의 수가 1개인데, 0이 출력된다.

 

투포인터 할때 sum에 lt를 대입해주지 말자, rt가 움직이면서 sum을 누적하고, 특정 조건에서 걸리면 lt를 움직이면서 빼주자.

public class Solution {
    public int solution(int n) {
        int answer = 0, lt = 1, sum =lt;

        for (int rt = 2; rt <= n ; rt++) {
            sum += rt;
            if (sum == n) answer ++;
            while(sum >= n) {
                sum -= lt;
                lt++;
                if (sum == n) answer ++;
            }
        }
        return answer;
    }
}

정확성 테스트

테스트 1 〉	통과 (0.03ms, 76.1MB)
테스트 2 〉	통과 (0.04ms, 74.5MB)
테스트 3 〉	통과 (0.04ms, 64.9MB)
테스트 4 〉	통과 (0.03ms, 74MB)
테스트 5 〉	통과 (0.03ms, 71MB)
테스트 6 〉	통과 (0.02ms, 77.8MB)
테스트 7 〉	통과 (0.04ms, 74.6MB)
테스트 8 〉	통과 (0.03ms, 72MB)
테스트 9 〉	통과 (0.03ms, 74.5MB)
테스트 10 〉	통과 (0.04ms, 72.6MB)
테스트 11 〉	통과 (0.05ms, 74.2MB)
테스트 12 〉	통과 (0.04ms, 78MB)
테스트 13 〉	통과 (0.04ms, 76.3MB)
테스트 14 〉	통과 (0.03ms, 77.5MB)
테스트 15 〉	실패 (0.02ms, 75MB)
테스트 16 〉	통과 (0.02ms, 76.5MB)
테스트 17 〉	통과 (0.02ms, 76MB)
테스트 18 〉	통과 (0.03ms, 72.7MB)

효율성 테스트

테스트 1 〉	통과 (0.29ms, 51.8MB)
테스트 2 〉	통과 (0.28ms, 52.1MB)
테스트 3 〉	통과 (0.36ms, 51.8MB)
테스트 4 〉	통과 (0.33ms, 51.6MB)
테스트 5 〉	통과 (0.36ms, 69.1MB)
테스트 6 〉	통과 (0.39ms, 52.1MB)

 

두번째 풀이

public class Solution {
    public int solution(int n) {
        int answer = 0, lt = 1, sum =0;

        for (int rt = 1; rt <= n ; rt++) {
            sum += rt;
            if (sum == n) answer ++;
            while(sum >= n) {
                sum -= lt;
                lt++;
                if (sum == n) answer ++;
            }
        }
        return answer;
    }
}

테스트 1 〉	통과 (0.02ms, 74.4MB)
테스트 2 〉	통과 (0.04ms, 74.3MB)
테스트 3 〉	통과 (0.06ms, 74.1MB)
테스트 4 〉	통과 (0.03ms, 73.8MB)
테스트 5 〉	통과 (0.02ms, 71.3MB)
테스트 6 〉	통과 (0.03ms, 79.7MB)
테스트 7 〉	통과 (0.04ms, 78.7MB)
테스트 8 〉	통과 (0.04ms, 78.6MB)
테스트 9 〉	통과 (0.02ms, 75.5MB)
테스트 10 〉	통과 (0.07ms, 72.8MB)
테스트 11 〉	통과 (0.08ms, 74.7MB)
테스트 12 〉	통과 (0.09ms, 79.2MB)
테스트 13 〉	통과 (0.06ms, 75.2MB)
테스트 14 〉	통과 (0.03ms, 75.1MB)
테스트 15 〉	통과 (0.02ms, 73.3MB)
테스트 16 〉	통과 (0.02ms, 72.2MB)
테스트 17 〉	통과 (0.03ms, 74.9MB)
테스트 18 〉	통과 (0.02ms, 72.2MB)

효율성 테스트

테스트 1 〉	통과 (0.50ms, 52.3MB)
테스트 2 〉	통과 (0.31ms, 52.3MB)
테스트 3 〉	통과 (0.36ms, 52MB)
테스트 4 〉	통과 (0.42ms, 52.1MB)
테스트 5 〉	통과 (0.40ms, 71.7MB)
테스트 6 〉	통과 (0.38ms, 51.9MB)

세번째 풀이 ( 제일 신뢰성 높은 코드 )

우선 1부터 n까지의 모든 자연수를 int배열에 담아주고, lt,rt를 움직이면서 더해준다.

class Solution {
    public int solution(int n) {
        int answer = 0, lt = 1, sum =0;

        int[] arr = new int[n+1];
        for (int i = 1; i <= n; i++) arr[i] = i;

        for (int rt = 1; rt <= n ; rt++) {
            sum += rt;
            if (sum == n) answer ++;
            while(sum >= n) {
                sum -= arr[lt++];
                if (sum == n) answer ++;
            }
        }
        return answer;
    }
}

 

테스트 1 〉	통과 (0.02ms, 70.8MB)
테스트 2 〉	통과 (0.08ms, 79.6MB)
테스트 3 〉	통과 (0.05ms, 72MB)
테스트 4 〉	통과 (0.05ms, 66.8MB)
테스트 5 〉	통과 (0.04ms, 80MB)
테스트 6 〉	통과 (0.02ms, 73.6MB)
테스트 7 〉	통과 (0.04ms, 79.9MB)
테스트 8 〉	통과 (0.04ms, 77.1MB)
테스트 9 〉	통과 (0.02ms, 82.3MB)
테스트 10 〉	통과 (0.06ms, 78.2MB)
테스트 11 〉	통과 (0.06ms, 76.2MB)
테스트 12 〉	통과 (0.04ms, 84.7MB)
테스트 13 〉	통과 (0.06ms, 78.4MB)
테스트 14 〉	통과 (0.06ms, 78.3MB)
테스트 15 〉	통과 (0.02ms, 79.6MB)
테스트 16 〉	통과 (0.02ms, 76.5MB)
테스트 17 〉	통과 (0.02ms, 73.3MB)
테스트 18 〉	통과 (0.04ms, 71MB)

효율성 테스트

테스트 1 〉	통과 (0.41ms, 52.3MB)
테스트 2 〉	통과 (0.44ms, 52.3MB)
테스트 3 〉	통과 (0.50ms, 69.9MB)
테스트 4 〉	통과 (0.56ms, 52.4MB)
테스트 5 〉	통과 (0.60ms, 52.1MB)
테스트 6 〉	통과 (0.59ms, 52.4MB)

 

첫번째 풀이와 세번째 풀이의 차이

두 코드의 주요 차이점은 배열을 사용하느냐 아니냐와 변수 초기화에 있습니다. 첫 번째 코드에서는 배열을 사용하지 않고 변수를 직접 조작하며 문제를 해결하려고 시도하고 있습니다. 두 번째 코드에서는 배열을 사용하여 각 숫자를 저장하고, 이 배열을 사용하여 합계를 계산합니다.

1. 변수 초기화:
   - 첫 번째 코드에서 `sum` 변수를 `lt`로 초기화하고, `lt` 값을 더해가며 합계를 계산합니다. `lt`를 초기값으로 설정한 이유는 반복문의 처음부터 시작하기 위함으로 보입니다. 하지만 이렇게 초기화하면 `lt`가 이미 1로 설정되어 있기 때문에 1을 더해주지 않아도 됩니다.
   - 두 번째 코드에서는 `sum` 변수를 0으로 초기화하고, 배열 `arr`에 각 숫자를 저장한 후, `rt` 값을 더해가며 합계를 계산합니다. 이 방식은 코드를 더 명확하게 만듭니다.

2. 배열 사용:
   - 첫 번째 코드에서는 배열을 사용하지 않고 `lt`와 `rt`를 사용하여 합계를 계산하고 있습니다.
   - 두 번째 코드에서는 배열 `arr`을 사용하여 각 숫자를 저장하고, `arr[lt]` 값을 사용하여 `sum`에서 빼고 있습니다. 이렇게 하면 코드가 더 간결하고 이해하기 쉽습니다.

두 번째 코드가 더 명확하고 이해하기 쉬우며 배열을 사용하여 합계를 계산하므로 코드의 신뢰성이 높아집니다. 따라서 프로그래머스에서도 두 번째 코드가 정확성 100%를 얻었을 가능성이 높습니다. 첫 번째 코드에서 발생한 오류의 원인은 초기화와 변수 조작 방식 때문일 가능성이 높습니다.