[리트코드 LeetCode] Excel Sheet Column (Python)

Excel Sheet Column

• https://leetcode.com/explore/interview/card/top-interview-questions-medium/113/math/817/
• 분류: Top Interview Questions - Medium - Math

Explore - LeetCode

문제

• 주어진 문자열 columnTitle은 엑셀 문서의 column 이름을 말한다. 이때 상응하는 column number를 반환하라.
• column title과 column number의 예시
• A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ...
• type columnTitle: str / rtype: int

예시

Example 1:
Input: columnTitle = "A"
Output: 1

Example 2:
Input: columnTitle = "AB"
Output: 28

Example 3:
Input: columnTitle = "ZY"
Output: 701

조건

• 1 <= columnTitle.length <= 7
• columnTitle 는 영어 대문자로만 구성됨
• columnTitle is in the range ["A", "FXSHRXW"]

풀이

A~Z: 26*0 + 1~26

A_ = 26*1 + 1~26

B_ = 26*2 + 1~26

…

Z_ = 26*26 + 1~26

ZZ = 26*26 + 26

AAA = 2626 + 261 + 1

AB_ = 26261 + 26*2 + 1~26

AZZ = 2626 + 2626 + 26

BAA = 26262 + 26*1 + 1

→ 각 자릿수는 26 ** (자릿수-1) * 해당 문자가 갖는 수로 연산됨

 

1. 재귀

26의 (문자열 길이-1)승 * 맨 앞 문자(1~26) + 다음 자릿수에 대한 연산 재귀 호출

columnTitle이 빈 문자열이 되면 0 반환

class Solution(object):
    def titleToNumber(self, columnTitle):
        return 0 if not columnTitle else 26 ** (len(columnTitle)-1) * (ord(columnTitle[0]) - ord('A') + 1) + self.titleToNumber(columnTitle[1:])

Time: O(len(title)) / Space: O(len(title))

Runtime: 16 ms (beats 81.3%) / Memory Usage: 13.6 MB (beats 31.87%)

 

2. 반복문

ans = 0
n = len(columnTitle)
for i, ch in enumerate(columnTitle):
	ans += 26 ** (n-i-1) * (ord(ch) - 64)
return ans

Time: O(len(title)) / Space: O(1)

Runtime: 24 ms (beats 39.51%) / Memory Usage: 13.4 MB (beats 62.44%)

 

제곱 연산자 대신 for문을 통해 26을 각 자릿수만큼 곱하는 방법

class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        col_num = 0
        for char in columnTitle:
            col_num = col_num * 26 + (ord(char) - 64)
        return col_num

Time: O(len(title)) / Space: O(1)

Runtime: 16 ms (beats 81.3%) / Memory Usage: 13.4 MB (beats 86.5%)