이걸 들고 온 이유는 내 생각대로 문제를 풀고, 결과값은 잘 나오는데 문제에서 오답처리가 계속 돼 어려웠던 문제라 이 문제들을 풀면서 겪었던 과정과 이 과정들을 통해 배운 부분을 기록하기위해서다.
문제
자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- n은 1 이상 100,000,000 이하인 자연수입니다.
입출력 예nresult
| 45 | 7 |
| 125 | 229 |
입출력 예 설명
입출력 예 #1
- 답을 도출하는 과정은 다음과 같습니다.
| 45 | 1200 | 0021 | 7 |
- 따라서 7을 return 해야 합니다.
사고 풀이
- 숫자를 3진법으로 변환
- 변환한 숫자 뒤집기
- 다시 10진법으로 변환
- 값 반환
이렇게 하면 될것같다.
직접 풀기
1.숫자 3진법으로 변환
int x = 0; int y = 0;
while(n>0)
{
x = n%3;
answer += x * pow(10,y);
n/=3;
y++;
}우리가 3진법을 하는 방법은 쉽다.(링크 : 수학 카테고리에 업로드 예정)
이거에 따라 계산을 하자면 3의 나머지를 더해주는데 10을 y제곱 하는 과정으로 더해주면 n = 11이라고 쳤을 때
처음에 3으로 나누면 나머지가 2 몫이 3이므로
answer = 2 x 10^0 = 2
n = 3
이 되고 두번째는 나머지 0 몫이 1이므로
answer = 2 + (0 x 10^1)
n = 1
세번째는 나머지 1 몫 0 이므로
x = 2 + (1 x 10^2) = 102
n = 0
이 된다. 그리고 조건을 벗어낫기 때문에 반복문은 종료가 되는 것이다.
2. 숫자 뒤집기
y = 0;
while(answer > 0 )
{
y *= 10;
y += answer%10;
answer /= 10;
}이건 그냥 숫자를 뒤에서부터 빼서 계속 10을 곱해 앞으로 밀면서 넣어주는거라고 보면 된다.
3. 다시 10진법으로 변환
while(y > 0)
{
answer += y%10*pow(3,x);
y/=10;
x++;
}이제 3진법을 다시 10진법으로 바꿔야한다. (링크 : )
이건 그냥 자릿수마다 제곱해서 더해주면 된다.
그리고 반환
완성
#include <vector>
#include <cmath>
using namespace std;
int solution(int n) {
int answer = 0;
int y = 0;
int x = 0;
while(n>0)
{
int x = n%3;
answer += x * pow(10,y);
n/=3;
y++;
}
y = 0;
while(answer > 0 )
{
y *= 10;
y += answer%10;
answer /= 10;
}
while(y > 0)
{
answer += y%10*pow(3,x);
y/=10;
x++;
}
return answer;
}이렇게 하면 n(주어진 값) -> answer(3진법모양의 수) -> y(뒤집힌 3진법) -> answer(10진법 모양의 수) 로 왔다갔다 하면서 완성된다.
값도 제대로 나왔으나 오답이였다.
변경
우선 값은 제대로 나온다 그렇다면 계산 속도가 문제인건가? 싶어서 줄일 방법을 생각해보았더니 처음에 3진법으로 바꿀 때 뒤집어서 적용시키면 되는거였다.
3진법 변환과 숫자 뒤집기 한번에 하기
int x = 0; int y = 0;
while(n>0)
{
int x = n%3;
y += y * 10 + x;
n/=3;
}전에는 나머지값에 10의 y제곱해서 더해주었는데 그냥 기존 수 *10하고 나머지를 더해주면 알아서 뒤집힌 형태로 잘 나온다.
#include <vector>
#include <cmath>
using namespace std;
int solution(int n) {
int answer = 0;
int y = 0;
int x = 0;
while(n>0)
{
int x = n%3;
y += y * 10 + x;
n/=3;
}
x = 0;
while(y > 0)
{
answer += y%10*pow(3,x);
y/=10;
x++;
}
return answer;
}하지만 정답이 안나온다.
왜 그런지 몰랐다. 나는 나의 수학적 지식에 의문을 품고 엑셀을 통해 내 계산방법이 맞는지 체크해보았다.
엑셀
45를 3진수로 바꾸면 1200
역순으로하면 21
10진수 변환하면 7이다. 정답은 제대로 나온다.
그렇다면 큰 수도 제대로 되는지 체크를 해보면
이런 답이 나온다.
제대로 되는지 다른 사이트들을 돌면서 검증해보았다.(사이트 링크 : https://ko.calc-site.com/bases/convert_n)
우선 99999999를 3진수로 변환하고 뒤집은 값은 엑셀의 값과 동일하다.
뒤집은 수를 바꾸면
이렇게 정답이 나온다.
그렇다면 내 방식은 일단 틀리지 않았다. 그렇다면 뭐가 문제일까... 모르겠어서 주위에 도움을 요청했더니
99999999이라는 수를 넣어보라고 해서 넣어봤더니.... 전혀 다른 수가 나왔다.
변수 타입 바꾸기
비쥬얼 스튜디오에서 왜 다른 수가 나올까 한번 해봤더니.
중간부터 이상해졌다.
그렇다... int의 최대 저장 가능한 수 범위는? -2,147,483,648 ~ 2,147,483,647 다.
그래서 나는unsigned long long으로 바꿔줬다.
아주 잘 나온다.
그래서 나는 그대로 바로 적었더니...
이런 식으로 나온다. 찾아보니
이 오류는 링커 오류로, 함수 solution(int)의 구현체를 찾을 수 없어 발생합니다. 코드에서 함수 선언과 정의가 일치하지 않거나, 구현 파일이 컴파일되지 않았을 때 나타납니다.
라는 문제라고 한다.... 그래서 입력값인 n을 int로 바꿨더니
n은 1 이상 100,000,000 이하인 자연수입니다.
이 조건인 99,999,999를 넣으면 0이 나온다...
근데 생각해보면 int면 제한사항이랑 다르지 않나...?라는 생각이 들긴 한다 하지만 제출 시 통과된다.
제한조건을 너무 진지하게 안받아들여도 될거같다.
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
int solution(int n)
{
int answer = 0;
unsigned long long x = 0;
unsigned long long y = 0;
while(n>0)
{
x = n%3;
y = y * 10 + x;
n/=3;
}
x = 1;
while(y > 0)
{
answer += y%10*x;
y/=10;
x*=3;
}
return answer;
}결론
하지만 결국 3진법의 형태를 띌 뿐이지 실제로는
221021111022202이라는 엄청난 크기의 수를 갖게되는것이기 때문에 프로그래머스에서 처음에 제시해주는 string을 사용해서 해결하거나 vector를 이용해서 하는게 더 나을거같다.
나는 어느 순간부터 어떤 자료형 형태를 사용할지 고민을 안하고있었는데 이런거 하나하나 생각을 제대로 하는게 좋겠다고 다시 한번 상기할 수 있었고 최대한 잊지 않도록 여기에 기록해두려고 한다.
'C++' 카테고리의 다른 글
| C++[아이템을 다른 헤더파일에서 가져와서 사용하기] (0) | 2025.01.14 |
|---|---|
| C++[텍스트 RPG에서 상점 만들기(2. 구매, 판매)] (0) | 2025.01.13 |
| C++ [텍스트 RPG에서 상점 만들기(1. 플로우차트, 상점 입장)] (0) | 2025.01.10 |
| C++[클래스를 이용해 동물소리 출력] (0) | 2024.12.26 |
| C++ [오름차순과 내림차순 정렬] (1) | 2024.12.24 |