알고리즘/해시5

• 

  [프로그래머스] 폰켓몬 - 파이썬(python) 나의 풀이 def solution(nums): return min(len(nums)/2, len(set(nums))) set 을 이용해서 중복된 것들을 지우는 것이 포인트이다. 처음에는 너무 어렵게 생각해서, hash dictionary 를 만들고 난리를 쳤는데.... 중복되지 않은 종류의 개수를 모두 세었을 때 전체 포켓몬 숫자 / 2 보다 작다면, 해당 종류의 개수가 정답이 될 것이다. 반면, 중복되지 않은 종류의 개수가 포켓몬 숫자 / 2보다 많다면, 종류가 다르더라도 다 데려갈 수 없으므로 포켓몬 숫자 / 2가 정답이 될 것이다. 알고리즘/해시 2022. 9. 1.

• 

  [프로그래머스] 베스트앨범 - 파이썬(python) 나의 풀이 def solution(genres, plays): answer = [] dic = {} dic2 = {} # dic 에 key : 장르, # value : 장르 총 재생횟수 를 저장한다. # dic2 에 key : 장르, # value : (수록곡 재생횟수, 고유번호) 을 저장한다. for i, (j,k) in enumerate(zip(genres, plays)): if j not in dic : dic[j] = plays[i] else : dic[j] += plays[i] if j not in dic2 : dic2[j] = [(plays[i], i)] else : dic2[j].append((plays[i],i)) # dic 의 (key, value) 에 대해 value 값으로 내림차순 정.. 알고리즘/해시 2022. 5. 6.

• 

  [프로그래머스] 위장 - 파이썬(python) 나의 풀이 def solution(clothes): clothes_hash = {} count = 1 for _, i in clothes : if i in clothes_hash : clothes_hash[i] += 1 else : clothes_hash[i] = 2 for i in clothes_hash.values(): count *= i return count - 1 옷의 종류를 key 로 생각하여 해시 테이블을 생성한다. 조합을 구할 때는 (옷 종류별 개수 + 1) 끼리 곱해주면 된다. 옷 종류별로 하나의 옷만 입을 수 있기 때문에 개수가 경우의 수가 되고, 1을 더하는 이유는 옷을 안 입는 경우도 더해야 하기 때문이다. 그리고 전체 경우의수에서 -1을 해야 옷을 하나도 안 입는 경우를 빼야 한다.. 알고리즘/해시 2022. 5. 5.

• 

  [프로그래머스] 전화번호 목록 - 파이썬(python) 내 풀이 def solution(phone_book): phone_book.sort() for i in range(len(phone_book) - 1) : if phone_book[i+1].startswith(phone_book[i]) : return False return True 해싱을 사용하지 않고, startswith 라는 엄청 유용한 함수를 사용하여 간단하게 풀었다. 파이썬에서 숫자 문자열을 sort() 하면, 숫자의 크기가 아닌 사전 형식으로 정렬이 된다. 즉, ["12", "123", "1235", "567", "88"] 과 같이 정렬된다. -> 이는, 접두사를 비교할 때 인접한 인덱스 두 개만 비교를 하면 된다는 뜻이다. 다른 풀이 (1) def solution(phoneBook): pho.. 알고리즘/해시 2022. 5. 5.

• 

  [프로그래머스] 완주하지 못한 선수 - 파이썬(python) 내 풀이 def solution(participant, completion): hash = {} # key: 참가자 이름, value: 참가자 숫자를 담은 해시 딕셔너리 for i in participant : if i in hash : # 해시테이블에 존재하는 이름이라면 hash[i] += 1 else : hash[i] = 1 for i in completion : if hash[i] == 1 : del hash[i] else : hash[i] -= 1 return list(hash.keys())[0] 동명이인이 존재한다는 조건에 따라 해시 테이블을 만들었다. {key :참가자 이름 value: 완주자 수} 완주자 배열을 반복하면서, 해시 테이블에 있는 참가자 숫자를 1씩 뺀다. 완주자 배열을 모두 돈.. 알고리즘/해시 2022. 5. 5.