Problem Solving/LeetCode
-
[리트코드] (LeetCode) 49번 Group Anagrams 문제Problem Solving/LeetCode 2021. 7. 5. 17:56
한 문자열의 요소가 같은 것끼리 이루어져있는 것들을 리스트로 묶어서 반환하면 되는 문제다. 한 문자열을 정렬해서 비교하면 같은 요소로 이루어져있는지 아닌지 알 수 있다. 이것을 아이디어로 문자열을 정렬한 값을 딕셔너리에 key 값으로 하여 value로 받으면 쉽게 풀 수 있다. class Solution(object): def groupAnagrams(self, strs): # value가 list인 형태의 dict를 반환 group = defaultdict(list) for word in strs: group[''.join(sorted(word))].append(word) return list(group.values())
-
[리트코드] (LeetCode) 24번 Swap Nodes in Pairs 문제Problem Solving/LeetCode 2021. 7. 5. 17:49
예제 그림과 같이 pairs끼리의 노드를 스왑해서 그 연결 리스트를 리턴하면 되는 문제다. 파이썬이라 가능한 풀이 법인데, 다중 할당을 통해 while 루프를 돌면서 한 번에 node.val과 node.next.val을 서로 스왑해주며 풀었다. class Solution: def swapPairs(self, head: ListNode) -> ListNode: node = head while node and node.next: node.val, node.next.val = node.next.val, node.val node = node.next.next return head
-
[리트코드] (LeetCode) 21번 Merge Two Sorted Lists 문제Problem Solving/LeetCode 2021. 7. 5. 17:43
두 개의 연결 리스트를 받아 정렬된 하나의 연결 리스트를 리턴하면 되는 문제다. 다양한 풀이 방법이 존재하는 것 같았으나, 필자는 제일 쉬운 방법으로 접근해서 풀었다. 각 연결 리스트의 데이터를 하나의 리스트에 담아주고, 정렬한 후, 새로운 ListNode를 만들어서 리턴해줬다. 사실 이러면 쓸데없는 메모리를 많이 잡아먹는다. 따라서 훌륭한 두뇌를 갖고 있다면.. 새로운 리스트를 만드는 게 아닌 파라미터로 받은 리스트를 바로 정렬하는 방법으로 문제를 해결할 수 있을 것이다. class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: l = [] while l1: l.append(l1.val) l1 = l1.next wh..
-
[리트코드] (LeetCode) 20번 Valid Parentheses 문제Problem Solving/LeetCode 2021. 7. 5. 17:37
스택 자료구조를 활용한 대표적인 알고리즘 문제다. 괄호를 딕셔너리 형태로 짝을 지어주고, for문에서 문자열에 닫는 괄호를 접근할때마다 pop을 해서 stack에 여는 괄호랑 비교하면서 풀었다 크게 어려울 것은 없었지만 예외처리에 신경써야 했다. class Solution: def isValid(self, s: str) -> bool: stack = [] t = { ')': '(', '}': '{', ']': '[' } for c in s: if c not in t.values(): if len(stack) == 0: return False if stack.pop() != t[c]: return False else: stack.append(c) return False if len(stack) != 0 e..
-
[리트코드] (LeetCode) 15번 3Sum 문제Problem Solving/LeetCode 2021. 7. 5. 17:30
파라미터로 주어지는 리스트 nums에서 3개의 요소로 0이 되는 값을 새로운 리스트로 만들어서 리스트 in 리스트 형태로 리턴하면 되는 문제다. 처음에는 브루트 포스로 시도 했으나 시간 초과로 틀렸고, 그 이후에는 투 포인터를 활용해서 문제를 풀렸고 시도 했으나.. 뭔가 한 끝이 맞지 않아 계속 틀렸고, 책을 참고하여 코드를 작성하였다. 여기서 중요한 포인트는 마지막 else 문에서 while문을 통해 같은 값은 계속해서 스킵해주는 것이다. class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: result = [] nums.sort() for i in range(len(nums)-1): if i > 0 and nums[i] == ..
-
[리트코드] (LeetCode) 2번 Add Two Numbers 문제Problem Solving/LeetCode 2021. 7. 5. 17:18
파라미터로 두 연결 리스트의 head를 받고, 두 연결 리스트의 데이터를 더한 하나의 연결 리스트의 head를 반환하면 되는 문제다. class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: nums1 = [] nums2 = [] while l1: nums1.append(l1.val) l1 = l1.next while l2: nums2.append(l2.val) l2 = l2.next nums1.reverse() nums2.reverse() n1 = ''.join(map(str, nums1)) n2 = ''.join(map(str, nums2)) n = int(n1) + int(n2) n = list(str(n)) n..
-
[리트코드] (LeetCode) 1번 Two Sum 문제Problem Solving/LeetCode 2021. 6. 15. 13:53
일단 문제 내용은 간단하다. 정수로 이루어진 리스트와, 타겟 정수 하나를 함수 파라미터로 받고 리스트의 요소의 합으로 타겟이 되는 리스트의 인덱스 두개를 리스트로 리턴하면 된다. ex) 파라미터 : list = [2,7,11,15] , target = 9 리스트의 0 => 2 리스트의 1 => 7 2 + 7 = 9 리턴 => [0,1] 방법은 다양하게 있을 것 같다. 브루트 포스 (Brute force) 형식으로 for 문을 두번 반복해서 모든 경우의 수를 더해보며 구할 수 있고.. 아니면, 인덱스 번호를 하나씩 더하거나 하나씩 빼가며 인덱스를 추적하는 포인터 변수를 하나 만들어서 구할 수도 있을 것 같고.. 근데 나는 브루트 포스 식으로 풀고 싶지 않았고, 좀 깔끔한 코드로 할 수 있지 않을까 고민하면..
-
[리트코드] (LeetCode) 49번 Group Anagrams 문제Problem Solving/LeetCode 2021. 6. 14. 22:53
class Solution(object): def groupAnagrams(self, strs): # value가 list인 형태의 dict를 반환 a = defaultdict(list) for word in strs: a[''.join(sorted(word))].append(word) return list(a.values()) 리스트의 각 요소가 같은 글자로 이루어진 것들끼리 합쳐 리턴 해주면 된다. 따라서 딕셔너리를 하나 만들어 주고 key로 리스트의 요소를 정렬한 값을 받고 각 리스트의 요소를 append 해주면 자연스럽게 같은 글자끼리 합쳐진 딕셔너리가 되고 그 딕셔너리에 values만 반환해주면 된다.