[알고리즘_Programmers] 7주차 2번 문제 및 풀이

이번 포스팅에서는 "숫자의 표현"이라는 문제에 대한 풀이를 진행하겠다.

 

우선 주어진 문제는 다음과 같다.

 

<문제>

 

<잘못된 풀이 1>

 

• 접근 방법은 잘 생각을 해냈으나, answer의 초기화 위치를 잘못 지정해줘서 출력 값이 계속 '1'이 나오는 상황에 직면했다.
• 코드를 아무리 쳐다보아도, 어느 부분이 잘못된 것인지를 알 수가 없어서 구글링을 해보았다.
• 그 결과, answer의 초기화 위치가 잘못되었다는 것을 깨달았다...ㅠㅠ
  • 초기화 위치를 for 문 밖에 설정하면, 반복문이 돌아가면서 새롭게 초기화가 되지 못한다.
  • 따라서 for 문 안에다가 초기화 값을 지정해주어야 한다.
  • 거의 다 푼 문제였는데 이걸 발견 못하다니 ㅜㅜ 정말 아쉽다..

 

<잘못된 풀이 2>

 

• answer의 초기화 위치를 수정해주고 코드를 다시 돌려보았더니, 원하는 출력 값인 '4'가 출력되었다!!
• 신나는 마음으로 "코드 채점하고 제출" 버튼을 눌렀으나...결과는 효율성 부분에서 문제 발생 ㅎㅎㅎ
• Level 2 문제들은 코드의 효율성에 대한 부분도 체크를 하기 때문에, 이 부분도 신경을 써서 구현을 해주어야 한다.

 

<풀이 1>

 

• 시간 복잡도를 줄여주기 위해 다른 사람의 풀이를 참고해보니, break 문을 사용한 것을 확인할 수 있었다.
• 연속된 자연수의 합이 n이 나오면, 다음 수를 아무리 더해도 다시는 n이 나올 수 없으므로 break 문을 써준다.
• 마찬가지로 연속된 자연수의 합이 n보다 커지면, 다음 수를 아무리 더해도 다시는 n이 나올 수 없으므로 break 문을 써준다.
• 이와 같이 break 문을 사용하면, 시간 복잡도가 줄어들어서 "코드 채점하고 제출" 버튼을 눌렀을 때 문제가 발생하지 않는다. ^^

 

<풀이 2>

 

• 위 풀이는 또 다른 사람의 풀이이다.
• 반복문을 돌리는데 1부터 n까지 홀수만을 대상으로 하고, n을 i로 나눴을 때 나누어 떨어지는 수들의 개수를 반환해주는 코드이다.
• 즉, 쉽게 말해 n이 주어졌을 때, 홀수인 약수의 개수를 구해주는 것이다.
• 코드를 보자마자 확 와닿지는 않았다. 왜 이렇게 푸는 것이 정답인지도 사실 처음에는 잘 이해되지 않았다.
• 그런데...풀이에 대한 해설을 보고 나서 알았다. 이 사람은 천재라는 것을. 어떻게 이런 생각을 할까..?

<풀이 2>의 코드에 대한 부연 설명을 해보면 아래와 같다.

 

예를 들어 생각해보자.

 

15를 예로 생각해보면, 15의 홀수인 약수는 1, 3, 5, 15가 있다.

 

(1) 약수가 1

- 1로 인해 15는 연속하는 하나의 자연수, 15로 이루어져있음을 알 수 있다.

 

(2) 약수가 3

- 3으로 인해 15는 5+5+5 의 합으로 표현되는 것을 알 수 있고, 약간의 조작을 통해 4+5+6 이 되고 연속하는 자연수가 된다.

 

(3) 약수가 5

- 5도 마찬가지로 3+3+3+3+3 즉, 1+2+3+4+5 로 표현이 가능하다.

 

(4) 약수가 15

- 15 같은 경우는 위의 (1), (2), (3) 과는 조금 예외적이다.  

- 모든 홀수 2n+1는 n 과 n+1, 연속하는 두 수의 합으로 표현 가능하므로, 이 경우에는 7+8로 생각하면 될 듯 하다.

 

 

★ <풀이 2>에 대한 부연 설명 참고 사이트: https://ssungkang.tistory.com/entry/%EC%88%AB%EC%9E%90%EC%9D%98-%ED%91%9C%ED%98%84%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2

숫자의 표현(프로그래머스 - level2)

 

문제들이 하나 같이 어렵다... 그래도 포기는 하지말자. Level 2 문제 끝까지 Run!!