Hash

LeetCode 1. Two Sum bruteforce Easiest way to solve this problem is bruteforcing. For each pair of integers, check whether their sum equals to target. If so, return their indexes. Time Complexity = $ O(n^2) $ class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> ans; for (int i=0; i<nums.size(); i++){ for (int j=i+1; j<nums.size(); j++){ if ((nums[i] + nums[j]) == target){ ans = {i, j}; } } } return ans; } }; hash In order to reduce Runtime, implementing hash table will work. Searching in hash table is much faster than doing in array. ...

베스트앨범 문제 바로가기 나의 풀이 def solution(genres, plays): playlist = {} count = {} for idx, (g, p) in enumerate(zip(genres, plays)): if g in playlist: playlist[g].append((p,idx)) count[g] += p else: playlist[g] = [(p,idx)] count[g] = p ans = [] for g in sorted(count.items(), reverse=True, key=lambda x:x[1]): for p in sorted(playlist[g[0]], reverse=True, key=lambda x:x[0])[:2]: ans.append(p[1]) return ans 고수의 풀이 def solution(genres, plays): answer = [] d = {e:[] for e in set(genres)} for e in zip(genres, plays, range(len(plays))): d[e[0]].append([e[1] , e[2]]) genreSort =sorted(list(d.keys()), key= lambda x: sum( map(lambda y: y[0],d[x])), reverse = True) for g in genreSort: temp = [e[1] for e in sorted(d[g],key= lambda x: (x[0], -x[1]), reverse = True)] answer += temp[:min(len(temp),2)] return answer 출처 CODE REVIEW 멜x, 벅x, 스x티파이와 같은 음원 프로그램에서 쓸 법한 정렬 문제. 총 재생수로 genres를 정렬한 후에, 그 장르별로 많이 재생한 2개의 항목의 번호를 출력해야했다. 코드의 큰 구조는 1) genres, plays를 묶어서 dict로 만드는 과정과 2) 앞에서 생성한 dict을 알맞게 정렬하는 과정로 구성된다. dict를 정렬할 떄에는 sort를 사용하지 못하고 sorted()로 묶어서 사용해야한다. 비슷한 논리지만 다른 형태인 고수의 풀이도 참고하자!

백준 17219번 바로가기 나의 풀이 # 입력 import sys read = sys.stdin.readline n,m = map(int, read().split()) pro = dict() # 처리 for _ in range(n): ad, pw = read().split() pro[ad] = pw for _ in range(m): print(pro[read().strip()]) CODE REVIEW hash 형태로 정보를 저장하고, 다시 불러내는 문제. sys.stdin.readline 코드의 반복을 줄이기 위해 read = sys.stdin.readline으로 지정하고, read()로 부르면 편하게 사용 가능하다.

백준 9375번 바로가기 나의 풀이 import sys from collections import Counter read = sys.stdin.readline for _ in range(int(read().strip())): closet = [] for _ in range(int(read().strip())): temp = read().split() closet.append(temp[1]) closet = Counter(closet) ans = 1 for c in closet.values(): ans *= (c+1) print(ans-1) CODE REVIEW (종류별 갯수 + 1)을 모두 곱해준 뒤에 1을 빼주면 원하는 값이 나온다. collections 모듈의 Counter 클래스를 이용하여 편하게 해결했다.

백준 1620번 바로가기 나의 풀이 import sys n, m = map(int, sys.stdin.readline().split()) dogam = {} dogam2 = {} for i in range(n): temp = sys.stdin.readline().rstrip() dogam[i+1] = temp dogam2[temp] = i+1 for _ in range(m): cur = sys.stdin.readline().rstrip() try: cur = int(cur) print(dogam[cur]) except: name = str(cur) print(dogam2[name]) CODE REVIEW hash를 이용한 자료 구조 문제. (이름-숫자) (숫자-이름) 모두 구할 수 있어야하므로 dogam을 두 개 생성하는게 편리하다.