[TIL_Carrotww] 91 - 23/01/25

📝Carrotww의 코딩 기록장

🧲 python algorithm interview

🔍 Leetcode 771 Jewels and Stones - Easy

쉬운 문제다 hash 파트에 나오는 문제이고 응용 없이 dictionary만 알면 풀 수 있다.

• 내 풀이

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        from collections import defaultdict
        jewels_dict = defaultdict(int)
        result = 0

        for jewels in jewels:
            jewels_dict[jewels] += 1

        for stone in stones:
            if stone in jewels_dict:
                result += 1

        return result

• counter를 이용한 풀이

# counter 사용
class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        result = 0
        from collections import Counter
        counter = Counter(stones)
        for jewel in jewels:
            result += counter[jewel]

        return result

• python 다운 한 줄 풀이

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        return sum(s in jewels for s in stones)

위와 같은 방식으로 풀면 list comprehesion 부분에서 [True, False, False] 와 같은 식으로 bool 값이 담긴 후 sum을 하며 True를 계산한다.

🔍Leetcode3 Longest Substring Without Repeating Characters - Medium

투 포인터로 풀면 쉽게 풀 수 있다.
투 포인터 방식에 많이 익숙해졌다고 생각했지만 아직 문제를 보고 바로바로 코드가 나오는 수준은 아니라 아쉽다.

• 처음 풀이
  처음에 투포인터로 풀면 쉽겠다라고는 생각했지만 감이 안잡혀 일단 bruteforce로 풀어보았다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = 0
        for i in range(len(s)):
            if result >= len(s[i:]):
                break
            index = i
            check_str = set()
            while index < len(s):
                if s[index] in check_str:
                    break
                check_str.add(s[index])
                index += 1
                result = max(result, len(check_str))
        return result

위와 같은 방법으로 풀면... 겁나 느리다... ㅠㅠ
하위 7%

• 투 포인터 풀이 O(n)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_length = start = 0
        for i, char in enumerate(s):
            if char in used and start <= used[char]:
                start = used[char] + 1
            else:
                max_length = max(max_length, i - start + 1)
            used[char] = i

        return max_length

20배는 빨라졌다.

🔍 Leetcode347 Top K Frequent Elements Medium

• 내 풀이

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        from collections import Counter
        counter = Counter(nums)
        result = []
        counter_list = [(key, val) for key, val in counter.items()]
        counter_list.sort(key=lambda x:x[1])

        for i in range(k):
            key, val = counter_list.pop()
            result.append(key)
        return result

카운터를 이용해서 리스트로 정렬한 후 k 번 만큼 반복하여 풀었다.

빠르다!

• 책의 Heap 풀이

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        from collections import Counter
        import heapq
        counter = Counter(nums)
        heap = result = []
        for c in counter:
            heapq.heappush(heap, (-counter[c], c))
        for i in range(k):
            result.append(heapq.heappop(heap)[1])

        return result

heap을 사용했다는 점만 다르다

• 한 줄 풀이

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        from collections import Counter
        return list(zip(*Counter(nums).most_common(k)))[0]

zip과 Counter() 의 most_common() 기능을 알고있으면 이렇게도 가능하다.