아무리 사소하더라도 배움이 없는 날은 없다.
SQL 코드카타 171번
간단한 left join 문제.
s.marks는 값이고 grade는 범위를 통해 구해야 하므로
join의 조건에 between을 써 주는 것만 신경쓰면 됨.
SELECT CASE
WHEN g.grade < 8 THEN 'NULL'
ELSE s.name
end AS name,
g.grade,
s.marks
FROM students s
LEFT JOIN grades g
ON s.marks BETWEEN g.min_mark AND max_mark
ORDER BY 2 DESC,
1 알고리즘 코드카타 60번
이름만 들어도 웅장해지는 무려 '기사단원의 무기' 문제.
숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다.
각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.
예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다. 무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다. 그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.
기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 return 하는 solution 함수를 완성하시오.
<1트> : 테스트 케이스 통과, 제출 결과 오답(59.3)
def solution(number, limit, power):
x = []
for i in range(1,number+1):
count = 0
for j in range(1,i+1):
if i%j == 0:
count +=1
x.append(count)
for k in x:
if k > limit:
x.remove(k)
x.append(power)
return sum(x)테스트 케이스는 통과했는데 제출 결과 오답이 떴다.
커버하지 못한 케이스도 있었지만 그건 로직을 수정하면 해결할 수 있겠다는 느낌이 있었다. 그보다 좀 더 크리티컬한 건 시간 초과로 오답이 뜬 케이스가 훨씬 많다는 것.
아무래도 number가 최대 100,000까지 가능하다 보니 이걸 하나씩 반복문으로 돌리면서 약수 개수 확인하고, 그걸 다시 limit와 하나씩 대조하는 과정에서 시간을 많이 잡아먹는 것 같았다. (아직 잘 이해하지 못하는 개념이지만, 시간복잡도 O(n^2)짜리라고 한다.) 구글 colab 환경에서 number를 100,000으로 주고 테스트해 본 결과 무려 7분 32초가 나왔다!
우선 문제가 된 상황들을 하나씩 해결해 보기로 했다.
- 로직이 틀려서 오답이 된 케이스 해결
위의 함수에서는 x에 들어있는 원소 k가 limit을 초과할 경우 x에서 k를 제거하고 power를 넣어주었다. 리스트에서 문자열은 replace를 써서 쉽게 교체할 수 있으나 숫자에는 적용되지 않기 때문에 생각해 낸 방법이었는데, 저렇게 쓰면 반복문의 대상인 x 자체가 변경되기 때문에 반복 과정에서 문제가 생길 수 있다.
따라서 'limit보다 큰 경우에는 k 대신 power를 넣어준다'라는 부분을 수정할 필요가 있다. 아예 새로운 리스트 y를 선언해서 limit보다 작은 경우 power를 y에 append하는 등의 방식으로 할 수도 있지만, 보다 간단하게 리스트 컴프리핸션으로 처리가 가능하다.
<2트> : 테스트 케이스 통과, 제출 결과 오답(66.7)def solution(number, limit, power): x = [] for i in range(1,number+1): count = 0 for j in range(1,i+1): if i%j == 0: count +=1 x.append(count) x2 = [power if k > limit else k for k in x] return sum(x2)
2트 결과 정답률이 올라갔다. 커버하지 못한 케이스는 더 이상 없게 됐고, (즉 로직 자체에는 문제가 없게 됐고) 시간이 너무 오래 걸려서 오답 처리된 케이스만 남았다. 약수의 개수를 구해주는 부분의 시간을 줄여야 하는데...
지난 토요일 해결했던 알고리즘 코드카타에서, 어떤 수가 소수인지 여부를 판정하기 위해 약수의 개수를 구할 때 1부터 자기 자신까지 모두 반복하지 않고 제곱근+1까지만 반복했던 게 생각났다. 이렇게 하면 큰 수여도 끝까지 다 반복하지 않아서 시간 복잡도가 줄어드는 이점이 있었다. 이 문제에서 number의 최대값은 100,000인데, 제곱근 언저리까지만 검증하면 되니까 310 내외에서 끝낼 수 있다는 말.
- 시간복잡도 때문에 오답이 된 케이스 해결
<3트> : 정답def solution(number, limit, power): x = [] #1부터 number까지 각 수의 약수 개수를 저장 for i in range(1, number + 1): #1부터 number까지 반복 count = 0 #약수 개수 초기값은 0 sqrt_i = int(i**0.5) #i의 제곱근 sqrt_i 선언 for j in range(1, sqrt_i+1): #number의 각 수 i에 대해, 다시 1부터 i제곱근+1까지 반복하며 if i%j == 0: #만약 j가 i의 약수라면 count += 1 #count에 1씩 증가 if j != i//j: #j가 i를 j로 나눈 몫과 다르다면 (즉, 1과 6, 2와 3 등으로) count += 1 #count에 한 번 더 1을 증가(반대쪽 약수도 세어줘야 하므로) x.append(count) #x에 count를 추가 x2 = [power if k > limit else k for k in x] #x의 요소 k에 대해 k가 limit보다 크다면 power로 대체한 x2 선언 return sum(x2) #x2의 합을 구해 반환
약수의 개수 구하는 부분이 많이 복잡했지만 정답을 도출하는 데는 성공했다.
심지어 실행 시간은 7분에서 1.26초로 줄었다!
만약 i가 9라면 j는 1부터 4까지 검증하는데,
- 1은 9의 약수이므로 count에 1 추가
그리고 1은 9//1, 즉 9와 다르므로 count에 또 1 추가 (이게 핵심) - 2는 9의 약수가 아님
- 3은 9의 약수이므로 count에 1 추가
그리고 3은 9//3, 즉 3과 같으므로 count에 또 1을 추가하지 않는다 - 4는 9의 약수가 아님
- 결론적으로 i가 9일 경우 count는 3이 되는 것
약수는 항상 쌍으로 존재하므로
j != i//j 조건을 넣어서 참이면 count에 1을 더해주는 것이다. 이 조건은 완전제곱수인 경우에는 중복해서 count되면 안 되기 때문에 더욱 유용하다. 만약 이렇게 하기 복잡하다면 그냥 제곱근까지 검증해서 약수를 모두 넣은 다음에 set을 써서 중복을 제거해도 될 것 같긴 하다.
이중반복문의 볼륨이 커질 때 생길 수 있는 시간복잡도 문제를 해결하기 위해 리스트 컴프리핸션이나 제곱근까지만 검증하는 방법 등 테크닉 활용을 배웠던 문제.
