Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 오늘밤 세계에서 이 사랑이 사라진다 해도 #독후감 #오열
- 백준
- 툰쉐이딩
- 코드리뷰
- leetcode
- c++ 베이직
- A* Algorithm
- 브론즈
- Toon Shading
- 순환 리스트
- STL
- 네트워크 기초
- Console
- UE_5
- build.cs
- 헤더 경로
- 언리얼엔진5 #언리얼 클라이언트 프로그래밍
- CS
- 원카페#무인카페#카페추천#카페맛집
- 메테리얼
- CS50
- Unreal
- 폭설 #미친 날씨
- Module
- 언리얼 엔진5 #언리얼 클라이언트 프로그래밍
- C++
- 언리얼
- Gas
- Harvard
- topdownmove
Archives
- Today
- Total
WN_인생기록
LeetCode - 9. Palindrome Number 본문
팰린드룸(회문) 에 대한 문제이다.
int 형으로 된 숫자가 회문인지 아닌지 판단하는 알고리즘을 구하는 문제이다.
예시에는 기본 상태와, 예외 처리해야할 예시들이 보여진다.
(음수는 팰린드룸 X, 10 일때는 01 이기 때문에 회문이 될 수 없음)
정리하자면
앞부분과 뒷부분이 같아야 하는데, 음수이면 안되고, 10의 배수이거나 0이여서도 안됨
class Solution {
public:
bool isPalindrome(int x)
{
// 음수 제외, 10의 배수 제외, 0 제외 조건
if (x < 0 || (x % 10 == 0 && x != 0))
return false;
// x 값을 original에 복사
original = x;
// 자릿값 구하기
while (x > 0)
{
length++;
x /= 10;
}
// 자릿수를 통해서 앞자리 구하기
front = original / (pow(10,(length / 2)));
// original의 %(나머지 연산)을 통해서 뒷자리 구하기
while (original > reverse)
{
reverse = reverse * 10 + original % 10;
original /= 10;
}
// 앞자리 뒷자리 비교하기
if (front == reverse)
{
return true;
}
return false;
}
private:
int front;
int reverse;
int original;
int length;
};
처음에는 이런식으로 클래스와 멤버 변수들을 활용해서 작성해봤는데, 생각보니까 불필요한 것들이 많은거 같았다.
멤버 변수에 대한 정의가 너무 많아서 굳이 이렇게 안해될텐데 싶었다. 물론 이렇게 해서 문제는 풀리지만 좀 더 효율적으로 만들고 싶었다. 메모리 사용도 너무 많아서, 줄이고 싶었다.
class Solution {
public:
bool isPalindrome(int x)
{
// 음수 제외, 10의 배수 제외, 0 제외 조건
if (x < 0 || (x % 10 == 0 && x != 0))
return false;
// 멤버 변수 아닌, 일반 변수로 선언 + log를 활용함으로써 자릿수 파악하기
// 자릿수/2 값으로 팰린드룸 기준 정해서 앞자리 구하기
int front = x /pow(10,(int)log10(x)/2);
// 뒷자리 초기화 한 뒤, 뒷자리 구하기
int reverse =0;
while(x > reverse)
{
reverse = reverse * 10 + x % 10;
x /= 10;
}
return (front == reverse) ? true : false;
}
};
이렇게 줄였더니 문제가 발생했다. 바로 (int)log10(x/2) 부분에서 회문 기준으로 정확하게 나누지 못할때가 발생한다.
즉 홀수 자릿수 일때 오답이 나온다. 그래서 이부분을 갈아엎고 새로운 방식으로 접근했다.
class Solution {
public:
bool isPalindrome(int x) {
// 음수와 10의 배수(0 제외)는 팰린드롬이 아님
if (x < 0 || (x % 10 == 0 && x != 0))
{
return false;
}
int reverse = 0;
while (x > reverse)
{
reverse = reverse * 10 + x % 10;
x /= 10;
}
// x와 reverse가 같거나, 홀수 자릿수일 경우 중앙 숫자를 제외하고
//x가 reverse/10과 같은지 확인
return x == reverse || x == reverse / 10;
}
};
앞자리를 따로 구하는게 아니라, 뒷자리 구할때 동시에 같은 지점에서 멈출 수 있도록 한뒤, 비교할때 홀수라면 x가 한자릿수 모자를테니, /10 을 해줌으로써 중앙값을 빼주는 역할을 한다. 그러면 회문인지 아닌지 판단이 바로 가능함으로, 많은 과정을 줄인셈이다.
이렇게 코드가 간결하게 마무리 되었다.
별거 아닌 알고리즘이지만, 다양한 방법으로 시간 복잡도와 공간 복잡도에 대한 비교를 할 수 있어서
더 효율적인게 뭔지 어렴풋이 파악이 가능했다.
'LeetCode > Easy' 카테고리의 다른 글
LeetCode - 14.Longest Common Prefix (0) | 2024.03.27 |
---|---|
LeetCode - 13 Roman to Integer (0) | 2024.03.27 |