Skip to content

Commit

Permalink
#221 & #236 solution
Browse files Browse the repository at this point in the history
  • Loading branch information
jungsiroo committed Jan 5, 2025
1 parent 4c091c8 commit 6544db9
Show file tree
Hide file tree
Showing 2 changed files with 67 additions and 0 deletions.
23 changes: 23 additions & 0 deletions best-time-to-buy-and-sell-stock/jungsiroo.py
Original file line number Diff line number Diff line change
@@ -0,0 +1,23 @@
class Solution:
def maxProfit(self, prices: List[int]) -> int:
"""
๊ฐ€์žฅ ์ˆ˜์ต์„ ๋งŽ์ด ์–ป์„ ์ˆ˜ ์žˆ๋„๋ก ์ €์ ์— ๋งค์ˆ˜, ๊ณ ์ ์— ๋งค๋„
๋งค์ˆ˜์™€ ๋งค๋„๋Š” ์„œ๋กœ ๋‹ค๋ฅธ ๋‚ 
min_price๋ฅผ ๋นผ๊ฐ€๋ฉด์„œ price ์—…๋ฐ์ดํŠธ
Time Complexity : O(n)
Space Complexity : O(1)
"""

min_price = max(prices)
days = len(prices)

for day in range(days):
min_price = min(prices[day], min_price)
prices[day] -= min_price

return max(prices)



44 changes: 44 additions & 0 deletions group-anagrams/jungsiroo.py
Original file line number Diff line number Diff line change
@@ -0,0 +1,44 @@
from collections import defaultdict

class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
# Naive Solution : Sort string

# ๊ฐ ๋‹จ์–ด๋งˆ๋‹ค ๋ชจ๋‘ ์ •๋ ฌ์„ ํ•œ ๋’ค ํ•ด๋‹น ๊ฐ’์„ hash๋กœ ์‚ฌ์šฉํ•˜์—ฌ ๋”•์…”๋„ˆ๋ฆฌ์— ์ถ”๊ฐ€ํ•˜๋Š” ๋ฐฉ๋ฒ•
# strs[i].length = k
# Time Complexity : O(n*klog(k))
# Space Complexity : O(n*k)

"""
n = len(strs)
word_dict = defaultdict(list)
for word in strs:
key = hash(''.join(sorted(word)))
word_dict[key].append(word)
ret = []
for value in word_dict.values():
ret.append(value)
return ret
"""

# Better Solution : Counting

# anagram ์˜ ํŠน์„ฑ ์ค‘ ์•ŒํŒŒ๋ฒณ ์นด์šดํŠธ ๊ฐฏ์ˆ˜๊ฐ€ ๊ฐ™๋‹ค๋Š” ๊ฒƒ์„ ์ด์šฉ
# ์นด์šดํŠธ ๊ฐฏ์ˆ˜๋ฅผ ํ™œ์šฉํ•˜์—ฌ key ๊ฐ’์œผ๋กœ ์ฒ˜๋ฆฌ
# Time Complexity : O(n*k)
# Space Complexity : O(n*k)
word_dict = defaultdict(list)

for word in strs:
freq = [0]*26
for char in word:
freq[ord(char) - ord('a')] += 1
word_dict[tuple(freq)].append(word)

return list(word_dict.values())



0 comments on commit 6544db9

Please sign in to comment.