[코드트리 챌린지] 8주차 - 중급 자료구조

dev_Hyun·2023년 10월 25일

코드트리 챌린지

목록 보기

8/8

0) 들어가기 앞서

어느덧 코드트리 블로그 챌린지의 마지막 8주차 이다. 2개월이란 시간이 순식간에 지나갔고, 코드트리에서 코테를 학습하는 행동이 주중 아침을 시작하는 루틴으로 자리잡혔다. 챌린지가 마감되어도 주차마다 진단테스트를 수행하고 저장소에 업로드하는 것을 유지해보면 의미있을 것 같다 :)

1) 실력 진단 결과

비록 다시 700점대로 진입했으나, 투 포인터 유형으로 추정되는 문항에서 시간초과로 풀이에 성공하지 못한 것이 아쉬웠다. (투 포인터, HashMap 두 가지 방법으로 모두 풀이 가능한 문항이었다. 아래 리뷰를 참고.)

테스트 결과 IM단계의 중급 자료구조를 학습하라는 진단을 받았고, 이번 마지막 주차는 해당 유형을 학습하겠다!

2) 중급 자료구조 HashMap

문제1

두 수의 합 (링크 : https://www.codetree.ai/cote/20/problems/sum-of-two-num?&utm_source=clipboard&utm_medium=text)
실력진단테스트에서 출제된 문항과 비슷한 문항이다.

리뷰

HashMap 사용 풀이

n, k = map(int, input().split())
arr = list(map(int, input().split()))

dic = dict()
count = 0

for num in arr:
    if k - num in dic:
        count += dic[k - num]
    dic[num] = dic.get(num, 0) + 1

print(count)

문제2

원소의 합이 0 (링크 : https://www.codetree.ai/missions/8/problems/the-sum-of-the-elements-is-0?&utm_source=clipboard&utm_medium=text_

리뷰
두 가지 중점이 있었다.

조합을 (A,B) (C,D) 두 쌍만 고려한 것.
합이 일치하는 항목을 찾은 후, 해당 항목을 삭제하지 않는 것.

먼저, (A, C) (B, D) 등을 고려하지 않고, (A,B) (C, D) 쌍만 고려한 이유는 어떤 수열끼리 쌍을 이룰지는 중요하지 않고, 어떤 수열끼리 쌍을 이루던 네 개의 숫자의 모든 조합이 고려된다.

그리고 모든 조합을 고려하기 위해서 두 번째 중점처럼 일치하는 합 항목을 찾은 후, 해당 항목을 삭제하지 않아야 한다. 만약 삭제할 경우 동일한 합을 가진 다른 잠재적인 쌍을 고려하지 않게 되기 때문이다.

다음 케이스를 살펴보면 잠재적인 쌍을 고려해야 함을 알 수 있다.
n = 2
arr = [1, 2]
brr = [-1, -2]
crr = [1, 2]
drr = [-1, -2]
arr, brr 에서 만들 수 있는 조합은
(1, -1), (1, -2), (2, -1), (2, -2) 이고, 이를 dictionary에 key(합) value(개수) 형태로 저장하면 dic = {[0:2], [1:1], [-1:1]} 이다.

crr, brr 에서 만들 수 있는 조합도 (1, -1), (1, -2), (2, -1), (2, -2) 이다. 합은 0, -1, 1, 0 순서이다. crr, brr 쌍의 합 0을 먼저 찾으면 2개 이다. 이를 의미하는 쌍은 (1, -1, 1, -1) 과 (2, -2, 1, -1) 이다. 그런데 해당 항목을 삭제하게 될 경우 crr, brr 에서 만들어지는 쌍 (2, -2) 에 대해 고려할 수 없게 된다.

다음 케이스들도 유사하다.

n = 2
arr = [1, 1]
brr = [-1, -1]
crr = [1, 1]
drr = [-1, -1]

n = 2
arr = [0, 0]
brr = [0, 0]
crr = [0, 0]
drr = [0, 0]

따라서 위 두 중점을 고려하여 코드를 작성하면 다음과 같다.

n = int(input())
arr = list(map(int, input().split()))
brr = list(map(int, input().split()))
crr = list(map(int, input().split()))
drr = list(map(int, input().split()))    

dic_ab = dict()
ans = 0

for i in arr:
    for j in brr:
        dic_ab[i + j] = dic_ab.get(i + j, 0) + 1

for i in crr:
    for j in drr:
        diff = -(i + j)
        if diff in dic_ab:
            ans += dic_ab[diff]
            # del dic_ab[diff]
            
print(ans)

3) 경품 추첨

블로그 챌린지 7주차 보상으로 경품 자동 응모가 되었다고 한다. (결과는 To be continue...)

dev_Hyun

공룡, 다람쥐 그리고 돌고래!

이전 포스트

[코드트리 챌린지] 8주차 - 중급 자료구조