해시 테이블 추가문제

Question 1: Integer to Roman

숫자를 로마 문자로 변환하라

입력: num = 58

출력: ‘LVIII’

내 풀이

class Solution:
    def intToRoman(self, num: int) -> str:
        table = {1000:'M', 900:'CM', 
                 500:'D', 400:'CD',
                 100:'C', 90:'XC',
                 50:'L', 40:'XL',                
                 10:'X', 9:'IX',                
                 5:'V', 4:'IV',
                 1:'I'}
        
        result = ''
        for key, value in table.items():
            result += value * int(num/key)
            num = num % key
        
        return result

• 1000의 값부터 차례로 입력값에 나눈다음 몫을 빈 문자열인 result에 더한다.
• 입력값을 딕셔너리의 키로 나눈 값이 다음 입력값이 된다.

결과

Runtime: 61 ms, faster than 61.10% of Python3 online submissions for Integer to Roman. Memory Usage: 13.9 MB, less than 77.45% of Python3 online submissions for Integer to Roman.

---

Question 2: K Closest Points to Origin

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

입력: points = [[1,3],[-2,2]], k = 1

출력: [[-2,2]]

내 풀이

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        return sorted(points, key = lambda x: sqrt(x[0]**2 + x[1]**2))[:k]

• sorted() 함수의 key 값을 euclidean distance를 구하는 공식을 넣었다.

결과

Runtime: 1363 ms, faster than 19.49% of Python3 online submissions for K Closest Points to Origin. Memory Usage: 20.1 MB, less than 96.11% of Python3 online submissions for K Closest Points to Origin.

---

Question 3: Sender With Largest Word Count

You have a chat log of n messages. You are given two string arrays messages and senders where messages[i] is a message sent by senders[i].

A message is list of words that are separated by a single space with no leading or trailing spaces. The word count of a sender is the total number of words sent by the sender. Note that a sender may send more than one message.

Return the sender with the largest word count. If there is more than one sender with the largest word count, return the one with the lexicographically largest name.

입력: messages = [“Hello userTwooo”,”Hi userThree”,”Wonderful day Alice”,”Nice day userThree”], senders = [“Alice”,”userTwo”,”userThree”,”Alice”]

출력: “Alice”

내 풀이

class Solution:
    def largestWordCount(self, messages: List[str], senders: List[str]) -> str:
        senders_dict = collections.defaultdict(int)
        
        for i in range(len(senders)):
            senders_dict[senders[i]] = senders_dict[senders[i]] + len(messages[i].split())
     
        senders_sorted = sorted(senders_dict.items(), key = lambda x: x[1], reverse=True)
        
        # 문자의 개수가 같을 때 사전적으로 큰 이름을 리턴할 수 있도록 함
        max_word_cnt = senders_sorted[0][1]
        max_sender = senders_sorted[0][0]
        
        print(max_sender)
        for sender, word_cnt in senders_sorted:
            if word_cnt == max_word_cnt:
                max_sender = max(max_sender, sender)
            else:
                break
        
        return max_sender

결과

Runtime: 609 ms, faster than 55.17% of Python3 online submissions for Sender With Largest Word Count. Memory Usage: 21.9 MB, less than 9.46% of Python3 online submissions for Sender With Largest Word Count.