리트코드 문제 11, 12

11. Container with Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container.

입력: s = [1,8,6,2,5,4,8,3,7]

출력: 49

내 풀이

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        distance = len(height) - 1    
        max_volume = 0
        
        for d in range(distance, 0, -1):
            if height[left] < height[right]:
                max_volume = max(height[left] * d, max_volume)
                left += 1
            else:
                max_volume = max(height[right] * d, max_volume)
                right -= 1
        
        return max_volume

• left와 right 포인트를 지정한다. 이때, 두개의 포인트는 제일 끝에서부터 시작한다.
• left와 right 위치에 있는 기둥을 비교하여 (더 짧은 기둥의 높이) * (왼쪽과 오른쪽 기둥의 거리) 만큼을 최대 높이로 지정한다.
• 반복문을 돌때는 제일 끝에 있는 기둥끼리 비교하므로 제일 끝에 있는 기둥의 거리부터 시작한다.

결과

Runtime: 1285 ms, faster than 31.93% of Python3 online submissions for Container With Most Water. Memory Usage: 27.4 MB, less than 85.10% of Python3 online submissions for Container With Most Water.

---

12. Integer to Roman

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.
• Given an integer, convert it to a roman numeral.

입력: num = 1994

출력: “MCMXCIV”

내 풀이

class Solution:
    def intToRoman(self, num: int) -> str:
        convert2roman = {1:'I', 5:'V', 10:'X', 50:'L', 100:'C', 500:'D', 1000:'M'}
        output = ''
        num_digit = len(str(num))
        
        for i in range(1, num_digit+1):
            digit = 10**(num_digit-i)
            quo, rem = divmod(num, digit)           
            num = rem
            if quo < 5:
                if quo == 4:
                    roman = convert2roman[digit]+convert2roman[5*digit] 
                else:
                    roman, i = '', 0
                    while quo*digit > i:
                        roman += convert2roman[digit]
                        i += digit
            else:
                if quo == 9:
                    roman = convert2roman[digit]+convert2roman[10*digit] 
                else:
                    roman, i = convert2roman[5*digit], 5*digit
                    while quo*digit > i:
                        roman += convert2roman[digit]
                        i += digit
                        
            output += roman
        
        return output
            

• 숫자를 각 자리수대로 쪼개서 앞 자리수가 4또는 9인지 여부를 체크한다.
• 만약 4나 9가 아닐시에 while문을 통해 (0) 또는 (5*자리수)에서 시작해 해당 숫자가 될때까지 자리수를 더해나간다.

결과

Runtime: 90 ms, faster than 33.35% of Python3 online submissions for Integer to Roman. Memory Usage: 13.9 MB, less than 80.47% of Python3 online submissions for Integer to Roman.

풀이 1

class Solution(object):
    def intToRoman(self, num):
        values = [ 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 ]
        numerals = [ "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" ]
        res = ""
        for i, v in enumerate(values):
            res += (num//v) * numerals[i]
            num %= v
        return res

중요내용

• 앞자리가 4와 9로 시작하는 경우에 대한 로마 숫자를 모두 만들었다.
• values 와 numerals 리스트의 순서를 큰 값부터 작은 값까지 나열하여서 num을 큰 값부터 차례대로 나누었을때 값을 res에 더하였다.
• 그리고 다음 num은 values 리스트의 요소로 나누었을때 나머지 값으로 지정해준다.