항해99 알고리즘 5회차

해시맵 디자인 https://leetcode.com/problems/design-hashmap

Design HashMap - LeetCode

 

접근 방식

 

파이썬 알고리즘 인터뷰의 해시맵 디자인 개별 체이닝을 한번 구현 후 문제를 풀었다.

Node 클래스를 이용해서 바로 값을 입력, 수정해주는 방식으로 진행하였다.

 

class Node:
    def __init__(self, key=None, val=None):
        self.key = key
        self.val = val

class MyHashMap:

    def __init__(self):
        self.table = collections.defaultdict(Node)

    def put(self, key: int, value: int) -> None:
        if self.table[key].val is None:
            self.table[key] = Node(key, value)
            return
        self.table[key].val = value

    def get(self, key: int) -> int:
        if self.table[key].val is None:
            return -1
        return self.table[key].val

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

---

보석과 돌 https://leetcode.com/problems/jewels-and-stones

 

Jewels and Stones - LeetCode

 

접근 방식

• 파이썬의 collections.counter를 사용하면 간편하게 풀 수 있다고 생각했다.

 

def numJewelsInStones(self, jewels: str, stones: str) -> int:
        stones = collections.Counter(stones)
        count = 0
        for i in jewels:
            count += stones[i]

        return count

 

---

중복 문자가 없는 가장 긴 부분 문자열 https://leetcode.com/problems/longest-substring-without-repeating-characters

Longest Substring Without Repeating Characters - LeetCode

 

접근 방식

• 다음 문자열의 위치를 끝까지 확인하면 되지 않을까 ? 해시맵으로는 생각이 안나서 스택으로 구현을 했다. 반쪽자리 작동이 되어버렸다. "pwwkew” 테스트케이스는 중첩된 문자가 옆에 있기에 카운트에 체크가 안됐다.

 

틀린 결과

def lengthOfLongestSubstring(self, s: str) -> int:
        stack = []
        count = 0
        rank = 0
        for char in range(len(s)-1):
            stack.append(s[char])
            count += 1
            if len(stack) > 1 and s[char+1] == stack[+1]:
                if rank < count:
                    rank = count - 1
                    count = 0
        
        return rank

 

 

파이썬 알고리즘 인터뷰

• 이번에 알게 된 함수
  • max는 인자 2개를 받으면, 비교하고 큰 값을 가져옴
• 슬라이딩 윈도우 기법 사용
  • 투 포인터 사용
• start가 오른쪽으로 계속 나아감.
  • 존재하거나, start보다 used[char]가 클 경우
  • start 값을 갱신한다.

맞은 결과 - 파이썬 알고리즘 인터뷰

def lengthOfLongestSubstring(self, s: str) -> int:
	used = {}
	max_length = start = 0
	
	for i, char in enumerate(s):
	    # 존재 할 경우, start가 갱신한 인덱스 보다 낮을경우
	    if char in used and start <= used[char]:
	        start = used[char] + 1  # start를 갱신

	    # 존재 하지 않을 경우
	    else:
					# 현재위치 - 갱신한 인덱스 + 1
					# + 1은 문자열 위치

					# max에 인자가 2개면 비교 후 높은값 반환
	        max_length = max(max_length, i - start + 1)
	
	    used[char] = i  # 현재 문자열의 위치 저장
	
	return max_length

---

상위 K 빈도 요소 https://leetcode.com/problems/top-k-frequent-elements

Top K Frequent Elements - LeetCode

 

접근 방식

• 단순하게 개수를 세고 k 개수가 넘는걸 저장하면 되지 않을까 ?
• k가 2여도 nums[1,2]면 2개 다 결과에 나와야한다.

 

놓쳤던 부분

• k가 몇개 이상 일시에만 뜨게 하는 줄 알고 착각 했다.
• 그냥 제일 번번하게 나온 개수를 순서대로 k만큼 나오게 하면 됐었다.

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        stack = []
        for a, b in collections.Counter(nums).most_common():
            if k == 0:
                break
            stack.append(a)
            k -= 1
        return stack

---

수 찾기 https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

문제 접근

• 처음에 입력이 왜 저렇게 출력되는지 헷갈렸는데
• 프린터 큐 문제를 읽은 덕분인지 이해는 빨리 갔다.

import collections

# 여기서 4번째 줄이 2번째 줄에 포함되는지를 찾는 문제.

N = int(input())
first = list(map(int, input().split()))

M = int(input())
second = list(map(int, input().split()))


a = collections.Counter(first)

for i in second:
    if a[i] > 0:
        print(1)
    else:
        print(0)

---

비밀번호 찾기 https://www.acmicpc.net/problem/17219

17219번: 비밀번호 찾기

 

문제 접근

• 간단하게 딕셔너리(해시맵)에 추가하고 빼주면 됐었다.

import collections

N, M = list(map(int, input().split()))
table = collections.defaultdict()

for i in range(N):
    addr, pw = list(map(str, input().split()))
    table[addr] = pw

for i in range(M):
    print(table[input()])