[코딩테스트] Hackerrank SQL Weather Observation Station 18 해커랭크 문제풀이

SQL 코딩테스트 준비를 위해 해커랭크 문제풀이를 해보려고 합니다. 서버는 MySQL을 기준으로 설정하였으며, 문제의 핵심은 sql로 거리공식을 이용해 계산 함수를 이해하는 것입니다. SQL 코딩 능력을 키우고자 하는 분들에게 도움이 될 수 있도록 문제 해결에 필요한 사고 과정과 코드 설명을 상세히 다루었습니다.

 

 

문제 : Weather Observation Station 18 (해커랭크 sql, mysql) 

 

 

난이도 : Medium

서버 : MySQL

테이블 이름 : STATION 

문제 의도 : SQL의 수학 계산 함수를 사용할 수 있는지, 없는지가 관건이다. 이에 거리 공식 중 Euclidean distance(유클리드 거리), Manhattan distance(맨하탄 거리), Hamming distance(해밍 거리) 등 거리 공식을 알고 있는지도 문제이다. 

 

https://www.hackerrank.com/challenges/weather-observation-station-18/problem?isFullScreen=true

Weather Observation Station 18 | HackerRank

 

 

 

 

문제 요약  : P1(a,b), P2(c,d) 두개 포인트의 거리를 구하는 쿼리 작성하시오. 
이떄, 거리는 맨해튼 거리입니다. Manhattan Distance

input sample

output sample

 

 

정답 SQL 코드 :

SELECT
ROUND(ABS(MAX(LAT_N) - MIN(LAT_N)) + ABS( MAX(LONG_W) - MIN(LONG_W)), 4) AS DISTANCE
FROM STATION

 

 

 

풀이과정 : 

(나의 풀이 사고과정 정리) 

 

일단, 거리 공식했을떄, 바로 생각난것은 
유클리디안 거리 공식이었는데, 이에 제곱함수랑 루트함수를 찾고 다음과 같이 코드를 작성했다. 

 

그런데, 다시 보니 맨해튼 거리 공식이었고, 단순히 거리 값만 구하면 되는거라 다중열, 행을 서브쿼리로 두지 않아도 

됬었다. 

 

SELECT 
SQRT(POWER(C-A,2) + POWER(D-B,2)) AS DISTANCE
FROM (
    SELECT ID, 
           CITY, 
           STATE,
           MAX(LAT_N) AS C,
           MIN(LAT_N) AS A,
           MAX(LONG_W) AS D,
           MIN(LONG_W) AS B
    FROM STATION 
    GROUP BY 1,2,3 
)

 

거리 구하는 공식를 정리하자면, 3가지 있습니다. 


1. 유클리드 거리 (Euclidean Distance)

정의 : 두 점 사이의 직선 거리를 측정합니다. 일반적으로 2차원 또는 3차원 공간에서 가장 많이 사용됩니다.


공식 :
- 2차원에서 두 점  (x_1, y_1) 와  (x_2, y_2)  사이의 유클리드 거리 

SELECT 
    SQRT(POWER(x2 - x1, 2) + POWER(y2 - y1, 2)) AS euclidean_distance
FROM 
    points

설명 : 
유클리드 거리는 피타고라스의 정리를 기반으로 하며, 두 점 사이의 직선 거리를 계산합니다. 직관적으로 이해하기 쉽고, 많은 응용 분야에서 사용됩니다.



2. 맨해튼 거리 (Manhattan Distance)

정의 : 두 점 사이의 거리로, 격자 형태로 이동하는 경우의 거리입니다.
이는 도시의 블록 구조와 비슷하게 생각할 수 있습니다.

공식 :
- 2차원에서 두 점 (x_1, y_1) 와 (x_2, y_2) 사이의 맨해튼 거리는 다음과 같습니다:
  
  d = |x_2 - x_1| + |y_2 - y_1|

SELECT 
    ABS(x2 - x1) + ABS(y2 - y1) AS manhattan_distance
FROM 
    points

설명 : 맨해튼 거리는 격자형 경로를 따를 때의 거리를 나타내며, 직선 경로가 아닌 경우에 적합합니다.
주로 최적화 문제나 경로 탐색에서 사용됩니다.



3. 해밍 거리 (Hamming Distance)

정의 : 두 문자열 또는 이진수 간의 차이를 측정하는 거리입니다.
주로 두 문자열의 길이가 동일할 때 사용됩니다.

 

공식 : 

주어진 두 문자열 X와 Y가 있을 때, 해밍 거리는 다음과 같이 계산됩니다.

여기서,

• n은 문자열 X와 Y의 길이입니다.
• δ(Xi,Yi)는 X와 Y의 i번째 문자가 같으면 0, 다르면 1인 함수입니다.

​​

즉, 두 문자열 X와 Y의 각 자리에서 문자가 다르면 1을 더하고, 같으면 0을 더하여 전체 값을 합산하면 해밍 거리가 됩니다.

SELECT 
    LENGTH(string1) - LENGTH(REPLACE(string1, string2, '')) AS hamming_distance
FROM 
    strings

설명 : 해밍 거리는 주로 오류 검출 및 정정 코드에서 사용됩니다.
두 문자열에서 서로 다른 위치의 수를 세어 데이터 전송의 오류를 확인하는 데 유용합니다.

 

예시 : 
두 개의 문자열 1011101과 1001001이 있다고 가정합시다.

1. 두 문자열을 각 자리별로 비교:
2. 1011101 1001001
3. 각 자리를 비교해 보면, 2번째, 5번째, 6번째 자리가 서로 다릅니다.

 

따라서, 다음과 같은 코드를 실행하면 정답!

SELECT
ROUND(ABS(MAX(LAT_N) - MIN(LAT_N)) + ABS( MAX(LONG_W) - MIN(LONG_W)), 4) AS DISTANCE
FROM STATION