99클럽 코테 스터디 9일차 TIL [04/10]

김뚱입니다 2025. 4. 10. 22:53

[시작]

참여 기간 : 2025/03/31 ~ 2025/04/28

참여 난이도 : 파이썬 / 비기너

⏳ 코테 스터디 진행도 🧱 : [▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰░                                 ] 9/29일 (31%)

본 글에서 다룬 문제 : leetcode(Design HashMap)

문제 푸는 데 걸린 시간 : 타이머 시작을 깜빡함. 10분 내외 소요

잠 참으면서 겨우 작성함

글 말투가 딱딱할 수 있음

[오늘의 문제]

[문제 해석 및 분석]

HashMap을 설계해라는데, 내장 해시 테이블 라이브러리는 사용 금지 조건임

MyHashMap()
- 새로운 객체를 생성, 빈 해시맵으로 초기화
void put(int key, int value)
- key와 value를 해시맵에 추가
- 만약 key가 이미 존재한다면, 기존의 값을 새로운 value로 덮어씀
int get(int key)
- 주어진 key에 매핑된 값을 반환
- 해당 key가 해시맵에 없다면 -1을 반환
void remove(int key)
- 해시맵에 key가 존재하면, 해당 key와 관련된 값을 삭제
제약 조건
- 0 <= key, value <= 10^6
- 최대 10⁴번까지 put, get, remove가 호출

일단 해석한 결과는 위와 같고

문제를 분석하기 전 Hash가 뭔지 간단하게 알고 넘어가려 함

Hash(해시)는 데이터를 빠르게 저장하고 검색하기 위한 방식임

어떻게?

어떤 값을 고정된 범위의 숫자로 바꿔주는 함수 또는 방식을 사용해서.

예시를 통해 이해해 보자.

내가 어떤 문자열, 숫자, 데이터를 갖고 있는데

이걸 그냥 저장하면 느릴 수 있음

그래서 특정 값 → 고정된 숫자(인덱스)로 바꿔서 배열처럼 빠르게 접근하는 거임

이때 사용하는 건 해시 함수

key = "chicken"  
→ hash("chicken") = 3  
→ arr[3]에 "chicken" 관련 데이터를 저장

key = "banana"  
→ hash("banana") = 7  
→ arr[7]에 저장

해시가 뭔지 이해했으니 문제에서 나온 해시맵이 뭔지도 알아보자

해시맵은 해시를 활용해서 key → value 구조로 데이터를 저장하는 구조임

Key → Value
"chicken" → 50
"banana" → 29
"meme" → 1234

구조는 위와 같은데 이걸 어떻게 내부적으로 구현하냐면

"chicken" 같은 key를 hash() 함수로 숫자로 바꾼 뒤

그 숫자를 인덱스로 사용해서 배열이나 리스트 안에 value를 저장함

이렇게 하는 이유는 빠르고, 배열처럼 접근하니까 시간복잡도가 보통 O(1)에 동작하기 때문에 사용함

그러니까 이 문제는 이런 내부 동작 원리를 구현해 봐라는 문제

우리가 구현할 HashMap은 아래의 3가지 연산을 지원해야 함

put(key, value)
- key에 value 저장 (덮어씌우기도 포함)
get(key)
- key가 존재하면 value 반환, 없으면 -1
remove(key)
- key와 연결된 값을 삭제

아 사실 이 문제를 풀 수 있는 여러 방법이 있겠지만....

너무 피곤해서 그냥 빠르게 정답을 맞힐 수 있는 방식으로 선택해서 풀어보려 함

배열을 사용할 생각이고 이유는 구현하기 제일 간단할 것 같아서.

0 <= key, value <= 10^6라고 했으니

배열의 index를 key처럼 사용하면 될 것 같다. 직접 접근 가능하니까 빠르지 않을까?

사실 문제의 취지는 해시와 해시맵을 구현하면서 이해도를 높이라는 것 같은데

다음에 그렇게 해보겠다... 눈이 너무 감김... 피곤해서 속도 좋지 않아서 pass

일단 내 생각대로 코드를 구현해 보겠다.

[코드]

class MyHashMap:
    def __init__(self):
        self.map = [-1] * 1000001 

    def put(self, key: int, value: int) -> None:
        self.map[key] = value     

    def get(self, key: int) -> int:
        return self.map[key]      

    def remove(self, key: int) -> None:
        self.map[key] = -1        

        


# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

가볍게 설명함

저 MyHashMap이라는 클래스를 만들어서 put, get, remove 기능을 넣었음

self.map = [-1] * 1000001으로 해시맵에 쓸 기본 리스트를 만들었음

key가 최대 10^6이므로 길이는 저렇게 했고, 모든 값을 -1로 초기화해서 값이 없다는 걸 표현했음

그리고 위에서 이야기했듯 이 리스트에서는 key를 그대로 인덱스로 사용함

def put에서는 key를 인덱스 삼고 해당 위치에 value를 저장하며 이미 값이 있으면 그냥 덮어씀

한마디로 저장과 수정 둘 다 처리함

def get에서는 key를 인덱스로 삼아 값을 읽어오고

만약에 존재하지 않는다?

아까 초기값을 -1로 지정해 놔서 01이 반환되면 해당 key는 없음으로 간주함

def remove에서는 해당 key 위치에 저장된 값을 제거하고

실제로 값을 없애는 대신 다시 -1로 바꿔주는 방식으로 처리함

[제출 결과]

[시간복잡도]

내가 제출한 코드는 현산 하나마다 배열 인덱스에 접근하거나 수정만 함

대신 [-1] * 1000001 이렇게 리스트 생성을 하는데

이건 처음 생성할 때만 시간이 소요되므로 시간복잡도는 O(10^6)

나머지 메서드는 인덱스 접근 + 대입 정도여서 시간 복잡도는 O(1)

문제 조건에 따라 최대 전체 연산이 10^4회여도 시간복잡도는 O(10^4)

그런데 처음 생성할때만 소요되는 시간은 한 번만 소요되니까 무시해도 되지 않을까?

그러면 이 코드의 시간복잡도는 O(10^4) 정도가 된다.

[다른 접근 방법]

나는 문제 조건보다 큰 리스트를 만들어서 key를 인덱스로 사용한 방법으로 솔루션했다.

다른 방법은 비슷하게 리스트를 이용한 방법인데

key, value 쌍을 리스트에 쭉 저장해서 key를 찾을 때마다 리스트를 처음부터 끝까지 순회하면 되지 않을까

이렇게 하면 그렇게 긴 코드는 아닐 것 같고 시간복잡도도 엄청나게 크진 않을 것 같다.

다만 리스트를 매번 처음부터 끝까지 순회하므로 효율적이진 않을 듯하다.

지금 이 문제에서야 제한적인 횟수로 반복하니까 그렇지 많은 데이터를 이런 식으로 구현한다? 무리일듯함

물론 다른 방법으로도 구현할 수 있겠지만 그건 다음에 도전...

[회고]

이전에 접했던 문제들을 풀었던 방식과 비슷하게 풀었다.

해시맵을 다른 방법으로도 분명 풀 수 있을 것 같은데 지금은 어떻게 풀어야 할지 모르겠음

해당 부분 공부의 필요성을 느꼈고 추가적으로 다른 접근법을 알게 되면 글을 수정하여 추가하거나 댓글로 작성할 예정

코딩테스트가 좋은 점이 내가 무엇이 부족한지 명확하게 알 수 있어서 좋다.