[TIL 코테]-해시와 관련된..

코딩테스트 공부기

무엇보다도 코딩테스트를 본격적으로 시작하는데 있어서 프로그래머스의 고득점kit로 핵심적인 영역들을 공부하기로 마음을 먹고 시작하였다

2022-07-01

1.해시

기본적으로 문제를 풀 때 해시와 관련된 문제에서의 특징을 느껴보자면 예를 두 리스트가 있을 때 중복되는게 있을 때 분명 set()를 생각해볼 수 있을 것이다.중복성 제거?아니면 이런것 때문에?? 하지만 예를 들어 문제에서 같은 것이 여러개가 존재하는데 이 상태에서 set를 쓰면 다른 리스트와의 비교가 있을 때 하나로 줄어드니 쉽지않다는 것을 알 수 있을 것이다.
따라서 같은 원소들에 대해서 개수로 비교가 쉽다는 것을 파악가능!

🔑무엇인가 중복되는 요소들이 있을때 걔네들의 개수체크 필요할때

추가적으로 해시에서의 모든 탐색,삽입,삭제,수정은 O(1)이다.이런 점에서 상당히 매력적인 자료구조임을 알 수 있다.

🚩기본적인 해시 코드 작성틀

	hash=dict()
	for x in hash:
    	if x in hash:
        	hash[x]+=1
        else:
        	hash[x]=0
    return hash

이와 같이 되는 원리로 코드를 짜는 것을 기억하고 이걸 응용하면 거의 다 풀리는 듯 하다.

🙌하지만 해시과 나온다면 Counter객체를 꼭 써볼 것을 강추!-상당히 편해

	from collections import Counter
    Counter(리스트)
    #이런식으로 하면 해당 리스트에 대한 각 요소들에 대한개수로 키-밸루로 카운터 객체를 만들어줌
    

단 저걸 그대로 쓰기는 자료형이 Counter 오브젝트라 힘드니 dict()로 형변환 해주자

	dict(Counter(리스트))

추가적으로 Counter객체는 연산이 가능하여

	Counter(리스트a)-Counter(리스트b)
    #중복되는 값들의 차가 가능함
    Counter(리스트a)+Counter(리스트b)
    #중복되는 값들은 밸류가 더해져서 연산됨

꼭 써보자

---

🚩문제를 풀어보면서 느낀 점

1.해시문제에서는 Counter를 사용하면 정말 빈도 수를 쉽게 알아낼 수 있다

2.만약 숫자를 표현한 문자열 ex)"123"이런 것을 정렬하면 앞에 순서부터 정렬된다

3.접두어나 이런 기본 바탕의 아이디어는 빈 문자열에다가 더해가는 원리

4.조합같은 것을 필요로 하는 문제에서 모든 조합을 생각하기 힘들면 없는 경우를 추가적으로 +1해서 생각한 후 나중에 빼줘도 좋다!

5.해시들 또한 정렬에 자유롭게 하자-이중 딕셔너리 가능