[코테] 리트코드 파이썬 1번 Two Sum, 9번 Palindrome Number, 13번 Roman to Integer

Two Sum - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform

 

주어진 array 중 두 원소를 합쳐서 target 값과 동일할 때의 두 원소의 인덱스를 return하면 되는 문제이다.

 

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

 

간단히 이중반복문을 사용하여 풀 수 있었다.

하지만 runTime이 다른 사용자들보다 높아 다른 분의 풀이를 살펴보니. array를 한바퀴만 돌면서 'target-해당원소'를 하여 얻어낸 값이 해당 array에 있다면 인덱스를 return 하면 O[n]으로 풀 수 있었다.

 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numMap = {}
        n = len(nums)

        for i in range(n):
            complement = target - nums[i]
            if complement in numMap:
                return [numMap[complement], i]
            numMap[nums[i]] = i

        return []  # No solution found

 

---

Palindrome Number - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform

 

앞으로 읽는 것과 뒤로 읽었을 때의 결과가 같은 문자열을 찾는 문제이다.

 

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x<0:
            return False
        
        check=str(x)
        if len(str(x)) % 2!=0: #홀수
            check=check[:len(check)//2]+check[len(check)//2+1:]
            print(check)
        
        
        array1=[i for i in check[:len(check)//2]]
        array2=[i for i in check[len(check)//2:]]
        array2.reverse()
        
        if array1==array2:
            return True
        else:
            return False

 

음수이면 조건이 충족되지 않기 때문에 바로 False를 return 하였다.

주어진 수의 길이가 홀수라면 조건과 상관없는 중간값은 제거하였다.

 

짝수의 길이를 가진 수를 반으로 나눠 리스트로 변환하였고 뒤의 부분에 해당하는 리스트를 reverse() 해주어서 앞부분과 비교했을 때 같으면 True를 그렇지않다면 False를 출력하도록 하였다.

 

---

Roman to Integer - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform

 

로마자를 정수로 바꾸는 문제이다. 다만, 몇몇 조건에서는 다른 방식으로 특정 정수를 표현할 수 있었다.

 

우선 로마자에 해당하는 정수들을 dicts라는 딕셔너리에 저장해두었다.

또 추가적으로 특정 문자 앞에 와서 다른 정수로 표현될 수 있는 문자를 alter라는 딕셔너리에 저장했다.

 

class Solution:
    def romanToInt(self, s: str) -> int:
        dicts={"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
        alter={"V":"I","X":"I","L":"X","C":"X","D":"C","M":"C"}
        array=[dicts[i] for i in s]
        stack=[]
        result=0
        
        for i in s:
            if len(stack)!=0:
                if i in alter.keys() and alter[i]==stack[0]:
                    result+=dicts[i]-dicts[stack[0]]
                    stack.pop()
                else:
                    check=stack.pop()
                    result+=dicts[check]
                    stack.append(i)
            else:
                stack.append(i)

        if len(stack)!=0:
            check=stack.pop()
            result+=dicts[check]

        return result

 

스택을 활용하여 앞에 조건에 해당하는지를 검사했다.

문자열을 돌면서 스택에 아무것도 없다면 해당 값을 stack에 넣었다. 스택에 원소가 있다면, 해당 원소가 특정 원소 앞에 올 수 있는지 확인한다. 올 수 있는 원소라면 현재 원소와 스택의 원소의 차를 이용하여 결과값에 더해준다. 스택에 원소가 있지만 앞에 올 수 없는 원소라면 pop하여 결과값에 더해주고 비어있는 스택에 현재 원소를 넣어주면 된다.