릿코드 2. Add Two Numbers, 49. Group Anagrams

문제

2. https://leetcode.com/problems/add-two-numbers/description/?envType=study-plan-v2&envId=top-interview-150

LeetCode - The World's Leading Online Programming Learning Platform

접근

문제에서 제시한 singly-linked list 구조에 맞춰 알고리즘을 풀어나가는 문제였다.

 

처음에 순서를 뒤집기 위해 string으로 변환하며 뒤집었는데

val*1 + val*10 + val*100 과 같이 덧셈으로 뒤집을 수 있다. (C 수업들을 때, 이런 식으로 많이 했었는데)

 

return 할 linked list를 만드는 방법에 2가지가 있다.

2 -> 3 -> 1 -> 4 이런 linked list가 필요할 때

1. 앞에서부터(2부터) 만드는 방법 = 재귀

2. 뒤에서부터(4부터) 만드는 방법

나는 재귀가 떠올랐다.

다만 문제 흐름상 마지막 결과가 뒤집혀있기 때문에 앞에서부터 만들려면 reverse가 한번 필요하다.

 

# 재귀방법
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        a1_val, a2_val = 0, 0 
        num = 1
        while 1:
            a1_val += l1.val * num
            num *= 10
            if not l1.next:
                break
            l1 = l1.next
        num = 1
        while 1:
            a2_val += l2.val * num
            num *= 10
            if not l2.next:
                break
            l2 = l2.next
        a3 = list(str(a1_val + a2_val))
        a3.reverse()
        return self.linked(a3, 0)
    
    def linked(self, arr, idx):
        if idx == len(arr):
            return None
        else:
            return ListNode(arr[idx], self.linked(arr, idx+1))

# 뒤에서부터 방법
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        a1_val, a2_val = 0, 0 
        num = 1
        while 1:
            a1_val += l1.val * num
            num *= 10
            if not l1.next:
                break
            l1 = l1.next
        num = 1
        while 1:
            a2_val += l2.val * num
            num *= 10
            if not l2.next:
                break
            l2 = l2.next
        a3 = list(str(a1_val + a2_val))

        result = None
        for i in range(len(a3)):
            if i==0:
                result = ListNode(a3[i])
                prev = result
            else:
                result = ListNode(a3[i], prev)
                prev = result

        return result

문제

49. https://leetcode.com/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-interview-150

LeetCode - The World's Leading Online Programming Learning Platform

접근

처음에 매 반복마다 sort하는 건 재미없을 것 같아서, 다른 방법으로 접근했다. 결과적으론 sort가 빠르긴하다.

 

문자 아스키코드 제곱의 합으로 string마다 hash값을 만들려고 했다.

그냥 아스키코드 합은 같은 경우 나올 듯해서 제곱도 섞어 뒀는데도 같은 경우 나오더라.

 

그래서 한 번 나온 해쉬값이면서 set(string)이 다르다면 조건을 거쳐서 값을 바꾼다.

때문에 dictionary에 나왔던 해쉬값과 set(string)을 기억해야 하고 경우에 따라 비효율적인 횟수가 있을 수 있다.

 

# string마다 hash값 방법
# ex) gethash(abc)=32123, gethash(bac)=32123
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hashmap = {}
        history = {}
        for i in strs:
            locate = self.gethash(i, history)
            if hashmap.get(locate):
                hashmap[locate].append(i)
            else:
                hashmap[locate] = [i]
        return list(hashmap.values())
    
    def gethash(self, s, history):
        result = 0
        for i in s:
            result += ord(i)**2 + ord(i)

        prevent = history.get(result)
        if prevent and set(prevent) != set(s):
            result += 1
            while True:
                result += 1
                h = history.get(result)
                if not h or set(h) == set(s):
                    break
        history[result] = set(s)
        return result

# sort 방법
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hashmap = {}
        for i in strs:
            k = list(i)
            k.sort()
            k = "".join(k)
            if hashmap.get(k):
                hashmap[k].append(i)
            else:
                hashmap[k] = [i]
        return list(hashmap.values())