{프로젝트 오일러/Project Euler} 4. 세자리 수를 곱해 만든 대칭수

한국어/Hackerrank - 한국어 버전과 문제가 다를 수 있습니다. 채점은 Hackerrank를 추천합니다.

101101 < 입력값:n < 10^7

palindrome = set()
for i in range(999, 99, -1):
	for j in range(999, 99, -1):
		if (i*j) % 11 == 0:
			s = str(i*j)
			if s == s[::-1]:
				palindrome.add(i*j)
palindrome = sorted(palindrome)
for _ in range(int(input())):
    n = int(input())
    begin, end = 0, len(palindrome)-1
    while begin <= end:
        mid = (begin+end)//2
        if palindrome[mid] >= n:
            end = mid - 1
        else:
            begin = mid + 1
    print(palindrome[end])

이 문제는 정수 n이 주어질 때 세 자릿수 두 개를 곱하여 만들어지는 대칭수(회 문수) 중에서 n보다 작은 대칭수 중 가장 큰 대칭수를 출력하는 문제입니다.

n이 800000인 경우 n보다 작은 대칭수 중 가장 큰 것은 793397이며 이는 869*913입니다.

또한, 입력의 최솟값이 101102이므로 모든 입력값에 대한 답은 6자리 대칭수입니다

어느 두 세자리 수의 곱이 조건에 맞을지 알 수 없기 때문에 미리 세 자릿수 두 개로 만들 수 있는 모든 대칭수를 저장합니다.

이때, 중복을 없애기 위해 set을 사용하고 추후 이진 탐색을 사용하기 위해 해당 set을 정렬된 리스트로 만들어줍니다.

그리고 대칭수인지 확인하는 과정에서 어떤 수가 11의 배수인지 확인하는데 이는 길이가 짝수인 대칭수는 11의 배수이기 때문입니다.

위와 같은 방법을 통해 모든 대칭수를 구했다면 답을 구해야 합니다.

이를 위해 주어진 리스트에서 n이 들어가야 할 인덱스를 구하면 되므로 이진 탐색을 통해 구합니다.

여기서는 따로 이진탐색을 설명하지는 않지만 결론적으로 while문이 끝나면 begin은 end+1이며 인덱스 begin에는 n보다 크거나 같은 값이 있고 인덱스 end에는 n보다 작은 값이 있습니다. 

그러므로 인덱스 end에 있는 값을 출력하면 됩니다.

 

*이 문제는 처음에는 쉽게 풀릴 줄 알고 풀다가 시간 초과가 나서 고치는 과정에서 짝수인 대칭수는 11의 배수라는 것을 알게 된 재밌는 문제였습니다. 

**계속 느끼지만 그냥 프로젝트 오일러 사이트에서 문제를 푸는 것보다는 Hackerrank가 더 공부에 도움이 되는 것 같습니다.