[Level2] 숫자의 표현 답안 및 풀이

◇ 문제 설명

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

• 1 + 2 + 3 + 4 + 5 = 15
• 4 + 5 + 6 = 15
• 7 + 8 = 15
• 15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

 

◇ 제한 조건

• n은 10,000 이하의 자연수 입니다.

 

◇ 입출력 예시

n	result
15	4

 

◇ 초기 내용

※ [출처] 프로그래머스-코딩테스트 연습-문제명

※ 초기 내용을 참고하여 문제에 맞는 코드를 작성하세요.

class Solution {
    public int solution(int n) {
        int answer = 0;
        return answer;
    }
}

 

---

◇ 풀이 과정

문제의 풀이과정은 이러했다.

1. 연속적인 수의 기준점을 잡을 변수를 for반복문을 이용하여 반복
2. 중첩 for문을 이용하여 위에서 선언한 변수에서 n까지 반복
3. 누적합을 구하기 위해 sum변수 생성 후 연속적인 수의 누적합 구하기
4. 그 누적합이 n과 같으면 answer +1
5. 누적합이 answer보다 크면 이후 값들은 절대 n값이 될 수 없으므로 break문을 이용하여 효율성 향상

 

◇  참고 사항

첫번째, 효율성

• break문을 이용하여 효율성을 향상시켰다. 
• 효율성이 낮은 코드의 실행과정
  

  class Solution {
      public int solution(int n) {
          int answer = 0;
          for(int i = 1; i<=n; i++){
              int sum = 0;
              for(int j = i; j<=n; j++){
                  sum+=j;
                  if(sum==n) answer++;
              }
          }
          return answer;
      }
  }​

  
  
  i = 1일때,
  

  idx	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
  sum	1	3	6	10	15	21	28	36	45	55	66	78	91	105	120

  i = 2일때,
  

  idx	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
  sum	-	2	5	9	14	20	27	35	44	54	65	77	90	104	119

  i = 3일때,
  

  idx	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
  sum	-	-	3	7	12	18	25	33	42	52	63	75	98	102	117

  i = 4일때,
  

  idx	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
  sum	-	-	-	4	9	15	22	30	39	49	60	73	95	99	114

  i = 5일때,
  

  idx	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
  sum	-	-	-	-	5	11	18	26	35	45	56	68	81	95	110

• 효율성이 높은 코드의 실행과정
  

  class Solution {
      public int solution(int n) {
          int answer = 0;
          for(int i = 1; i<=n; i++){
              int sum = 0;
              for(int j = i; j<=n; j++){
                  sum+=j;
                  if(sum==n){
                      answer++;
                      break;
                  }
                  else if(sum > n){
                      break;
                  }
              }
          }
          return answer;
      }
  }

  i = 1일때,
  

  idx	1	2	3	4	5
  sum	1	3	6	10	15

  i = 2일때,
  

  idx	1	2	3	4	5	6
  sum	-	2	5	9	14	20

  i = 3일때,
  

  idx	1	2	3	4	5	6
  sum	-	-	3	7	12	18

  i = 4일때,
  

  idx	1	2	3	4	5	6
  sum	-	-	-	4	9	15

  i = 5일때,
  

  idx	1	2	3	4	5	6	7
  sum	-	-	-	-	5	11	18

두번째, break문

• 반복문을 빠져나가기 위한 코드
• break문 사용시, 반복 문장을 실행하지 않고 반복문 밖의 문장으로 빠져나간다.
• 실행과정
  ex. 반복문 10회 반복
  

  for(int i = 1; i<=10; i++){
      System.out.println(i);
  }​

   
  

  출력결과

  1 2 3 4 5 6 7 8 9 10

  
  ex. 반복문 10회 반복(단, i가 5일때 break)
  

  for(int i = 1; i<=10; i++){
  	System.out.println(i);
  	if(i==5) break;
  }​

  
  

  출력결과

  1 2 3 4 5

 

◇ 답안

class Solution {
    public int solution(int n) {
        int answer = 0;
        //1~n까지 반복문 실행
        for(int i = 1; i<=n; i++){
            //누적합을 구할 변수 선언
            int sum = 0;
            //연속된 숫자의 누적합을 구할 반복문
            for(int j = i; j<=n; j++){
                //누접합 구하기
                sum+=j;
                //만약, 누적된 합이 n과 같으면 answer +1
                //이후 sum에 누적되는 값들은 n보다 크기때문에 체크할 필요가 없으므로 
                //break문을 사용하여 반복 멈춤으로써 효율성 향상
                if(sum==n){
                    answer++;
                    break;
                }
                //연속적인 누적합이 만들어지지 않는 수들에 관해서도
                //누적된 값이 n보다 크면 break문 사용하여 효율성 향상
                else if(sum > n){
                    break;
                }
            }
        }
        return answer;
    }
}

 

◇ 실행결과

숫자의 표현 실행결과

◇ 효율성 테스트 결과

숫자의 표현 효율성 테스트 결과

◇ 출처

https://programmers.co.kr/learn/challenges

코딩테스트 연습