구름LEVEL 어느개발자 이야기

 

 

스토리가 있는 알고리즘 문제입니다.

데이터베이스 관리자였던 개발자가 해고를 당해, 회사 DB를 망가뜨려놓았다는 이야기인데요.
얼마나 억울하게 느꼈다면 그랬나 싶기도 하지만, 도의상 그러면 안되겠지요 :)

level.goorm.io/exam/43171/%EC%96%B4%EB%8A%90-%EA%B0%9C%EB%B0%9C%EC%9E%90-%EC%9D%B4%EC%95%BC%EA%B8%B0/quiz/1

구름LEVEL

자, 결국 망가뜨린 자료를 복구하는 것인데요. 
문제를 보고 처음엔 전혀 이해가 되질 않았습니다.

"이게 뭔 소리?" 추리를 하다 하다가, 결국 인터넷 검색 신공,
다른 분이 풀이한 것을 보고 어떤 문제인지 정체를 알아냈지요.
하지만 알고리즘 코딩은 직접 했습니다 :)

요는 말이 혼동이 되는 문제입니다.

"데이터를 N진법으로 표현했을 때 어떤 수의 제곱이 되는 최소값 N"이라고 적혀 있는데요.

"N진법으로 표현된 데이터는 어떤 수의 제곱인데, 이 때 최소값 N을 구하시오"가 적절하지 않을까 생각됩니다.
뭐 추리력을 테스트하는 거라면 할말은 없지만 말이지요 :)

진법이란 무엇일까요? 지구상의 대다수의 사람은 10진법을 사용합니다.
10진법이라는 것은 0, 1, 2, 3, 4, ..., 이렇게 숫자를 세다가 9 다음에는 10이라고 세는 것입니다.
이렇게 세게 된 이유는 아마도 사람의 손가락이 10개이기 때문일 것입니다.
옛날부터 손가락을 굽혀 가면서 숫자를 세어왔기 때문에 열개를 모두 센 것을 하나의 묶음으로 하여
10이란 숫자로 올리는 것으로 인식하는 것이지요.

그런데 만일 사람들이 원래 손가락이 8개나 12개라면 어떻겠습니까?
만일 손가락이 8개라면 사람들은 7까지만 숫자를 세고 그 다음에는 10을 세겠지요.
8개가 모여서 10이 되는 것입니다. 뭐 당연히 60, 70 다음에는 바로 100이 될겁니다.

만일 손가락이 12개라면, 원래의 10과 11이란 숫자는 다른 기호로 대체될 것입니다.
만일 10진수 10과 11이 A와 B로 대체된다면 숫자를 이렇게 세게 될것입니다.
0, 1, 2, 3, ... , 9, A, B, 그리고 다음이 10이 됩니다.

이 것이 바로 진법입니다. 손가락이 원래 8개인 사람이 숫자를 세는 규칙을 8진법,
손가락이 12개인 사람이 숫자를 세는 규칙을 12진법이라고 하겠지요..
참고로 우리가 사용하는 컴퓨터는 2진법을 사용합니다.

아래와 같은 숫자가 주어졌다고 생각해봅시다.

15

 

우리는 아직 이 숫자가 10진법으로 된 숫자인지 8진법인지 12진법인지 아니면 전혀 엉뚱한 659,163 진법인지(설마...) 전혀 알지 못합니다.

확실한 것은 5라는 숫자가 있으니 2~5진법은 아니라는 것입니다.
5라는 숫자를 셀 수 있다는 것은 손가락이 6개 이상이라는 의미이니까요.

하여간 아무 숫자가 주어지든 그 수는 '어떤 숫자'의 제곱이라고 합니다.
제곱이란 동일한 수를 2번 곱한 것을 의미합니다.
10진수든 16진수이든간에 원래의 값은 변동이 없지요.

사실 이 숫자는 11진법으는 15이지만 10진법으로는 16입니다.
16이라면 4의 제곱인데요. 바로 이 '4'라는 숫자를 맞추는 것이 아니라 '11'이라는 진법을 맞추는 것입니다

이 숫자가 우리가 해독해야 하는 목표가 되는 것이지요.
한가지 단서가 더 있습니다.
그 '어떤 숫자'는 여러개의 숫자가 있을 수 있기 때문에 그 중 최소값이 정답이라는 것입니다.

수학적인 이론 설명은 대충 이즈음으로 소개하고 알고리즘 풀이로 들어가 보겠습니다.

첫째. 암호화된 숫자를 먼저 입력받습니다.

둘째, base 라는 변수에 숫자를 2부터 1,000까지 대입시켜서 셋째~넷째 과정에 대해 반복 수행합니다.
이 변수가 바로 '진수'로 사용됩니다. 1,000은 사실 별 근거는 없습니다.
진법의 범위가 명시가 되어 있지 않아 대충 정한 것이지요.
1000까지 모두 진행한 다음에는 다섯째 단계로 이동합니다.

셋째, 입력된 각 숫자의 자릿수를 base 진법이라 가정하고 실제 10진수로 변환합니다.
만일 이 과정에서 진법에 해당하는 숫자와 동일하거나 초과하는 숫자가 포함된다면
'오버플로우'라고 인식하고 둘째 단계로 이동하여 다음 진수를 검사합니다.

넷째, 변환된 10진수가 어떤 숫자의 제곱인지 검사합니다.
만일 맞다면 base 변수의 내용을 출력하고 끝냅니다. 그렇지 않다면 둘째로 이동하여 계속해서 다음 진수를 검사합니다.

다섯째, 1000진법까지 검사했는데도 정답이 없으면 아무것도 출력하지 않고 끝냅니다.

이번에는 php로 알고리즘을 풀이해보았는데요.
모던 php 는 아니고 일반적인 방법으로 단순히 풀어보았습니다.

참고로 php에서는 숫자를 입력받을 때 fgets(STDIN)을 사용하더라구요.
주의하실 점은 Enter 값도 함께 따라오기 때문에 trim 명령어로 앞, 뒤 공백을 잘라주고 시작하시는게 좋습니다.

<?php
	$n = trim(fgets(STDIN));
	$len = strlen($n);
	
	for($base=2;$base<1000;++$base)
	{
		$sum=0;
		$base_multi=1;
		$overflow=false;
		for($i=$len-1;$i>=0;--$i)
		{
			$number_one=(int)substr($n,$i,1);			
			if($base<=$number_one){ $overflow=true; break; }
			$sum+=$base_multi*$number_one;
			$base_multi*=$base;
		}
		if($overflow)continue;
		$sqrt_num=floor(sqrt($sum));
		if($sqrt_num*$sqrt_num==$sum)
		{
			echo $base;
			exit;
		}
	}
?>

 

 

참고로 구름 IDE의 php 버전은 7.1.6입니다.
아래 명령어로 확인하실수 있지요 :)

echo PHP_VERSION;

오늘도 여기까지 읽어주셔서 감사합니다.