오늘은 1,2,4 로만 숫자를 세는 이상한 나라 문제를 풀어보았다.
문제 자체는 특별히 어려울 것이 없지만 시간 적인 부분에서 굉장히 타이트하다고 느꼈던 부분들을 해결하는 방법들을 기록하고자 포스팅을 남긴다~
프로그래머스 124 나라의 숫자 (level2)
입출력 예시
자연수 n이 주어질 때 위 예시와 같이 1,2,4를 이용한 독특한 진법으로 계산한 결과를 반환하는 것이 요구사항이다
나의 풀이
처음엔 이러한 문제는 보통 패턴이 있기에 1,2,3,,, 을 쭉 나열해보며 패턴을 찾아서 조건문으로 간단하게 처리 해주면 될 것이라 생각하였다.
근데 또 풀다보니 dp를 사용하면 굳이 if문을 중첩해서 막 걸어줄 필요 없이 간단히 해결 될 것 같아 dp를 사용하여 풀었다,
당연히 통과겠지 싶었지만 택도 없이 탈랐했고, 아무래도 bottom-up 방식으로 1-n 까지 memorization을 거치는 부분에서 시간이 초과 되었을 거라고 생각하였다.
결국 처음에 찾았던 패턴을 다시 이용했고 그 방식은 다음과 같다
- 사용되는 수는 1,2,4 세가지 수 이므로 3을 주기로 한 패턴이 존재하게 된다
- 주어지는 수를 < 3 * a + b >와 같은 방식으로 표현
- a 가 0 이상일때는 재귀적으로 다시 a = 3 * a' + b 과 같이 표현한다
- b가 1이나 2일때는 그대로 string으로 변환해 정답에 포함하고, 0일 때는 4를 string으로 포함하되 a의 값을 -1 시킨다
#include <string>
#include <vector>
using namespace std;
string solution(int n) {
string answer = "";
int share = n;
int left= -2;
while(share > 0){
left = share%3;
share = share/3;
if(left == 0){
answer = "4" + answer;
share--;
}else if (left == 1){
answer = "1" + answer;
}else{
answer = "2" + answer;
}
}
return answer;
}나는 초기에 while 문에 들어가기 전 share, left를 먼저 계산 한 후 while문 안의 조건문을 거친 후 다시 share, left 를 갱신하는 방식을 택했으며
1,2,4를 정답에 붙이는 과정에서 to_string()을 사용하였다.
하지만 이와 같은 방식은 시간 측면에서 통과하지 못했고 타 포스팅을 참고하여 수정하였다.
to_string() 사용대신 조건문을 하나 추가해 ( answer = "1" + answer; ) 과 같이 작성했고, 계산 횟수를 한번이라도 줄여야 함을 깨닫고 위와 같이 코드를 완성하였다.
다른 풀이
주어진 수를 3으로 나눈 나머지가 0,1,2 반복될 때 마다 정답에 포함되는 string이 "4", "1", "2"가 반복된다
이를 이용해 if 문을 3번 걸어줄 필요 없이 "412"[a] 와 같이 아주 깔-끔하게 작성된 풀이인 것 같아 함께 기록한다~!
💡 포스팅 관련 문제가 있다면 댓글이나 메일로 알려주시면 감사하겠습니다~!
