- 문제설명
- 제한사항
- 예시 & 입출력 예
- 해결과정
- 문제를 보자마자 특별한 알고리즘을 적용하는 문제가 아니고 규칙을 찾는 문제라고 직감했다.
- 요즘 규칙찾는 문제를 하나씩 접하게 되는데.. 이번 문제도 하나 둘씩 규칙을 찾아봤다. 아래 그림을 보자.
예시
- 124 나라의 숫자가 1,2,4로만 이루어져 있다고 간단하게 3진법으로 변환하면 되겠다고 생각할 수 없었다. 0,1,2 였다면 3진법으로 변환하면 끝이지만 1,2,4 이기 때문에 나머지가 특수한 경우가 분명 있을 것이라 판단했다.
- 변환 전과 후를 비교해보면, 10진수를 3으로 나누었을 때 나머지가 1,2라면 맨 끝자리에 써주고 나머지가 없다면 4를 써주는 규칙이 존재한다는 것은 확인할 수 있다. 해당 규칙을 바탕으로 2개 정도 테스트를 해보자!
- 위의 예시 표와 비교해봤을 때 첫번째로 발견한 규칙 : 3으로 10진수를 나누었을 때 나머지수(0,1,2)에 따라 4,1,2 적어주기 규칙을 적용해봤다.
- 위의 결과처럼 나머지 수에 0, 즉 변환 숫자로 4를 써줘야하는 상황이 없다면 정상적으로 결과가 나왔지만 변환 숫자에 4가 하나라도 껴있다면 엉뚱한 결과가 나왔다.
- 위의 표처럼 숫자를 쭉 나열해놓고 보니 4에 대한 규칙을 찾기가 어려웠다. 3진법과 유사한 만큼, 3개 단위로 명확히 끊어서 다시 확인해봤다. 아래 표를 보자.
3개씩 나눈 디테일 표
- 가장 편한 방법으로, 3의 배수들의 상황을 비교해봤다.
- 24와 27, 30을 비교해보면 각각 3으로 나누었을 때 나머지가 0이어서 4를 먼저 내뱉고, 몫이 각각 8, 9, 10이 나온다. 이후 다시 3으로 나누어보면 나머지는 각각 2,0,1이 나온다 이는 124 나라에서는 2,4,1을 의미한다.
- 따라서 각각 중간자리가 2, 4, 1로 들어가야하는데 위에 정답표를 보면 모두 1씩 빠져있는 1, 2, 4가 들어가있다.
- 이것을 보고 "아 ! 4를 내뱉은 후 몫인 8,9,10을 하나씩 숫자를 빼고난 뒤 3으로 나누어주면 원하는 결과인 1,2,4가 나오겠구나" 라고 생각했다. 이후 틀린부분이 없을지 직접 확인해봤다.
나머지가 4였던 경우는 다음 몫을 3으로 나눠줄 때 1을 빼준다.
- 솔루션
class Solution {
public String solution(int n) {
String num_124 = "";
while(n > 0) {
if(n % 3 == 0) {
num_124 += "4";
n = n/3 - 1;
}
if(n % 3 == 1) {
num_124 += "1";
n = n/3;
}
if(n % 3 == 2) {
num_124 += "2";
n = n/3;
}
}
StringBuffer sb = new StringBuffer(num_124);
String reverse = sb.reverse().toString();
return reverse;
}
}
- 배운점
- 이렇게 규칙을 찾는 문제는 다양하게, 또 많이 풀어보면서 사고력을 끌어올리는게 중요하다고 생각했다.