본문 바로가기

문돌이 존버/프로그래밍 스터디

(leetcode 문제 풀이) Excel Sheet Column Title

반응형
Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.
For example:
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
 
Example 1:
Input: columnNumber = 1
Output: "A"

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

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

Example 4:
Input: columnNumber = 2147483647
Output: "FXSHRXW"
 
Constraints:
1 <= columnNumber <= 2^31 - 1
# runtime: 44ms
class Solution:
    def convertToTitle(self, columnNumber):
        answer = ''
        while columnNumber != 0:
            tmp = chr(ord('A') + (columnNumber - 1) % 26)
            columnNumber = (columnNumber - 1) // 26
            answer = tmp + answer
        return answer

본 문제는 수학적 규칙을 찾아야 풀 수 있는 문제다. "A...Z"까지, 또 "AA...ZZ"까지 반복되는 형식이기 때문에 문자와 숫자 사이의 관계를 살펴보면 된다. 먼저 글자 1개는 1~26까지의 숫자를 가지는데 이를 이해하기는 쉽다. 그럼 글자 2개의 숫자 범위는 어떠할까?

1개 글자의 범위인 26을 2번 곱하면 된다. 즉 2개 글자는 26 x 26만큼의 범위를 가지고, 3개 글자는 26^3의 범위를 가지게 될 것이다.

여기서 AA(숫자로 27)의 경우, "1 x 26^1 + 1 x 26^0" 로 표현할 수 있다. BA(숫자로 53)의 경우, "2 x 26^1 + 1 x 26^0"로 나타내기 때문에 주어진 columnNumber를 26으로 나누어 몫과 나머지를 활용해 문자를 유추할 수 있음을 알 수 있다. 참고로 나머지에 해당하는 문자가 오른쪽부터 채워지는 형식이다.

다만 주의할 점은 AZ(숫자로 52)의 경우, "2 x 26^1 + 0 x 26^0"로 표현될 수 있는데, 이때 0에 해당하는 문자가 없기 때문에 "1 x 26^1 + 1 x 26^0"으로 나타내야 한다. 따라서 코드를 보면 기존 colunmNumber에서 1을 뺀 뒤에 26으로 나눈 몫과 나머지를 계산하고 있다.

아래는 Discussion 탭에 있는 외국인의 솔루션(deque 사용)을 가져온 것인데, 다른 코드들보다 95% 빠르다고 해서 실험해봤는데 별반 차이가 없었다...

# runtime: 42ms      
from collections import deque
import string
class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        dic = {n: letter for n, letter in zip(range(26), string.ascii_uppercase)} # string.ascii_uppercase: AB...Z 출력
        queue = deque()
        while columnNumber > 0:
            num = (columnNumber - 1) % 26
            queue.appendleft(dic[num])
            columnNumber = (columnNumber - 1) // 26
            
        return ''.join(queue)
728x90
반응형