본문 바로가기

Algorithm

 (51)
[Top Interview 150 - Math] 50. $Pow(x, n)$ [Q] [Medium]Implement pow(x, n), which calculates x raised to the power n (i.e., xn). pow(x, n) 을 구현하라고 해서 ** 로 return 했는데 통과뭔가 Medium 문제 인데 이렇게 풀어도 되나 다른 사람들 답도 찾아봤다.# Answerclass Solution: def myPow(self, x: float, n: int) -> float: return x ** n # 다른 사람 답class Solution: def myPow(self, x: float, n: int) -> float: my_pow_num = pow(x, n) if my_pow_num > (pow(2, 31) - 1)..
[Top Interview 150 - Math] 69. Sqrt(x) [Q] [Easy]Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.You must not use any built-in exponent function or operator.For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python. do not use x ** 0.5 못 보고 아래와 같이 풀었는데 정답처리 됐다.근데 안된다니까 일단 빼고다른 답들을 찾아보니 이진탐색도 있고, 아래 import math 한 것도 있는데 일단 impor..
[Top Interview 150 - Math] 172. Factorial Trailing Zeroes [Q] [Medium]Given an integer n, return the number of trailing zeroes in n!.Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1. int -> list 바꾸는 과정이 필요했다.0 만 따로 처리해주고, math.factorial 이용하면 쉬운 문제였다.다만 n = 1574 였을 때 오류가 났는데 애초에 math.factorial 이 적용되지 않았다.큰 수의 경우 이런식으로 구할 수 없음을 깨닫고 찾아보니 5의 배수가 뒷 자리 0을 가져온다는 것을 이용해야 했다. -> 5로 나눠서 몫을 계산하여 가져오면 뒷자리 0의 개수를 알 수 있다.아직도 수학도 갈 길이 멀다.# Wrong Answerimport ma..
[Top Interview 150 - Math] 9. Palindrome Number [Q] [Easy]Given an integer x, return true if x is a palindrome, and false otherwise. int -> list 바꾸는 과정이 필요했다.음수인 경우와 0보다 크고 10보다 작은 일의 자리 숫자인 경우도 따로 처리해줬다.제출하다보니 예외가 계속해서 나와서 그걸 처리하다 보니 코드가 좀 지저분해졌다.# Answerimport mathclass Solution: def isPalindrome(self, x: int) -> bool: # 음수 따로 처리 if x = 0) & (x 1) & (x_list[:middle-1] == list(reversed(x_list[middle:]))): ..
[Top Interview 150 - Hashmap] 128. Longest Consecutive Sequence [Q] [Medium]Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.You must write an algorithm that runs in O(n) time. 이 문제는 오름차순으로 하면 바로 풀릴 문제였지만, time complexity 로 인해 사용하기 어렵다.hash set 을 사용해야 한다.# Answerclass Solution: def longestConsecutive(self, nums: List[int]) -> int: if not nums: return 0 num_set = set(nums) ..
[Top Interview 150 - Hashmap] 219. Contains Duplicate II [Q] [Easy]Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j)  문제가 참 이해가 안갔던 문제..# Answerclass Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: num_dict = {} for i, num in enumerate(nums): if num in num_dict and i - num_dict[num]
[Top Interview 150 - Hashmap] 49. Group Anagrams [Q] [Medium]Given an array of strings strs, group the anagrams together. You can return the answer in any order. 일단 문제가 짧아서 좋았다 22..collections.defaultdict 함수 쓰면 아주 간단하게 해결되는데 참고한 문제 해결 방법이 독특해서 재밌었다.# Answerimport collectionsclass Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: anagrams = collections.defaultdict(list) for word in strs: anagrams..
[Top Interview 150 - Hashmap] 242. Valid Anagram [Q] [Medium]Given two strings s and t, return true if t is an anagram of s, and false otherwise. 일단 문제가 짧아서 좋았다.문제가 짧으니까 잘 풀리는 것 같기도..?count(i) 함수 써서 해당 '문자열' 의 개수를 value 로 넣어주니 쉽게 풀렸다.# Answerclass Solution: def isAnagram(self, s: str, t: str) -> bool: # 길이 안 맞으면 False if len(s) != len(t): return False s_dict = dict() t_dict = dict() for i in s: ..

티스토리툴바