[LeetCode] #168 Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB 
...

Example :

Input: 1
Output: "A"
Input: 28
Output: "AB"
Input: 701
Output: "ZY"

분석해보기

이 문제는 우리가 자주 사용하는 엑셀의 시트컬럼 문자를 숫자로 만드는 것인데 먼저 컬럼문자가 만들어지는 패턴을 분석해보면 아래와 같다.

일단 알파벳의 수는 26개 이며 Z(26)를 넘은 숫자가 오면 다시 A가 된다. 즉 27이면 ZA가 될것이다.

ABCDEFGHIJKLMNOPQRSTUVWXYZ
12345678901234567890123456

A   1   AA  26+ 1   ...   ZA  26×26+ 1   AAA  1×26²+1×26+ 1
B   2   AB  26+ 2   ...   ZB  26×26+ 2   AAB  1×26²+1×26+ 2
.   .   ..  .....   ...   ..  ........   ...  .............
.   .   ..  .....   ...   ..  ........   ...  .............
Z  26   AZ  26+26   ...   ZZ  26×26+26   AAZ  1×26²+1×26+26

따라서 Output: "ZY"가 만들어지려면 아래와 같이 만들 수 있다.
ZY = Z x 26¹ + Y
ZY = 26 x 26¹ + 25
이번엔 숫자로부터 컬럼문자를 만드려면 반대로 (n % 26) 를 사용하면 된다.
701 / 26 = 26 = Z
701 % 26 = 25 = Y

결국 26이라는 알파벳 바운더리에서 계속 나누어진 값이 0이면 계산을 종료할 수 있다.
IF 26 / 26 == 0
하지만 27 / 26 이든 26 / 26 이든 결과값은 항상 1일 것이다.
따라서 (n - 1) / 26으로 계산식을 만들면 결과 값이 0이기 때문에 이런식을 사용한다.

숫자를 알파벳으로

컴퓨터는 수로 이루어져있기 때문에 이 수를 이용해서 알파벳을 표현할수 있는 ASCII테이블을 만들었다.
대문자 A를 표현하기 위해서는 십진수 65를 사용하는데 파이썬에서는 chr(65)함수를 이용하면 A가 출력된다. 반대로 ord("A")함수를 이용하면 65가 출력된다.

코드로 구현하기 (파이썬)

class Solution:
    def convertToTitle(self, n):
        str = ''
        while n != 0
            tmp = 'A' + (n-1) % 26
            n = (n-1) // 26
            str = tmp + str
        return str

시간 복잡도는 : O(N) 공간복잡도는 : O(N)인 알고리즘이며
이제 실행시켜보면 원하는 결과값을 확인 할 수 있다.

solution = Solution()
print(solution.convertToTitle(701))

ZY
Process finished with exit code 0