240508_TIL

아무리 사소하더라도 배움이 없는 날은 없다.

알고리즘 코드카타 33번

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

분기를 여러 번 타야 하는 알고리즘이다.

1. 우선 left와 right 모두에 대해 1부터 left(right)까지 숫자로 나누어서 나누어 떨어지는 수(약수)를 구한다.
2. 약수가 모여있는 리스트에 대해 리스트의 길이를 재서
   1. 홀수면 마이너스를 붙여서 리턴하고
   2. 짝수면 그냥 리턴한다
3. 마지막으로 2의 결과를 모두 더한다.

이 과정을 그대로 알고리즘에 구현하려면 반복문과 조건문이 굉장히 여러 번 중첩되어야 해서 구현하기 쉽지 않았다. 해서 방법을 바꿔본 것이 숫자의 성질을 이용하는 것.

어떤 수의 약수의 개수가 홀수 개라는 것은 완전제곱수라는 뜻이다. 즉, 4는 2의 완전제곱수이므로 약수가 1,2,4 이렇게 홀수 개의 약수를 갖는다. 9나 16 등의 다른 완전제곱수도 마찬가지. 반면 6의 약수는 (1,6), (2,3) 이렇게 짝수 개고, 둘씩 짝지어 묶을 수 있다. 이 성질을 이용해 구현해 보면

def solution(left, right):
    answer = 0
    for i in range(left, right+1):
        if int(i**0.5)==i**0.5:
            answer -= i
        else:
            answer += i
    return answer

left부터 right(그냥 right이 아니라 +1임에 주의)까지 숫자 i를 반복하는데,

1. i의 제곱근(**0.5)을 정수화(int)한 값이 실제로 i의 제곱근과 정확히 일치한다면 (즉, 약수의 개수가 홀수라면) answer에 i만큼을 빼 나가고
2. 그렇지 않다면 (즉, 완전제곱수가 아니므로 약수의 개수가 짝수라면) answer에 i만큼을 더해나간다

이렇게 쓸 수 있다. 파이썬 코드를 치는 기술보다는 다루게 될 데이터의 성질을 더 깊게 생각하면 의외로 쉽게 풀리는 문제.

---

SQL 코드카타 107번
primary department가 있는 직원이라면 id와 primary department에 해당하는 부서번호를, primary department가 없는 직원이라면 그냥 id와 부서번호를 함께 출력하는 문제.

① primary department가 있는 경우에는 그걸 뽑는다

select employee_id, department_id
from Employee
where primary_flag = 'Y'
group by 1

② primary department가 없는 경우에는 하나만 출력되므로

select employee_id, department_id
from Employee
group by 1 having count(*) = '1'

③ ①과 ②를 합쳐서 출력하면 끝

SELECT employee_id,
       department_id
FROM   employee
GROUP  BY 1
HAVING Count(*) = '1'
UNION
SELECT employee_id,
       department_id
FROM   employee
WHERE  primary_flag = 'Y'
GROUP  BY 1 

SQL 코드카타 108번

세 변의 길이가 주어질 때 삼각형이 성립할 조건을 묻는 문제. 삼각형이 성립할 조건이 뭐더라?를 생각해내는 게 제일 어려웠다....😂

쿼리 자체는 간단.

SELECT x,
       y,
       z,
       CASE
         WHEN x < y + z
              AND y < x + z
              AND z < x + y THEN 'Yes'
         ELSE 'No'
       end AS triangle
FROM   triangle

SQL 코드카타 109번
어떤 숫자가 3회 이상 연속해서 나타날 경우 그 숫자가 뭔지를 묻는 문제. lag함수를 써서 해결해 보려고 용을 쓰다가 시간을 더 쓸 수 없어서 팀원 찬스를 썼다ㅠ 일명 자가복제 문제.

의외로 window함수 없이도 간단하게 풀리는 문제다.

먼저 cross join을 써서 똑같은 테이블 logs 3개를 join해 모든 경우의 수를 만든다

SELECT
	*
FROM
	logs AS logs1
CROSS JOIN logs AS logs2
CROSS JOIN logs AS logs3

그리고 where 조건을 써서 id와 num이 세 번 연속 같은 경우를 찾아주면 된다. a=b, b=c이면 a=c이므로 조건은 두 번만 적으면 됨.

SELECT
	DISTINCT logs1.num AS ConsecutiveNums
FROM
	logs AS logs1
CROSS JOIN logs AS logs2
CROSS JOIN logs AS logs3
WHERE
	logs1.id + 1 = logs2.id AND logs1.num = logs2.num
	AND logs2.id + 1 = logs3.id AND logs2.num = logs3.num

같은 컬럼에 동일한 값이 여러 번 나오고, 그 숫자를 세서 활용해야 하는 경우에는 지난 번 풀었던 문제처럼 스칼라 서브쿼리를 써서 비율을 계산하거나 아니면 이번처럼 자가복제 문제라고 생각하고 접근해야겠다. 딱 보면 오는 감이라는 걸 만들어야 할 듯.

오늘은 알고리즘과 SQL 코드카타 모두 시간이 너무 오래 걸렸다.