[Project Euler] Coding Quiz 4

 

1억 번째 컬럼명만 구하라길래 입력은 따로 안 받았음.

 

public class Q004 {
    public static void main(String args[]) {
        System.out.println(run());
    }
    
    public static String run() {
        int n = 100000000;
        StringBuilder sb = new StringBuilder();
 
        sb.append((char)('A' + (((26 + ((n%26) - 1)))%26)));
        while((n /= 26) > 26) { sb.append((char)('A' + (((26 + ((n%26) - 1)))%26))); }
        sb.append((char)('A' + (((26 + ((n%26) - 1)))%26)));
 
        return sb.reverse().toString();
    }
}

 

7행:

 n 을 1억으로 초기화한다.

 

10~12행:

 n 이 1000이라고 하자.

 n%26 = 1000%26 = 12 이므로 10행에 의해  sb 에는

아스키 코드 값  'A' + (26 + 12 - 1)%26 = 'A' + 11 에 해당하는 문자인  L 이 추가된다.

그리고 11행 while 루프에 진입하면서  n 에는  n/36 = 1000/36 = 38 이 저장된다.

 

다시 같은 연산을 진행하면  n%26 = 38%26 = 12 이므로 마찬가지로  sb 에는  L 이 추가된다. 또한  n/26 = 38/26 = 1 이므로  n 에는 1이 저장되고 루프를 탈출한다.

마지막으로 12행에 의해  n%26 = 1%26 = 1 이므로  'A' + (26 + 1 - 1)%26 = 'A' + 0 에 해당하는 문자인  A 가 추가된다.

 

따라서  sb 에 형성된 문자열은  LLA 고  reverse()  메소드로 이를 거꾸로 돌리면  ALL 이 된다.

 

사실  'A' + (((26 + ((n%26) - 1)))%26  말고  'A' + n%26 - 1 로 써도 1억에 대한 답은 나온다. 그런데  n 이 26의 배수로 주어지면  'A' - 1 이 되어 알파벳이 아닌 다른 문자가 나오게 된다. 일반화된 풀이를 하려고 하다보니 식이 좀 복잡해졌다.

 

어쨌든 위 풀이가 성립하는 이유는 다음과 같다.

엑셀의 컬럼명은 알파벳 수의 제곱수만큼 사이클을 돌며 형성된다.

여기서는 아스키 코드를 고려하지 않고, A는 1, B는 2, ..., Z는 26에 대응된다고 가정하자.

A~Z(1~26) 사이클이 끝나면 자릿수가 하나 늘어서 AA부터 다시 시작하고, AA~ZZ까지는 26^2개의 컬럼을 만들고, 그 다음 AAA~ZZZ는 26^3개의 컬럼을 만들고, ... 

 

따라서 첫 번째 자리(문자열 상에서 맨 끝 문자)는 26으로 나눈 나머지가 되고,

그 다음 자리는 26으로 나눠진 n을 26으로 나눈 나머지가 되고,

그리고 그 다음 자리는 그 n을 다시 26으로 나눈 값을 26으로 나눈 나머지가 되고, ...

즉 뒤에서부터 셌을 때 i번째 문자는  (n/(26^i))%26 이 되는 것이다.

 

 

이건 거의 직관이고, 조금 더 엄밀하게는 주어진 수를 26진수로 변환한다고 생각할 수 있다.

 

우선 주어진  n 을 2진수로 변환하는 것을 생각해보자. 몫이 0이 될 때까지 2로 나누면서 나머지를 기록하고, 그 수들을 아래부터 위로 쭉 읽으면 그게 2진수로 변환된  n 이다.

마찬가지로  n 을 26으로 나누면서 나머지를 기록하고, 거꾸로 읽는다고 생각하면 된다. 다만 숫자 대신 A~Z를 사용해서 표현하는 것이다.

 

 

 

26으로 나누면서 나머지를 기록하고, 아래에서 위로 쭉 읽으면 1 12 12가 된다.

그리고 이 수들을 1 -> A, 2 -> B, ..., 12 -> L, ..., 26 -> Z로 변환하면 ALL이 된다.

(코드 상에서는  'A' + (나머지 - 1) 로 변환된다.)

 

따라서  n 을 26으로 나눈 나머지에 대응되는 알파벳을  StringBuilder 에 추가한 뒤  reverse()  메소드로 순서를 역전하면 정답이 된다.

 

 

 

 

....고 생각했으나 미처 생각지 못 한 맹점이 있었다.

*2021/01/21

 

 n  = 26이면 Z가 나와야 하는데, 위 코드는 AZ를 뱉어냈다. 

이유는 다음과 같았다.

 

n = 26

n%26 = 0 -> 'Z'

 

n /= 26 -> n = 1

n%26 = 1 -> 'A'

 

n /= 26 -> n = 0

 

Terminate

 

'26진수로 변환한다'는 발상까지는 좋았으나 그 다음을 생각하지 못 한 것이다.

 

n=26*27 = 702라면 다음과 같다.

n = 702

n%26 = 0 -> 'Z'

 

n /= 26 -> n = 27

n%26 = 1 -> 'A'

 

n /= 26 -> n = 1

n%26 = 1 -> 'A'

 

n /= 26 -> n = 0

 

Terminate

따라서 코드를 실행하면 AAZ가 나오지만, 702번째 컬럼명은 ZZ다.

어디가 문제일까?

 

 

일반적인 수에서 자릿수 하나가 넘어가면 10이 된다.

즉 10진수 26은 26진수로 10이고, 10진수 27은 26진수로 11이다.

그리고 현재 엑셀의 컬럼명은 1을 A로, 2를 B로, ..., Z를 26으로 mapping하고 있다.

따라서 27은 11 → AA로 정확히 변환되지만 26은 10 → AZ로 변환된다.

 

Z로 변환되어야 할 26이 AZ로 변환된다.

따라서 이번 loop에서 n%26 == 0이었다면 n에서 1~25의 수를 빼서 다음 n /= 26에서 몫이 0이 되도록 해야 한다.

그러면 마지막 loop에서 n == 0이 되어 탈출조건을 만족하므로 불필요한 A가 붙지 않게 된다.

 

 

 

 

최종 답안은 다음과 같다.

public class Q004 {
    public static void main(String args[]) {
        System.out.println(run());
    }
    
    public static String run() {
        int n = 26;
        StringBuilder sb = new StringBuilder();
 
        do {
            sb.append((char)('A' + (((26 + ((n%26) - 1)))%26)));
        } while((n = (n - ((n%26 == 0)? 1 : 0)) / 26) > 0);
 
        return sb.reverse().toString();
    }
}