[Leetcode] Two Sum / Reverse Integer / Roman to Integer / Longest Common Prefix / Valid Parentheses

Two Sum

오답 😔

def twoSum(self, nums: List[int], target: int) -> List[int]:
    re = []
    for i in range(len(nums)):
        others = nums[i+1:]
        for j in others:
            if nums[i]+j==target:
                re += i
                re += nums.index(j)
                return re

• [TypeError] line8, 9 : list + int이기 때문
  👉 list + [int] 형태가 되어야 함
  👉 근데 애초에 굳이 빈 리스트를 만들고 추가할 필요도 없는 것 같음! 답 도출되면 바로 리스트 만들도록 수정

• 수정 후 ▶ [Wrong Answer] input=([3,3], 6)일 때 [0, 1]이 아닌 [0, 0]이 리턴됨
  why? list에 중복된 값이 있으면 list.index(n)는 가장 먼저 등장하는 n의 인덱스를 반환하기 때문!
  👉 두 번째 for문도 리스트가 아닌 range(len(list))를 이용하는 형태로 수정
  
  

정답 🥳

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

이게 무차별 대입방식인 브루트 포스로 푼... 가장 비효율적(ㅎㅎ) 풀이라고 한다~~~!😵

다른 solution 😮

def twoSum(self, nums, target):
    for i, n in enumerate(nums):
        m = target - n
        if (m in nums) and (nums.index(m) != i):
            return [nums.index(m), i]

배운 것 💪✨

• enumerate()

  • 리스트, 튜플, 문자열 등 시퀀스 자료형을 입력받아 (인덱스, 원소)형태의 튜플로 반환
  • 보통 for문과 함께 다음처럼 사용됨

>> for i, name in enumerate(['I', 'love', 'cookie']):
...     print(i, name)
...
0 I
1 love
2 cookie

Reverse Integer

오답 😔

def reverse(self, x: int) -> int:
    y = str(x) if x>=0 else str(abs(x))
    return y[::-1] if x>=0 else "-"+y[::-1]

• [Wrong Answer] input=120일 때 '21'이 아닌 '021' 출력
  👉 str 형태로 답을 구해서 발생하는 문제. int()를 이용해 0 없애기.
• 수정 후 ▶ [Wrong Answer] input=1534236469일 때 2**31범위를 초과하므로 0이 리턴되어야 하는데 초과값 그대로 리턴됨
  👉 범위 지정해서 if문 삽입
  
  

정답 🥳

def reverse(self, x: int) -> int:
    y = str(abs(x))
    re = y[::-1] if x>=0 else "-"+y[::-1]
    if (-2**31 <= int(re) <= 2**31 - 1):
        return int(re)
    else: return 0

Roman to Integer

정답 🥳

def romanToInt(self, s: str) -> int:
    li = (('IV', 4), ('IX', 9), ('XL', 40), ('XC', 90), ('CD', 400), ('CM', 900))
    n = 0
    for a, b in li:
        if a in s:
            n += b
            s = s.replace(a, '')
    dic = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
    for i in s:
        if i in dic.keys():	#없어도 되는 부분 (i는 당연히 dic.keys() 안에 있을 것)
            n += dic[i]
    return n

• 4, 9처럼 두 글자로 이루어진 문자는 바로 for문을 사용할 경우 한 글자씩 끊김
  👉 ('문자', 숫자)로 이루어진 튜플을 만들어 전체 문자열 내에서 찾은 뒤 제거
• 나머지 문자는 for문을 통해 하나씩 딕셔너리에 대응시켜서 값을 더함
  
  

다른 solution 😮

def romanToInt(self, s: str) -> int:
    data = {
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000
    }
    s = s.replace("IV", "IIII").replace("IX", "VIIII").replace("XL", "XXXX").replace("XC", "LXXXX").replace("CD", "CCCC").replace("CM", "DCCCC")
    return sum(map(data.get, s))

배운 것 💪✨

• 시퀀스 자료의 내부 원소로 시퀀스 자료를 넣어서 for a, b in list:의 형태로 for문을 작성하면 쉽게 짝을 맞춰 언패킹할 수 있음
• string.replace(x, y)
  • x를 y로 문자열 치환
  • 치환할 문자쌍이 여러 개인 경우 s.replace().replace().replace()... 형태로 이어 쓸 수 있음
  • string에 x가 없어도 에러가 뜨지 않음!
• dic[key] 대신 dic.get(key)를 사용하면 딕셔너리 내에 해당 key가 없는 경우에도 KeyError 대신 아무 값도 리턴하지 않음

Longest Common Prefix

오답 😔

def longestCommonPrefix(self, strs: List[str]) -> str:
    ans = ""
    for i in range(len(strs[0])):
        if list(filter(lambda x:x[i]==strs[0][i], strs))==strs:
            ans += strs[0][i]
    return ans

• [IndexError] line4: 첫 번째 문자열(strs[0])보다 짧은 문자열이 있는 경우 string index out of range 발생
  👉 try-except 구문으로 수정

• 수정 후 ▶ [IndexError] line3: 조건에서 0<=len(strs)<=200 이었으므로 strs가 빈 리스트일 수도 있음! len(strs)>0인 조건 추가

• 수정 후 ▶ [Wrong Answer] input=["cir", "car"]일 때 "c"가 아닌 "cr"이 리턴됨
  why? cir[1]!=car[1]일 때 for문을 빠져나가야 하는데 cir[2]==car[2]까지 확인 후 "r"을 ans에 추가해버림
  👉 else: break 구문을 삽입
  
  

정답 🥳

def longestCommonPrefix(self, strs: List[str]) -> str:
    ans = ""
    if len(strs) > 0:
        for i in range(len(strs[0])):
            try:
                if (list(filter(lambda x:x[i]==strs[0][i], strs)) == strs):
                    ans += strs[0][i]
                else: break
            except:
                pass
    return ans

다른 solution 😮

def longestCommonPrefix(self, strs):
    if not strs:
        return ""
    shortest = min(strs, key=len)
    for i, ch in enumerate(shortest):
        for other in strs:
            if other[i] != ch:
                return shortest[:i]
    return shortest 

👉 if문으로 i번째 문자가 일치하는지를 비교하는 것이 아니라, 불일치하는지를 비교해서 불일치하는 지점에서 바로 그전 문자열까지 리턴

배운 것 💪✨

• min(itreable, key=func)
  key 함수의 결과값이 최소인 자료를 반환함

Valid Parentheses

오답 😔

1.
def isValid(self, s: str) -> bool:
    li = ["()", "[]", "{}"]
    while True:
        try:
            for a in li:
                if a in s: s.replace(a, "")
        except:
            if len(s) == 0:
                return True
            else:
                return False

2.
def isValid(self, s: str) -> bool:
    while (("()" in s) or ("[]" in s) or ("{}" in s)):
        s.replace("()", "").replace("[]", "").replace("{}", "")
    if len(s) == 0:
        return True
    else:
        return False

• [Time Limit Exceeded]: s에 "()", "[]", "{}"가 안 남을 때까지(replace(a, "")를 실행할 수 있을 때까지) replace 작업을 하고, 안 되면 except 이하의 구문을 실행하게 하고 싶었는데 먼가 잘못된 것 같다...
  👉 이후에 찾은 원인: 그냥 s.replace()가 아니라 s = s.replace로 작성했어야 함~~~!

• 1번 수정 후 ▶ 여전히 [Time Limit Exceeded]: try 구문 안에서 오류가 발생하는 지점이 없어서 계속 for문이 반복되어서 그런 듯 (replace()는 대체할 문자열이 없어도 에러가 뜨지 않음)

• 2번 수정 후 ▶ 정답
  
  

정답 🥳

def isValid(self, s: str) -> bool:
    while (("()" in s) or ("[]" in s) or ("{}" in s)):
        s = s.replace("()", "").replace("[]", "").replace("{}", "")
    if len(s) == 0:
        return True
    else:
        return False

"()" in s 대신 s.find("()")>-1을 쓸 수도 있다
("()"가 s 내에 존재할 경우 해당 문자열의 첫 인덱스, 존재하지 않으면 -1 반환)

다른 solution 😮

def isValid(self, s):
    stack = []
    dict = {"]":"[", "}":"{", ")":"("}
    for char in s:
        if char in dict.values():
            stack.append(char)
        elif char in dict.keys():
            if stack == [] or dict[char] != stack.pop():
                return False
        else:
            return False
    return stack == []

👉 pop()을 통해 stack의 마지막 요소가 각 value에 대응되는 key인지 확인하면서, 해당 요소를 stack에서 빼냄

배운 것 💪✨

• s.replace(x, y) 만으로는 새 문자열이 반환될 뿐, s는 바뀌지 않는다
  👉 s = s.replace(x, y)의 형태로 작성해야 함
• string.find(찾을 문자열[, 찾을 위치])
  string에서 찾을 문자열이 처음 나온 위치를 반환하고, 문자열이 없을 경우 -1 반환 (index()와의 차이점)