[Leetcode] Reorder Data in Log Files / Most Common Word / Group Anagrams / Longest Palindromic Substring / Array Partition I

Reorder Data in Log Files

오답 😔

def reorderLogFiles(self, logs: List[str]) -> List[str]:
    return sorted(logs, key=lambda x: (x.split()[1], x.split()[0]))

• [Wrong Answer]
  Input: ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
  Output: ["dig2 3 6","dig1 8 1 5 1","let1 art can","let3 art zero","let2 own kit dig"]
  Expected: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]

잘못된 점
1. 첫 번째 정렬 기준인 x.split()[1]로 인해 digit-log들이 앞에 나옴
2. digit-log들은 입력 순서를 유지해야 하는데 이것도 숫자 순서대로 정렬이 바뀜
👉 digit-logs와 letter-logs를 따로 정렬해야겠다

오답 2 😔

def reorderLogFiles(self, logs: List[str]) -> List[str]:
    letters = filter(lambda x: x.split()[1].isalpha(), logs)
    letters = sorted(letters, key=lambda x: (x.split()[1], x.split()[0]))
    digits = list(filter(lambda x: x.split()[1].isdigit(), logs))
    return letters + digits

• [Wrong Answer]
  Input: ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
  Output: ["a8 act zoo","g1 act car","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]
  Expected: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]

letter-log들은 로그명 문자열 끝까지 비교하고 같으면 identifier를 기준으로 정렬해야 하는데 x.split()[1] 때문에 첫 단어만 일치하면 그 다음에 바로identifier로 정렬함.

정답 🥳

def reorderLogFiles(self, logs: List[str]) -> List[str]:
    letters = filter(lambda x: x.split()[1].isalpha(), logs)
    letters = sorted(letters, key=lambda x: (" ".join(x.split()[1:]), x.split()[0]))
    digits = list(filter(lambda x: x.split()[1].isdigit(), logs))
    return letters + digits

👉 'python list to string'으로 구글링 결과... 잊고 있었던 join의 존재를 깨달음^^!

다른 solution 😮

def reorderLogFiles(self, logs: List[str]) -> List[str]:
    letters, digits = [], []
    for i in logs:
        if i.split()[1].isdigit():
            digits.append(i)
        else:
            letters.append(i)
    letters = sorted(letters, key=lambda x: (x.split()[1:], x.split()[0]))
    return letters + digits

👉 letter_log, digit_log 구분을 위해 filter 두 번 쓰는 것보다 그냥 for문 + if-else문으로 처리하는 게 더 빠름!
👉 x.split()[1:]을 string으로 만들 필요 없이.... 그냥 그대로 key로 써도 되는 거였다ㅎㅎ;;

배운 것 💪✨

• sorted(list, key=(1, 2, 3...): key(정렬기준) 여러 개 설정 가능! filter, map 함수와 달리 list()를 쓸 필요없이 바로 리스트를 반환해 줌

• list = sorted(list, key=...)는 list.sort(key=...)와 같음

• " ".join(list): 리스트를 문자열로 바꿀 때 사용
  
  

Most Common Word

오답 😔

def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
    paragraph = list(filter(lambda x: x not in banned, paragraph.lower().split()))
    return max(paragraph, key=lambda x: paragraph.count(x))

• [Wrong Answer]
  Input: "Bob hit a ball, the hit BALL flew far after it was hit."
  ["hit"]
  Output: "bob"
  Expected: "ball"

터미널에서 필터함수를 적용한 paragraph를 확인해 본 결과 "ball," 과 "ball"이 따로 카운트되어서 모든 단어의 카운트수가 1이 되었다. 그래서 맨 앞에 위치한 bob이 리턴된 것...
👉 맨 첫줄에 re.sub("[^a-z ]", " ", paragraph.lower())을 추가했는데 아무 변화도 일어나지 않음
why? 이 코드는 치환된 값을 반환할 뿐 원래 문자열을 바꿔주진 않기 때문에 앞에 paragraph = 을 붙여 줘야 함!

정답 🥳

1. count 이용
def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
    paragraph = re.sub("[^a-z ]", " ", paragraph.lower())
    paragraph = list(filter(lambda x: x not in banned, paragraph.split()))
    return max(paragraph, key=lambda x: paragraph.count(x))

2. collections 모듈의 Counter 이용 (더 빠름!)
def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
    paragraph = re.sub("[^a-z ]", " ", paragraph.lower())
    paragraph = list(filter(lambda x: x not in banned, paragraph.split()))
    dic = collections.Counter(paragraph)
    return max(dic.keys(), key=lambda x:dic[x])

다른 solution 😮

def mostCommonWord(self, paragraph, banned):
    words = [word for word in re.sub(r'[^\w]', ' ', paragraph).lower().split() if word not in banned]
    counts = collections.Counter(words)
    return counts.most_common(1)[0][0]

👉 Counter 객체에는 most_common()이라는 메서드가 있었다~~!

배운 것 💪✨

• 정규표현식의 sub 메서드는 새 문자열을 반환할 뿐, 기존 문자열을 변하지는 않음 👉 str = re.sub('', '', str)의 형태로 작성해야 함

• collection.Counter(string/list)
  value: 개수 로 구성된 딕셔너리 반환

• Counter 객체의 most_common(n) 메서드
  (value, 개수)로 구성된 리스트 반환. 파라미터가 없으면 전체 튜플을, 있으면 개수가 큰 순서로 n개의 튜플로 구성된 리스트 반환.
  
  

Group Anagrams

정답 🥳

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
  #step1
    li = list(map(lambda x: sorted(list(x)), strs))
  #step2
    li = sorted(enumerate(li), key = lambda x: x[1])
    ans = []
    num = 0
    for i in range(len(li)):
  #step3
        if (i==0):
            ans.append([strs[li[i][0]]])
        elif li[i][1] == li[i-1][1]:
            ans[num].append(strs[li[i][0]])
        else:
            ans.append([strs[li[i][0]]])
            num += 1
    return ans

• step1
  각 단어를 리스트화하고, 알파벳을 재정렬한 리스트로 만들기
  e.g. ["tan", "pat", "nat"] -> [['a', 'n', 't'], ['a', 'p', 't'], ['a', 'n', 't']]

• step2
  해당 리스트들을 enumerate를 이용해 기존 인덱스와 리스트를 담은 튜플로 만들고, 리스트 컨텐츠대로 정렬하기
  e.g. [(0, ['a', 'n', 't']), (2, ['a', 'n', 't']), (1, ['a', 'p', 't'])]

• step3
  각 튜플(li[i])에 대해서
  • 맨 첫 튜플이면: 해당 인덱스(li[i][0])를 갖는 단어(strs[li[i][0])를 ans에 리스트로 추가
  • 이전 튜플과 value(li[i][1])가 같으면: 해당 인덱스를 갖는 단어를 ans의 가장 최근 리스트(ans[num]) 요소로 추가
  • 이전 튜플과 value가 다르면: 해당 인덱스를 갖는 단어를 ans에 새 리스트로 추가, 가장 최근 리스트의 인덱스(num)에 +1

수정에 수정을 거쳐 완성한 코드와... 글로 풀어써도 장황한 설명...^.ㅠ
👉 각 단어(스트링)를 단어내에서 알파벳순으로 재정렬하려고 리스트로 만든 후 sort를 썼는데... 그냥 스트링에 sort를 바로 써도 됨(but 리턴값은 리스트)

다른 solution 😮

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    anagrams = collections.defaultdict(list)
    for i in strs:
        anagrams["".join(sorted(i))].append(i)
    return list(anagrams.values())

👉 단어들을 재정렬한 후 defaultdict에 key(재정렬한 공통단어): value(기존 단어 리스트)로 추가하고 values만 출력하여 훨씬 간단하게 푼 방법!
👉 키값을 그냥 sorted(i)가 아닌 "".join(sorted(i))로 설정한 이유: 리스트는 가변객체이기 때문에 딕셔너리의 키로 설정할 수 없음! (TypeError 발생)

배운 것 💪✨

• sorted("apple") = ['a', 'e', 'l', 'p', 'p']
  "".join(sorted("apple")) = "aelpp"

• collections.defaultdict()

  특정 key의 value가 존재하지 않는 경우, 인자로 주어진 객체의 기본값(int: 0 / str: "" / list: [])을 초기값으로 지정하는 유사딕셔너리

dessert = collections.defaultdic(list)
dessert['bread']
dessert['icecream']
dessert['coffee']
print(dessert)	#{'bread':[], 'icecream':[], 'coffee':[]}

• 리스트는 딕셔너리의 키가 될 수 없음

Longest Palindromic Substring

오답 😔

def longestPalindrome(self, s: str) -> str:
    ans = ""
    for i in range(len(s)):
        for l in range(i+1, len(s)):
            if s[i] == s[l]:
                sub = s[i:l+1]
                if sub == sub[::-1] and len(sub) > len(ans):
                    ans = sub
    return ans

• [Wrong Answer] input="a"일 때 "a"가 아닌 ""가 출력
  👉 ans의 초기값을 빈 문자열이 아닌 s[0]으로 설정
  
  

정답 🥳

def longestPalindrome(self, s: str) -> str:
    ans = s[0]
    for i in range(len(s)):
        for l in range(i+1, len(s)):
            if s[i] == s[l]:
                sub = s[i:l+1]
                if sub == sub[::-1] and len(sub) > len(ans):
                    ans = sub
    return ans

다른 solution 😮

def longestPalindrome(self, s: str) -> str:
  #step1
    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right +=1
        return s[left+1:right]
  #step2
    if len(s)<2 or s==s[::-1]:
        return s
  #step3
    result = ''
    for i in range(len(s)):
        result = max(result, expand(i, i), expand(i, i+1), key=len)
    return result

• step1
  left, right 포인터를 인자로 받아 s[left]와 s[right]가 동일할 경우 포인터를 앞뒤로 확장하며 가장 긴 펠린드롬을 리턴하는 expand 함수를 작성한다.
• step2
  빠른 예외 처리를 위해 expand 판별이 필요없는 경우부터 리턴
• step3
  for문과 expand 함수를 이용해 홀수(expand(i, i)), 짝수(expand(i, i+1)) 두 가지 경우를 고려, 팰린드롬 여부를 판별하면서 우측으로 이동한다. 이렇게 판별한 최댓값이 최종 결과가 된다.
  
  

배운 것 💪✨

• 투포인터 방식
  • 리스트의 양쪽 끝에서부터 2개의 점 위치를 기록하며 순차적으로 자료를 처리하는 알고리즘
  • 주로 정렬된 리스트에서 유용
  • 특정 합을 가지는 부분 연속 수열 문제 등에 적용

• 예외 처리를 미리 하면 처리 속도가 훨씬 빨라짐!

Array Partition I

정답 🥳

def arrayPairSum(self, nums: List[int]) -> int:
    nums.sort()
    res = 0
    for i in range(0, len(nums), 2):
        res += nums[i]
    return res

👉 sort를 이용해 오름차순으로 정렬해준 뒤 짝수번째 값(두 개씩 묶었을 때 더 작은 값이므로)의 합을 출력의 합을 출력

다른 solution 😮

def arrayPairSum(self, nums: List[int]) -> int:
    return sum(sorted(nums)[::2])

배운 것 💪✨

• list[::n]
  처음부터 끝까지 n씩 인덱스가 증가하는 슬라이싱