백준 11047번 - 동전 0(Node.js)

백준 11047번 - 동전 0(Node.js)

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

가장 쉬운 그리디(Greedy : 욕심쟁이) 알고리즘을 이용하는 문제이다.

 

 

---

첫 번째 나의 풀이

• 제출시 결과는 틀렸습니다
• 20번째 줄 : haveCoins는 동전의 가치를 의미한다.
• 29번째 줄 : 동전의 가치가 큰 것부터 탐색하기 위해 for문에서 i를 N - 1부터 설정하였다.
• 30 ~ 43번째 줄 : 만약 현재 내가 설정한 가치인 nowAmount가 동전의 가치보다 작다면, 아무 일도 일어나지 않고
  그 반대라면, 다시 한번 반복문을 이용하여 (동전의 가치 * j)가 내가 설정한 가치보다 클 때까지 count를 증가시키며
  (동전의 가치 * j)가 내가 설정한 가치보다 크다면 [내가 설정한 가치 - {동전의 가치 * (j -1)}]의 연산을 해주게 된다.
• 처음에 이렇게 코드를 짜고, 제출했을 때의 결과가 틀렸습니다가 나와서 어리둥절했지만,
  만약, 동전의 가치가 1짜리밖에 없고, K의 값이 100,000,000이라면, for문을 100,000,000번 돌려야 했기에 이 로직은 맞지 않는다는 것을 알아내었다.

 

 

---

두 번째 나의 풀이

• 위에서 K의 값이 100,000,000이고, 동전의 가치가 1뿐일 때를 고려하기 위하여 33번째 줄의 for문에서 j를 100,000,000까지 반복하도록 하였더니 결과는 맞았습니다!!
• 하지만, 위의 코드가 돌아가긴 하지만, 어느 누가 for문을 100,000,000번 돌릴까.. 😂😂😂
• 그래서, 이 코드를 더 나은 방법으로 더 깔끔하게 돌아가도록 리팩토링을 해보았다.

 

 

---

세 번째 나의 풀이

• 제출 시 결과는 맞았습니다!!
• 이 방법은 for문을 100,000,000번 돌리지 않고, %와 /을 이용해서 풀었다.
• 30번째 줄 : K원의 가치를 만드는데, K원보다 가치가 큰 동전들은 사용하지 않으므로, 
  (K / 각 동전의 가치) 가 0.xxxxxx 가 나온다면, 이 동전은 사용하지 않는것을 의미한다.
  따라서, 같은 이치로 parseInt(K / 각 동전의 가치) 가 0이라면 아무 일도 해주지 않는다.
• 32 ~ 35번째 줄 : 만약 앞으로 만들 가치가 0이 된다면, 그 즉시 로직을 종료하기 위해 코드를 작성했다.
• 37 ~ 38번째 줄 : 각 동전의 가치의 필요한 갯수를 amount에 담고, 총 동전의 갯수인 count에 더해주었다.
• 39번째 줄 : 앞으로 만들 가치를 갱신해야 하기 때문에, (현재의 가치 % 각 동전의 가치) 로 남은 가치를 갱신해주었다.

 

 

---

느낀점

•  100,000,000번 포문을 돌리는 것과 리팩토링을 통하여 코드를 간결화했을 때 컴파일 시간이 리팩토링 후 약 1/4 정도로 줄어든 것을 볼 수 있었고, 뿐만 아니라 코드를 한눈에 보기에도 편해졌다.

위 : 리팩토링 후 / 아래 : 리팩토링 전