[SQL] SQL로 소수(Prime Number) 출력하기(HackerRank - Print Prime Numbers 문제)

🔊 본 포스팅에서 사용되는 테이블의 자료와 출처는 HackerRank 임을 밝힙니다. 더 다양한 SQL 문제를 풀어보시려면 HackerRank 사이트를 방문해 보세요!

 

HackerRank 사이트

 

이번 포스팅에서는 SQL로 소수(Prime Number)를 출력해보는 문제를 풀어보려고 한다. 해당 문제를 풀기 위해서 MySQL의 Stored Procedure를 참고해서 풀기도 했지만 일반적인 쿼리문을 통해 해결할 수 있는 풀이를 소개하기 위해 Discussion의 다른 분의 뛰어난 풀이를 참고했다.

 

하지만 문제를 해결해나가면서 MySQL의 Procedure라는 것에 대해 알게 되었고 Procedure 안에서 WHILE, LOOP, ITERATE, IF 등 다양한 문법을 사용할 수 있다는 사실도 알게 되었다. 이에 대해 자세히 알고 싶다면 여기를 클릭해 확인해보자. 그리고 이 Procedure를 활용해 소수를 구하는 풀이의 프레임은 여기를 통해 살펴보자.

 

이번 포스팅에서 해결하는 방법은 평소에 사용해왔던 일반적인 쿼리와 서브쿼리를 이용해 풀어보려 한다. 단순히 SQL 구문만 보아서는 직관적으로 풀이가 와 닿지 않으므로 문제 원본에 들어가 쿼리를 하나하나씩 출력해 살펴보는 것을 권장한다.

우선 문제에서 요구하는 사항은 다음과 같다.

 

Write a query to print allprime numbersless than or equal to 1000. Print your result on a single line, and use the ampersand ('&') character as your separator (instead of a space).
(1000 이하의 자연수들 중 모든 소수값들을 하나의 줄로 출력해라. 이 때 소수값들 사이에 구분자를 '&'를 삽입해 출력해라.)

이 때 소수란, 0.12, 0.567 과 같은 부동소수점을 얘기하는 것이 아닌 나눌 수 있는 수가 자기 자신과 1밖에 없는 숫자를 의미한다. 예를 들면 7은 두 개의 곱셈으로 나누어 본다면 1 x 7 이라는 1가지 조합밖에 존재하지 않는다. 17이나 13도 마찬가지다. 높은 숫자로 올라가면 787도 소수이다.

 

그런데 한 가지 이상한 점이 있다. 테이블이 주어지지 않았는데 대체 어떻게 쿼리를 하란 말인가? 이를 해결하기 위해서는 MySQL 자체에 내장되어 있는 테이블들이 담겨 있는 즉, 우리가 로컬에 MySQL을 깔게 되면 애초부터 존재하는 테이블들을 담고 있는 information_schema 를 이용해야 한다. information_schema에 대한 자세한 내용은 여기를 살펴보자.

 

먼저 해당 문제를 풀이한 SQL 구문부터 살펴보자.

 

SELECT GROUP_CONCAT(NUMB SEPARATOR '&')
FROM (SELECT @num:=@num+1 AS NUMB
      FROM information_schema.tables t1,
           information_schema.tables t2,
           (SELECT @num:=1) tmp
      ) tempNum
WHERE NUMB <= 1000
AND NOT EXISTS (SELECT *
                FROM (SELECT @nu:=@nu+1 AS NUMA
                      FROM information_schema.tables t1,
                           information_schema.tables t2,
                           (SELECT @nu:=1) tmp1
                      LIMIT 1000
                      ) tempNum1
                WHERE FLOOR(NUMB/NUMA) = (NUMB/NUMA)
                AND NUMA < NUMB
                AND 1 < NUMA
               )

 

많이 복잡하다.. 우선 가장 첫 번째에 있는 서브쿼리 형태부터 하나하나 출력해보자. 다음의 SQL 구문을 출력하면 다음과 같다.

 

SELECT *
FROM (SELECT @num:=@num+1 AS NUMB
      FROM information_schema.tables t1,
           information_schema.tables t2
      ) tempNum

 

결과 화면

 

위 화면을 보면 모두 Null 값이 되어 있다. 이 때 information_schema를 2개로 설정한 것은 information_schema를 1개로만 설정해서 모든 row들을 출력하면 1000개의 개수보다 적게 나오기 때문이다. 따라서 추후에 1000개보다 넘는 row들 중 1000개로 LIMIT 하기 위해 2개로 설정한다는 것을 알아두자. 위 쿼리에서 Null 값 대신 1보다 큰 즉 2부터 1씩 커지는 값을 넣어보자.

 

SELECT *
FROM (SELECT @num:=@num+1 AS NUMB
      FROM information_schema.tables t1,
           information_schema.tables t2,
           (SELECT @num:=1) tmp
      ) tempNum

 

결과 화면

 

우리가 원하는 데로 값이 삽입되었다. 사실 위에 SELECT 문만 붙여서 값이 삽입 된다는 사실이 신기 했다. @num 이라는 이미 사용된 변수가 들어가 있기 때문에 알아서 삽입되는 건지.. 이에 대해서는 추가적인 공부가 필요할 것 같다.

 

어쨋든 이제 1000보다 큰 숫자들이 모두 삽입되었으니 조건을 붙여주자. 그리고 조건문에 방금 만들었던 1000개의 숫자가 삽입된 테이블을 하나 더 만들어서 어떤 수가 '소수'인지 필터링해보자.

 

SELECT GROUP_CONCAT(NUMB SEPARATOR '&')
FROM (SELECT @num:=@num+1 AS NUMB
      FROM information_schema.tables t1,
           information_schema.tables t2,
           (SELECT @num:=1) tmp
      ) tempNum
WHERE NUMB <= 1000
AND NOT EXISTS (SELECT *
                FROM (SELECT @nu:=@nu+1 AS NUMA
                      FROM information_schema.tables t1,
                           information_schema.tables t2,
                           (SELECT @nu:=1) tmp1
                      LIMIT 1000
                      ) tempNum1
                WHERE FLOOR(NUMB/NUMA) = (NUMB/NUMA)
                AND NUMA < NUMB
                AND 1 < NUMA
               )

 

주목해야 할 부분은 FLOOR(NUMB/NUMA) = (NUMB/NUMA)를 만족하는 NUMB 숫자들이 바로 소수가 아니라는 점이다. 이에 대해서 간단한 예시를 들어보자.

 

NUMB	NUMA	FLOOR(NUMB/NUMA)	NUMB/NUMA
7	4	1	1.75
6	2	3	3
11	5	2	2.2
10	5	2	2

 

위 테이블을 보면 FLOOR(NUMB/NUMA) 와 NUMB/NUMA 가 동일하다는 조건을 만족하는 NUMB 수들은 소수가 아닌 수들임을 알 수 있다. 즉, 해당 조건을 불만족하는 NUMB 수들이 바로 소수라는 것이다.

 

따라서 이러한 조건이외에 추가적으로 NUMA가 1보다 크고 NUMA < NUMB 이어야 하는 조건 2가지를 더 붙여 원하는 값들인 1000 이하의 소수값들을 출력할 수 있다.

 

이제 마지막으로 구분자인 &를 사이에 넣어서 한 줄로 출력해주어야 하는데 이 때는 GROUP_CONCAT 함수를 사용하면 된다. 필자도 이에 대해서는 처음 알았는데 블로그를 찾아보니 유용한 기능이 많았다. 한 줄로 출력해줄 때 중복을 제거(DISTINCT) 하거나 정렬 순서(ORDER BY)를 정해주기, 지금 문제 풀이에 사용될 구분자 설정 등 다양한 기능이 있었다. 추후에 유용하게 사용해볼 만한 기능인 것 같다.

 

이제 GROUP_CONCAT 까지 설정한 후 최종 결과를 테스트 해보면 정답 처리가 된다. 끝으로 문두에 언급했던 Procedure을 이용한 풀이도 첨부해놓으려 한다. 단, 출력 데이터 길이가 길기 때문에 출력 길이를 설정하는 OUT 부분에 HackerRank 에서 제공하는 최댓값인 16,383 길이를 설정해야 한다.

 

-- Stored Procedure 만들기
DELIMITER $$
CREATE PROCEDURE getPrime(IN n INT,
                          OUT result VARCHAR(16383))
BEGIN
DECLARE j, i, flag INT;
SET j:=2;
SET result:= ' ';
WHILE (j<n) DO
SET i:=2;
SET flag:=0;

WHILE (i<=j) DO
IF (j%i=0) THEN
SET flag:=flag+1;
END IF;
SET i:=i+1;
END WHILE;

IF (flag=1) THEN
SET result:=CONCAT(result, j, '&');
END IF;
SET j:=j+1;
END WHILE;

END $$
-- 만든 Stored Procedure 호출(call)하기
CALL getPrime(1000, @result);
SELECT SUBSTR(@result, 1, LENGTH(@result)-1);