내일은 알고리즘

https://leetcode.com/problems/find-pivot-index/

좌측합과 우측합을 같게 만드는 중심을 찾는 꽤 재밌는 문제였습니다.

슬라이딩 윈도우와 비슷한 느낌으로 구현했는데, 좌측합이 0, 우측합이 모든 누적합인 상태로 시작해서 이번 턴에 중심으로 테스트하는 값을 우측합에서 빼고 이전 턴에 테스트한 값을 좌측합에 더하는 식으로 구현했습니다.

testcase 1번값의 풀이진행을 그림으로 나타내면 아래와 같습니다.

class Solution:
    # def pivotIndex(self, nums: List[int]) -> int:
    def pivotIndex(self, nums: list) -> int:
        pivot = -1
        idx = 0
        leftSum = 0
        rightSum = self.getRightSum(nums)

        while(idx < len(nums)):
            rightSum -= nums[idx]
            if(idx > 0):
                leftSum += nums[idx-1]
            
            if(leftSum == rightSum):
                pivot = idx
                break
            idx += 1

        return pivot
    
    def getRightSum(self, nums:list):
        rightSum = 0
        for i in nums:
            rightSum += i

        return rightSum


input = [[1,7,3,6,5,6],[1,2,3],[2,1,-1]]
for i in input:
    print(Solution().pivotIndex(i))

https://leetcode.com/problems/running-sum-of-1d-array/

LeetCode의 14일짜리 코스를 시험삼아 시작해봤습니다.

하루에 2문제씩 14일간 28문제를 푸는 코스네요.

배열의 누적합 문제입니다.

딱히 설명할 부분은 없는 간단한 문제였습니다.

LeetCode에서 주어지는 Example 코드가 Python 3.5 이상에서만 돌아가는 코드여서 주석처리 했습니다.

class Solution:
    # def runningSum(self, nums: List[int]) -> List[int]:
    def runningSum(self, nums: list) -> list:
        sum = 0
        answer = []
        for i in nums:
            sum += i
            answer.append(sum)
        
        return answer


input = [[1,2,3,4],[1,1,1,1,1],[3,1,2,10,1]]
for i in input:
    print(Solution().runningSum(i))

https://leetcode.com/problems/roman-to-integer/

최근에 추천받았던 LeetCode라는 외국 PS사이트입니다.

디자인도 예쁘고 개인이 사용한 자료구조, 알고리즘 통계나 문제 풀이 코스같이 특정 기간동안 스케쥴 관리 해주는 기능이 참 좋아보이네요.

LeetCode는 Easy - Medium - Hard 3단계로 문제의 난이도가 구분되어 있습니다. 회원가입하자마자 문제 리스트를 추천받았는데 가장 위에 있던 문제입니다. 

문제 자체는 문자열을 조건에 맞추어 숫자로 변환하기만 하면 되는데요, if문을 중첩하거나 switch-case를 쓰거나 여러가지 방법이 있을겁니다.

Python의 Dictionary를 이용해서 두가지 방법으로 풀었는데요.

첫 코드는 if문을 여러개 쪼개서 조건을 구분한 코드인데 통과는 되었지만 코드라인도 길고 깔끔하지 않아서 Dictionary를 좀 더 사용하는 코드로 다시 작성했습니다.

class Solution(object):
    def romanToInt(self, s: str) -> int:
        sum = 0
        i = 0
        symbol = {'I': 1, 'V': 5,'X': 10,'L': 50,'C': 100,'D': 500,'M': 1000}

        while(i < len(s)):
            if( i < len(s) - 1) :
                if(s[i] == 'I'):
                    if(s[i+1] == 'V'):
                        sum += 4
                        i += 1
                    elif(s[i+1] == 'X'):
                        sum += 9
                        i += 1
                    else : 
                        sum += symbol[s[i]]
                elif(s[i] == 'X'):
                    if(s[i+1] == 'L'):
                        sum += 40
                        i += 1
                    elif(s[i+1] == 'C'):
                        sum += 90
                        i += 1
                    else : 
                        sum += symbol[s[i]]
                elif(s[i] == 'C'):
                    if(s[i+1] == 'D'):
                        sum += 400
                        i += 1
                    elif(s[i+1] == 'M'):
                        sum += 900
                        i += 1
                    else : 
                        sum += symbol[s[i]]
                else : 
                    sum += symbol[s[i]]
            else:
                sum += symbol[s[i]]
            i += 1
        return sum


input = ["III","LVIII","MCMXCIV"]

for i in input:
    print(Solution().romanToInt(i))

# Solution().romanToInt(input[2])

class Solution(object):
    def romanToInt(self, s: str) -> int:
        symbolValue = {'I': 1, 'IV':4, 'V': 5, 'IX':9, 'X': 10, 'XL':40, 'L': 50, 'XC':90, 'C': 100, 'CD': 400, 'D': 500, 'CM': 900, 'M': 1000}
        sum = 0
        i = 0

        while(self.indexInString(i, s)):
            if(self.indexInString(i+1, s) and s[i: i+2] in symbolValue):
                sum += symbolValue[s[i: i+2]]
                i += 2
            else:
                sum += symbolValue[s[i]]
                i += 1
        return sum

    def indexInString(self, i: int, s:str)-> bool:
        return i < len(s)



input = ["III","LVIII","MCMXCIV"]

for i in input:
    print(Solution().romanToInt(i))

# Solution().romanToInt(input[2])