Problem #004

오일러 알고리즘

🚩 문제 설명

오일러 알고리즘 #04

대칭수란? (Palindrome)
앞에서부터 읽으나 뒤에서부터 읽으나 모양이 같은 수
ex) 1001, 33

◾ 세자리 수를 곱해서 만들 수 있는 가장 큰 대칭수를 구하는 문제

◾ 팰린드롬 문제

◾ 세자리 수 두개를 곱해서 큰 대칭수를 만드는 것이다.

◾ 세개를 곱하는 것이 아니니 주의하시길.

 

 

---

 

 

📑 문제 풀이

// 20200116 오일러 알고리즘 Problem 04
#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	string ans;			//연산되어 진 값
	string out;
	stack<char> st;
	int num=0;

	for (int i = 100; i < 1000; i++)
	{
		string reverse = "000000";		//연산되어 진 값의 역순
		for (int j = 100; j < 1000; j++)
		{
			if (ans == reverse && num < stoi(reverse))
			{
				num = stoi(ans);
			}
			ans = to_string(i * j);

			for (int k = 0; k < ans.size(); k++)
			{
				st.push(ans[k]);
			}
			
			for (int k =0; k<ans.size() ; k++)
			{
				reverse[k] = st.top();
				st.pop();
			}
		}
	}

	cout << num;
	return 0;
}

💬 Point

👉 브루트 포스
👉 스택

◾ 브루트포스와 스택을 사용해서 문제를 풀었다.

◾ 세자리 수를 곱해서 만드는 팰린드롬 수 이므로 100 에서 999까지 반복문을 돌아야한다.

◾ 100 x 100 ~ 999 x 999 까지 도는 것이다.

◾ ans 는 위처럼 두수가 곱해지는 수를 넣은 변수이다. to_string() 함수를 이용해서 문자열로 변경해준다.

◾ 그리고 그 문자열 하나하나를 stack에 넣어준다.

◾ 하나씩 pop 해서 reverse 변수안에 넣어준다.

◾ 만약 reverse 와 ans가 같다면 그 수는 팰린드롬수에 해당한다.

stoi() : string을 int로 변환하는 함수
to_string() : int를 string으로 변환하는 함수

 

 

---

 

 

But,

✅ 답을 구하기까지 시간이 좀 걸림.
✅ 반복문을 3개 돌아 O(N^3)이 되어서 900 * 900 * 900 이 되는데 이게 두번이니까 7초 + 7초 가 되어서 14초 정도 걸리게 된다.
✅ %10, %100, %1000 이런식으로 나눠서 각각의 자리를 구해 같은지 비교하는 방식도 나쁘지 않을 듯.
✅ reverse 변수 안에 반복문을 돌면서 넣어줘야하기 때문에 항상 자릿수를 "000" 이런식으로 초기화해야함.
✅ 그렇지않으면, string 문자열 첨자 범위가 벗어난다.

➕ Solution 풀이 사이트 첨부

https://www.mathblog.dk/project-euler-problem-4/

Solution to Project Euler problem 4 in C# | MathBlog

 

 

 

 

 

 

 

 

 

 

---