진법 변환 알고리즘을 구현해 봅시다.

구현 2021. 3. 25. 07:00

 진법 변환은 어떻게 하면 좋을까요? 사실 익숙한 것이지만, 막상 코테에 나오면 당황할 법 합니다. 단독으로 나오기도 하지만, 문제를 푸는 과정에서 등장하기도 합니다. 0보다 큰 정수 n을 b진법 (b는 1보다 큰 정수)으로 바꾸는 방법을 알아보도록 하겠습니다. 그리고, AssertionError를 떨구는 것도 같이 알아보겠습니다.

 

 


 먼저, 23을 10진법으로 변환하는 알고리즘을 생각해 봅시다. 그러면 먼저 23을 10으로 나눠야 할 겁니다.

 

 

 그러면 몫이 2가 나오고, 나머지가 3이 나옵니다. 여기서 우리는 나머지 3을 취합니다. 몫이 2가 아니니, 2를 10으로 나누어서 몫과 나머지를 다시 구해야 합니다.

 

 

 그러면 몫이 0이고, 나머지가 2입니다. 몫이 0이 되었으니 여기서 끝내면 되겠군요. 나머지는 3, 2 순으로 빠졌는데요. 실제로, 23을 10진법으로 표현한다면 역순으로 출력해야 합니다. 만약에 Java에서 ArrayList로 처리했다면 뒤에서부터 순회하면서 다시 결과 배열에 넣어야 할 겁니다.

 

 이것을 하지 않게 하려면, 앞과 뒤에서 넣고 뺄 수 있는 자료구조를 생각해야 하는데요. 이를 가능하게 하는 것은 Deque 기반의 구조입니다. 이 중에서 저는 ArrayDeque를 쓰겠습니다.

 

 

 여기서 push는 addFirst와 대응이 되는데요. 맨 앞에 추가한다는 의미입니다. 3이 추가되고, 2가 추가되는 상황이라면, 아래와 같이 추가가 될 겁니다.

 

 

 while loop을 돌면서 처음에 3이 나왔습니다. 이게 맨 앞에 추가되었습니다.

 

 

 다음에 2가 나왔는데 이게 맨 앞에 추가 되었습니다. 그러면, 2 3 이렇게 들어갑니다. 나온 순서대로 맨 앞에 추가가 되므로, 뒤집지 않아도 됨을 알 수 있어요. arrayList에 add를 하는 것과 넣는 방향이 반대임을 간파하시면 좋겠습니다.

 

 

 해당 코드는 위와 같습니다. 어렵지 않게 코딩하실 수 있습니다.

 


 그런데, 이걸로만 끝나면 뭔가 허전한 거 같군요. 정말 제가 작성한  conv 메서드가 맞는지 확인해 보도록 합시다. junit이 강력한 거 같지만, 여기에서는 AssertError만 언급하고 넘어가도록 하겠습니다. 실제로 제가 문제 출제를 할 때 Assertion 함수를 많이 이용하는 편입니다.

 

 Assert는 단정한다를 의미를 가집니다. 이를 쉽게 말하면, 사실이라는 것을 강하게 주장하는 겁니다. 코딩 테스트의 문제를 생각해 봅시다. n의 범위가 구간 [1, 10]에 속한다고 문제에서 제시하였습니다. 중요한 것은, 이것을 문제에서 강하게 주장했다는 겁니다. 이게 깨지면 어떻게 될까요? 예를 들어서, n이 30억이라던지, 200조라던지. 그러면, 문제 자체가 잘못된 게 되어 버립니다. 문제에서 강하게 주장한 것이 거짓이기 때문입니다. 문제에서 주어진 조건 조차 거짓이라면, 문제가 성립이 될 수 없어요. tc 갯수가 30 이하라고 했는데, 300억개가 주어질지 어떻게 알고요. 코딩 테스트에서 그런 일이 발생하면 정말 화나지 않을까요? 그 관점에서 보시면 됩니다.

 

 

 test는 다음을 테스트 할 겁니다. b진법으로 표현된 ret을 10진법의 수로 바꿨을 때 n이 나올 거에요. 이걸 프로그램에서는 강하게 주장하고 있습니다. 그러면, b진법으로 표현된 ret을 10진법의 수로 바꿨을 때 n이 아니라면요? 거짓말이 되어 버립니다. 만약에 거짓말이라면, AssertionError를 떨어트리면 됩니다.

 

 14번째 줄에 num은 ret을 10진법으로 변환한 수를 의미합니다.

 

 

 15번째 줄을 보면, 거꾸로 탐색을 하는 것을 볼 수 있는데요. 이는 맨 끝 자리수는 무조건 1이기 때문입니다. 중요한 것은 removeLast인데요. 이것은 맨 끝에 있는 원소를 제거합니다. 어떻게 수행되는지 보여드리겠습니다. 처음에 [2, 3]이 있었습니다. b의 값은 10입니다.

 

 zari가 1인 상태입니다. 이 상태에서 removeLast를 했더니 3이 뽑힙니다. 맨 뒤에 있는 것이 뽑히기 때문입니다. 여기에 1을 곱하면 3이고, 이게 num에 더해지므로, num은 3이 됩니다. zari에는 b가 곱해지는데, b가 10이라면 10이 곱해집니다.

 

 

 다음에 zari는 10이 됩니다. removeLast를 하면 2가 뽑힙니다. 여기에 10을 곱하면 20이고, 이게 num에 더해지므로, num은 3에 20을 더한 23이 됩니다. b진법으로 표현된 ret을 10진수로 변환했음을 알 수 있어요. 뒤에서부터 보는 게 쉽다는 것만 보시면 됩니다. 자. 여기서, 이 프로그램은 b진법으로 표현된 ret, 즉 num이 n이다. 라는 것을 강하게 주장하고 있어요.

 

 그러면 num이 n과 같지 않으면 AssertionError를 떨어트리면 됩니다. 그 순간 전제가 깨지기 때문입니다. 전제가 깨지는 것은 생각보다 심각한 문제입니다.

 

 

 main 함수에서는 단지, 제가 짠 conv 메서드가 맞는지 확인하기 위해서, test 메서드를 돌렸습니다.

 

 

 AssertionError가 뜨지 않는 걸로 보아서는 맞는 듯 하네요. 이 방식은 코테에서는 쓸 일이 있을지는 잘 모르겠습니다. 그런데, 문제 제작할 때도 꽤 많이 쓰이고, 테스트 할 때도 많이 쓰이는 듯 하니 알아두시면 도움이 될 듯 싶습니다.