1/16일 알고리즘 스터디 (2)

Leetcode 771. Jewels and Stones

문자열 jewels와 stones를 받아 jewels가 stones 내에 몇 개가 있는지 세는 문제이다.

jewels = "aA"이고 stones = "aAbabB"라면 정답은 3이다.

풀이 1

• 파이썬 내장함수 count()를 이용한다.

코드

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        result = 0
        for jewel in jewels:
            result += stones.count(jewel)
        return result

풀이 2

defaultdict을 이용한다 -> 비교를 생략할 수 있어 코드를 줄일 수 있음

코드

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        freqs = collections.defaultdict(int)
        count = 0

        for char in stones:
            freqs[char] += 1
        
        for char in jewels:
            count += freqs[char]

        return count

풀이 3

collections.Counter를 이용한다 -> 마찬가지로 코드를 줄일 수 있음

코드

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        freqs = collections.Counter(stones)
        count = 0

        for char in jewels:
            count += freqs[char]
        return count

풀이 4

sum() 내장함수를 이용한다 -> 매우 파이썬다운 방식

코드

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

시간, 코드 비교

	풀이 1	풀이 2	풀이 3	풀이 4
runtime	31 ms	28 ms	27 ms	29 ms
lines	4	7	5	1

---

Leetcode 3. Longest Substrings without Repeating Characters

string s가 주어졌을때, 반복되는 문자가 없는 가장 긴 substring을 찾아라.

Example 1

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

풀이 1

• 이중 for문을 통해 substring을 만들어간다
• set()을 통해 substring에 중복되는 문자가 있는지를 체크하고, 중복되는 문자이면 break로 안쪽 for문을 빠져나온다
• 이를 반복하면서 반복되는 문자가 없는 가장 긴 substring의 길이를 반환한다

코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0
        for i in range(len(s)):
            substring = set()
            for j in range(i, len(s)):
                if s[j] in substring:
                    break
                else:
                    substring.add(s[j])
            max_len = max(max_len, len(substring))
        return max_len

풀이 2

sliding window를 이용한다.

코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_len = start = 0
        for i, char in enumerate(s):
        	# 이미 등장했던 문자라면 start 위치 갱신
            if char in used and start <= used[char]:
                start = used[char] + 1
            else:    # 최대 부분 문자열 길이 갱신
                max_len = max(max_len, i - start + 1)
            
            used[char] = i
        
        return max_len

실행시간 비교

	풀이 1	풀이 2
runtime	481 ms	50 ms

---

Leetcode 347. Top K Frequent Elements

숫자로 구성된 리스트 nums를 입력받아 가장 빈도수가 높은 k개의 숫자를 반환한다.

nums = [1, 1, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5]이고 k = 2라면 [4, 5]를 반환하는 문제이다.

풀이 1

• nums를 정렬하여 같은 숫자는 같이 모이도록 한다
• 첫 번째 숫자부터 count()를 통해 해당 숫자와 수를 num_and_cnt에 tuple로 저장한다
• num_and_cnt를 수를 기준으로 내림차순 정렬한다
• k개만큼 result에 num를 저장한 후 return한다

코드

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        nums.sort()
        i = 0
        num_and_cnt = []
        while i < len(nums):
            cnt = nums.count(nums[i])
            num_and_cnt.append((nums[i], cnt))
            i = i + cnt
        num_and_cnt.sort(key=lambda x: x[1], reverse=True)
        result = []
        for i in range(k):
            result.append(num_and_cnt[i][0])
        return result

풀이 2

collections.Counter와 heapq 모듈을 이용한다.

코드

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freqs = collections.Counter(nums)
        count = 0
        f_heap = []
        for f in freqs:
            heapq.heappush(f_heap, (-freqs[f], f))

        topk = list()
        for _ in range(k):
            topk.append(heapq.heappop(f_heap)[1])

        return topk

풀이 3

• zip과 collection.Counter를 이용한다.

  collections.Counter(a).most_common(n) : a의 요소를 세어, 최빈값 n개를 반환한다. (리스트에 담긴 튜플형태로)
  * : tuple등과 같이 묶여져 있는 자료를 풀어준다.

코드

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

풀이 4

collections.Counter와 most_common()함수를 이용한다.

코드

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        num_and_cnt = collections.Counter(nums)
        sorted_nac = num_and_cnt.most_common()

        result = []
        for i in range(k):
            result.append(sorted_nac[i][0])
        return result

실행시간 비교

	풀이 1	풀이 2	풀이 3	풀이 4
runtime	1399 ms	92 ms	105 ms	97 ms