문제링크

문제 이해

[ 입력형태 / 조건 ]

n
자연수 | 15 | n은 10,000 이하의 자연수

[ 문제 ]

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return

[ 풀이 ]

try 1)

바로 조합을 이용해서 가능한 합을 구하고자 했지만, 조합으로 연속된 자연수를 구현하기엔 까다로워 보였음.

try 2)

큐를 이용해 n개의 값을 Node(이전 값, 합) 형태로 저장한 뒤, prev+1값을 더했을 때 같다면 ans를 증가, n보다 작다면 큐에 값 갱신하는 방법으로 구현
=> 테케는 전부 맞았지만, 효율성 테케는 시간초과가 나왔음

---

코드

> [실패] 1차 시도 : 큐 이용

• 생각한 풀이 그대로 구현

import java.util.*;

class Solution {
    public int solution(int n) {
        int ans = 1;
        Queue<Node> q = new LinkedList<>();
        for(int i=1; i<=n/2; i++){
            q.add(new Node(i,i));
        }
        
        while(!q.isEmpty()){
            Node node = q.poll();
            
            int curSum = node.sum + node.prev+1;
            if(n < curSum)
                continue;
            
            if(n==curSum){
                ans+=1;
                continue;
            }
            q.add(new Node(node.prev+1, curSum));
        }
        
        return ans;
    }
}

class Node{
    int prev;
    int sum;
    
    public Node(int prev, int sum){
        this.prev = prev;
        this.sum = sum;
    }
}

=> O(n/2)일텐데 시간초과가 나서 당황했음

> [실패] 2차 시도 : 구현

• 2중 반복문을 돌게 구현하되, 전체를 돌지 않게 했음

class Solution {
    public int solution(int n) {
        int ans = 1;
        
        for(int i=1; i<=n; i++){
            int sum = i;
            for(int j=i+1; j<=n; j++){
                sum += j;
                
                if(sum<n)
                    continue;
                
                if(sum == n)
                    ans++;
                break;
            }
        }
        return ans;
    }
}

Tip : 자료구조를 가져와 단순하게 구현한 것보다 가능한 구현으로 해결하는 게 더 효율적인 연산이 될 때가 있다.