[맛있는물회] <알고리즘> "124 나라의 숫자"

이전에 풀던 알고리즘 문제는 Level 3 이었는데 나한텐 솔직히 좀 꽤 상당히 어려웠다...ㅎㅎㅎㅎㅎ

그래서 level 2로 낮춰서 처음 본 문제가 "124나라의 숫자"라는 문제였다.

 

문제는 이러하다! (출처 - programmers.co.kr)

 

쭉 나열해보니 규칙은 생각보다 쉽게 찾게되었다.

근데.... 왜 안댑...

 

막 계속 해보다가 안되서 힘들었다. 알고리즘 능력이 상당히 떨어지나 보다.ㅎㅎㅎ 

더 열심히 해야겠다는 생각이 들었다.

 

 

 

처음에 10진수를 2진수로 만드는 것처럼 재귀함수를 사용해서 해봐야겠다는 생각이었다.

근데 재귀로 하니깐 return 값에 있어서 계속 어긋나는 것이었다.. 

계속 고민하다가 저번에 배운 Dynamic Programming이 생각나는 것이었다. 

어짜피 1, 2, 4로 표현하는 것도 n을 3으로 나누고 그 몫에 대해서 반복적으로 시행하는 것이었기 때문에 DP가 가능하였다.

 

 

예를 들어 1 = 1, 2 = 2, 3 = 4이므로

4, 5, 6같은 경우 1의 자리수는 1,2,4가 반복되고 10의 자리수는 n-1을 3으로 나누었을 때 나오는 몫을 다시 똑같이 반복하면 나오는 값이다.

4 = 11, 5 = 12, 6 = 14...

 

 

사실 그렇게 어려운 문제는 아니긴한데 생각보다 조금 까다로웠던 것 같다.

 

 

처음에 ArrayList 가 아닌 그냥 String 배열로 잡으니깐 너무 메모리 사용이 많아서 접고 ArrayList를 사용하였다. 

 

이렇게 푸니깐 문제는 해결되었다. 근데 알고리즘 사이트에서 시간효율성 부분에서 에러가 나는 것이었다.

아직도 이유는 모르겠다. 문제를 풀었다는 것에 만족하고 구글링하여서 다른 사람들이 푼 풀이를 보았다.

 

 

 

 

내가 처음에 생각했던 재귀를 그냥 while문으로 만들어 놓은 것이다.

 

나는 switch 문을 사용했지만 다른 사람들은 그냥 arr[3] = {"4", "1", "2"} 이런식으로 배열을 만들어서 사용하기도 했다.

 

 

처음에 접했을때 2진수만드는 것처럼 재귀를 쓰려고 매달리다 보니깐 생각의 폭이 좁아져있었던 것 같다.

그래도 검색없이 혼자서 해결했다는 것에 만족하면서 마무리 해야겠다!!

 

끗