문제

1차 시도 (실패)

로직

1. 숫자를 1부터 순서대로 리스트에 넣는다.
2. 숫자를 넣을 때마다 리스트의 합을 구한다.
3. 만약 리스트의 합이 n을 넘는다면 n을 넘지 않을 때까지 작은 수부터 순서대로 리스트에서 제거한다.
4. 만약 리스트의 합이 n과 동일하다면 answer에 1을 더한다.

코드

import java.util.*;


class Solution {
    public int solution(int n) {
        int answer = 0;
        List<Integer> numbers = new ArrayList<Integer>();
        
        for (int i = 1; i < n+1; i ++) {
            numbers.add(i);
            
            int sum = numbers.stream().mapToInt(Integer::intValue).sum();
            
            while (sum > n) {
                numbers.remove(0);
                sum = numbers.stream().mapToInt(Integer::intValue).sum();
            }
            
            if (sum == n) {
                answer += 1;
            }
        }
        return answer;
    }
}

결과

정확성 테스트에서는 만점을 받았지만 효율성 테스트에서는 시간 초과로 인해 모든 테스트 케이스를 통과하지 못했다.

2차 시도 (성공)

로직

1차 시도에서 어떤 부분에서 시간이 오래 걸렸는지 생각해 보았다.
매번 리스트를 돌면서 합을 구하는 데에 문제가 있지 않을까 생각하다가 새로운 방식이 떠올랐다.

우리는 오로지 합이 n이 되는지만 알면 된다. 어떤 값들을 합했을 때 n이 되는지까지는 알 필요가 없다. 리스트를 만들지 않고 sum과 뺀 값만을 이용해서 문제를 해결하는 방식을 생각해 보았다.

1. sum은 0으로, minNum은 1로 초기화한다.
2. 1부터 n까지 반복문을 돈다.
3. 해당하는 수를 sum에 더한다. 만약 sum이 n을 넘는다면 n을 넘지 않을 때까지 아래 과정을 반복한다.
   3-1. minNum을 뺀다.
   3-2. minNum에 1을 더한다.
4. 만약 sum이 n과 같다면 answer에 1을 더한다.

코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        int sum = 0;
        int minNum = 1;
        
        for (int i = 1; i < n+1; i ++) {
            sum += i;
            
            while (sum > n) {
                sum -= minNum;
                minNum ++;
            }
            
            if (sum == n) {
                answer += 1;
            }
        }
        return answer;
    }
}

결과

매우 짧은 시간 내로 성공하여 정확성과 효율성 테스트 모두 만점을 받았다!

새롭게 알게 된 점

List에 값을 넣고 빼는 방식을 이용하여 문제를 풀었을 때에는 정확성 테스트에서 시간이 6ms까지도 나왔는데 sum과 minNum만을 이용해서 문제를 푸니 0.1ms만에 테스트를 통과하였다.

로직을 한 번 더 되짚어 보며 내가 만든 변수가 꼭 필요한 변수인지 다시 한 번 생각해보고 훨씬 빠르고 간단한 로직을 만들어보는 시간이 되었다.

그리고 참조형 변수를 하나 만들고 값을 삽입하고 빼는 것이 기본형 변수를 이용하여 실행하는 것보다 얼마나 오래 걸리는지 체감할 수 있는 문제였다.