[코드트리 챌린지] 두번째 학습진단 HashMap

오늘은 두 번째 학습진단을 진행하였다.

하지만 지난번 보다 일찍 문제를 틀려서 746점으로 내려갔는데, HashMap을 사용하는 문제였다.

문제 풀이 방향은 잘 잡은 것 같은데, 시간 초과가 나타나 결국 틀리고 말았다.

문제를 틀린 김에 HashMap 자료구조에 대한 개념을 다시 잡고 가야겠다.

 

HashMap

Python에서는 HashMap 자료구조가 dict라는 class로 구현되어 있다.

HashMap은 key와 value 값으로 짝을 이루어 저장되는 구조이다.

따라서 key 를 통해 value를 빠르게 꺼내 쓸 수 있다.

순서 없이 저장되며,

삽입, 삭제, 탐색의 시간 복잡도는 O(1)이다.

 

(1)  Dictionary 선언

python에서는 dict() 함수를 호출하거나 {} 괄호를 통해 딕셔너리를 선언할 수 있다.

dictionary1 = dict()
dictionary2 = {}

 

(2) Dictionary 삽입

딕셔너리에 값을 입력하는 방법은 대표적으로 두 가지가 있다.

• dictionary = {key1:value1, key2:value2}
  dictionary선언과 함께 한 번에 key:value 형태로 입력하는 방법 (초기화)

dictionary1 = {
                "apple" : 1,
                "banana" : 2,
                "orange" :3
}
print(dictionary1) # {'apple': 1, 'banana': 2, 'orange': 3}

• dictionary[key] = value
  한 개씩 dictionary에 key와 value를 입력하는 방법

dictionary2 = dict() # 선언
dictionary2["kiwi"] = 4 # 삽입
print(dictionary2) # {'kiwi': 4}

 

(3) Dictionary 삭제

Dictionary에서 삭제는 key 값을 통해 이루어진다. 여기에는 대표적으로 두 가지 방법이 있다.

• dictionary.pop(key) 사용하기

dictionary1 = { "apple" : 1, "banana" : 2, "orange" :3 } # 선언
dictionary1.pop("apple") # 삭제
print(dictionary1) # {'banana': 2, 'orange': 3}

• del dictionary[key] 사용하기

dictionary1 = { "apple" : 1, "banana" : 2, "orange" :3 } # 선언
del dictionary1["apple"] # 삭제
print(dictionary1) # {'banana': 2, 'orange': 3}

 

(4) Dictionary 탐색

Dictionary에 탐색하는 방법은 다음과 같다.

• key in dictionary
  Dictionary에 특정 값(key)이 있는지 확인하는 방법

dictionary1 = { "apple" : 1, "banana" : 2, "orange" :3 } # 선언
print("apple" in dictionary1) # True
print("kiwi" in dictionary1) # False

• dictionary[key]
  Dictionary의 key에 해당하는 value를 가져오는 방법

dictionary1 = { "apple" : 1, "banana" : 2, "orange" :3 } # 선언
print(dictionary1["apple"]) # 1
print(dictionary1["orange"]) # 3

 

(5) Dictionary에 담긴 데이터 확인하기

Dictionary에 담긴 모든 key와 value를 각각의 리스트 형태로 추출할 수 있다.

• dictionary.keys()
  모든 key들을 리스트 형태로 반환한다.

dictionary = {'red': 3, 'blue': 3, 'green': 1} # 선언
print(dictionary.keys())
# dict_keys(['red', 'blue', 'green'])

• dictionary.values()
  모든 value들을 리스트 형태로 반환한다.

dictionary = {'red': 3, 'blue': 3, 'green': 1} # 선언
print(dictionary.values())
# dict_values([3, 3, 1])

• dictionary.items()
  모든 key와 value 쌍을 리스트 형태로 반환한다.

dictionary = {'red': 3, 'blue': 3, 'green': 1} # 선언
print(dictionary.items())
# dict_items([('red', 3), ('blue', 3), ('green', 1)])

 

틀렸던 문제와 유사한 문제를 풀어보면서 dictionary의 활용에 좀 더 익숙해져야겠다.

https://www.codetree.ai/landing/level-test/5888/result/4?&utm_source=clipboard&utm_medium=text 

문제

두 수의 합 문제는 다음과 같다.

n개의 정수로 이루어진 수열이 입력되었을 때, 서로 다른 위치의 두 수를 뽑아 더한 값이 k가 되는 경우의 수를 구하는 문제이다.

 

코드

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

numb = dict()
cnt = 0

for i in range(n):
    # 현재 값과 짝꿍이 될 수 있는 값을 말한다.
    diff = k - arr[i] 
    
    # 짝꿍이 될 수 있는 값이 이미 딕셔너리에 추가되어 있다면 
    # 현재 값과 짝꿍이 될 후보가 그 수만큼 있다는 뜻이다.
    # 즉 그 수만큼 경우의 수가 증가하면 된다.
    if diff in numb:  
        cnt += numb[diff]
    
    # 현재 값은 다른 숫자들의 짝꿍 후보가 될 수 있기에
    # 딕셔너리에 현재 값을 넣어준다.
    # 이미 같은 값이 존재한다면 개수를 늘려주면 된다.
    if arr[i] in numb:
        numb[arr[i]] += 1
    else:
        numb[arr[i]] = 1

# 마지막 경우의 수를 출력한다.
print(cnt)