[C++] LeetCode : Excel Sheet Column Number

Question

Given a string columnTitle that represents the column title as appears in an Excel sheet, return its corresponding column number.

 

Excel 시트에 나타나는 열 제목을 나타내는 문자열 columnTitle이 주어지면 해당 열 번호를 반환합니다.

제약사항

• 1 <= columnTitle.length <= 7
• columnTitle consists only of uppercase English letters.
• columnTitle is in the range ["A", "FXSHRXW"].

---

Solution

문제를 풀 때 고려한 사항

• 문자는 대문자만 나옴.
• FXSHRXW가 마지막 문자인 것을 보니 int범위의 최댓값이 아닐까라는 추측이 듦

---

Solution1

간단하게 예를 들어서 생각해본다.
1자리 수 => 1 ~ 26, 총 26개 
2자리 수 => 27 ~ 702, 총 676개 = 26²개
3자리 수 => 703 ~ 18278, 총 17576개 = 26³

그렇다면 26개의 단위로 column number를 확인할 수 있을 것 같다. 예를 들어,
 a = 1
 b = 2
 c = 3

"ABC" 라면 

'C' = 'C' - 'A' + 1

'B' = ('B' - 'A' + 1) * 26;

'A' = ('A' - 'A' + 1) * (26²)

로 세 수를 더하면 column number이다. 

 

class Solution {
public:
    int titleToNumber(string columnTitle) {
		int ans_col = 0;					// return 할 column 값
		int str_len = columnTitle.length(); // 문자열의 길이
		int back = str_len - 1;				// 문자열의 뒤부더 탐색
		
		int base_num = 0;					// base_num을 기준으로 얼마나 26을 곱할지
		
		while(back >= 0){					// 문자열 맨 앞까지 탐색
			// 기준 수를 기준으로 얼마나 26을 곱할지 계산하는 부분
			int copy_base_num = base_num;	
			int mul = 1;
			while(copy_base_num--){
				mul *= 26;
			}
			
			ans_col += (columnTitle[back] - 'A' + 1) * mul;
			if(mul == 1) mul--;
			
			base_num++;
			back--;
		}
		
		return ans_col;
    }
};

• Time complexity : O(n) 
• Space Complexity : O(1) 

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/113/math/817/

Explore - LeetCode