UNIST, CSE 3th

2 minute read

290. Word Pattern (easy)

‘abba’ == ‘cat dog dog cat’. 처음보는 단어가 왔지만 원래 있는 패턴인 경우. 원래 있는 단어가 왔을 떄, 다른 패턴이 오는 경우. 두가지 경우를 모두 체크하기 위해서 두개의 dict를 사용했다. 한개만 사용하고 구현이 가능하긴한데, 직관적이지 않아서 일단 나는 안했다.

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        pattern2word = {}
        word2pattern = {}
        temp = s.split(' ')
        if len(pattern) != len(temp):
            return False
        for index, word in enumerate(temp):
            p = pattern[index]
            if p in pattern2word and pattern2word[p] != word:
                return False
            if word in word2pattern and word2pattern[word] != p:
                return False
            pattern2word[p] = word
            word2pattern[word] = p
        return True

# 한개만 사용
class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        pair = {}
        s = s.split(' ')
        if len(pattern) != len(s):
            return False
        for i in range(len(pattern)):
            if pattern[i] not in pair and s[i] not in pair.values():
                pair[pattern[i]] = s[i]
            elif pattern[i] not in pair and s[i] in pair.values():
                return False
            elif pair[pattern[i]] != s[i]:
                return False
        return True

151. Reverse Words in a String (medium)

왜 medium인지 모르겠다.

class Solution:
    def reverseWords(self, s: str) -> str:
        temp = s.split(' ')
        temp.reverse()
        temp = [x for x in temp if x != '']
        return ' '.join(temp)

179. Largest Number (medium)

처음 생각한 방식은, 첫번째 digit 만 비교해서 정렬하고 그대로 문자열로 합치면 된다고 생각했으나, [3, 33, 34] 같은 녀석들을 어떻게 비교하느냐에 따라서 값이 달라져서 문제가 “어떻게 숫자를 lexicographical 하게 정렬하는지” 로 바꾸어서 생각했다. 그래서 생각해낸게 최대 자릿수를 계산해서 최대 자릿수보다 작은 숫자들을 변형해서 비교하는 방식을 고안했다. 예를 들어서 [3, 33, 34]에서 최대 자릿수가 2이므로 [30, 33, 34] 로 변환하여 생각하는 것이다. 하지만.. 3이 가장 앞에 오는경우, 앞자리의 영향을 받기 때문에 10의 배수를 곱하는 것 보다 마지막 자릿수를 연장하여 생각하는 방식으로 변경했다. 따라서 [3, 33, 34] 가 [33, 33, 34]로 변환되어 정렬했다. 그러나…. 문제는 안풀렸다.

counter example : [34323,3432]

class Solution:

    def get_adjust_digit(self, num, digit):
        current = math.floor(math.log10(num)) + 1
        res = num
        last_digit = num % 10
        for i in range(digit - current):
            res *= 10
            res += last_digit
        return res

    def largestNumber(self, nums: List[int]) -> str:
        max_digit = 0
        for num in nums:
            max_digit = max(max_digit, math.floor(math.log10(num)) + 1)
        # print(self.get_adjust_digit(3, 2)
        
        nums.sort(key=lambda x : self.get_adjust_digit(x, max_digit), reverse=True)
        # print(nums)
        
        res = ''
        for num in nums:
            res += str(num)
        return res

신기한 방식을 찾았다. 문자열을 뒤에 붙였을 때 숫자가 증가하는지 혹은 감소하는지를 기준으로 정렬한다. lstrip 함수를 이용하여 첫번째 digit이 0 이 되는 경우를 방지.

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums[:] = map(str, nums)
        nums.sort(key=NumCompare, reverse=True)
        return ''.join(nums).lstrip('0') or '0'

class NumCompare:
    def __init__(self, s: str):
        self.s = s
    def __lt__(self, other: str) -> bool:
        return self.s + other.s < other.s + self.s

You may also enjoy