Code jam 2016 qualification round A, B

코드잼 페이지 : https://code.google.com/codejam/contest/6254486/dashboard#s=p0

지난 2016년 4월 9일, 동아리 사람들끼리 학교에 강의실 하나 빌려서 구글 코드랩 퀄리피케이션 라운드 문제를 각자 풀어보는 시간을 가졌다.

총 4개의 문제가 나왔었고 다른 코드잼에서처럼 문제당 각각 small, large set 두가지 set에 대해서 정답을 제출할 수 있었다. 27시간동안 진행되며, 최소 30점 이상을 획득해야 다음 '예선'  코드잼에 참가 가능. 아마 전세계 동시 시작이다보니 시차때문에 시간을 많이준것 같고, 최소 점수도 낮은걸로 봐서 진짜 퀄리파잉 목적으로만 진행된것 같다.

알고리즘 문제는 잘 푸는건 아니지만 (전에 weird 포스팅만 봐도…) 오랜만에 동아리 사람들 얼굴도 볼겸 해서 그냥 반쯤 놀러가는 기분으로 학교 갔다가, 다른 친구들이랑 말도 안 섞고 모니터만 한참 쳐다보다 문제 다 풀고 나서야 치킨 먹으면서 떠들고 그랬었다.

그래도 나름 세번째 문제 large set빼고 다 풀었다

반년 정도 지났지만 그래도 더 잊어먹기 전에 간단하게 되돌아 보려고 한다.

A.Counting Sheep

링크 : link

문제 요약

주어진 숫자 N에 대해서 N, 2N, 3N … 처럼 N에 자연수를 곱해나갈때, 나온 값들의 숫자(digit)가 0부터 9까지 다 발견되는 시점의 결과값을 반환해라. 발견될 수 없는 경우엔 ‘insomnia’를 출력.

억지로 요약하니 많은 비약이 이루어지는것 같은데, 예를 들어 N = 1692 라고 해보자. 이 시점에서 {1, 2, 6, 9} 숫자들이 발견된다. 다음으로 2N = 3384 이므로 추가로 {3, 4, 8} 의 숫자가 발견 되어 총 {1, 2, 3, 4, 8, 9}의 숫자가 발견된 상태가 된다. 마지막으로 3N = 5076 이므로 {0, 5, 7} 의 숫자가 추가 발견 되어서 {0부터 9까지} 모든 숫자가 발견되었으니, 이 시점의 값인 5096을 답으로 한다.

값	지금껏 발견된 숫자들	답?
1692	{1, 2, 6, 9}	no
3384	{1, 2, 3, 4, 8, 9}	no
5076	{0, 1, 2, 3, 4, 5 ,6 ,7 ,8 ,9}	yes

N = 1692일때의 테이블

문제의 솔루션은 엄청 직관적인데, N에다 1부터 for문 돌면서 모든 숫자들이 전부 발견되는 시점만 찾으면 된다. 영원히 답이 안 나오는 경우에 대해선(insomnia) 하필 내가 그 날 학교에 약간 늦게 도착해서 풀 시간이 많이 없었고 혹시 첫번째 문제에서 이렇게 귀찮은 조건을 걸었겠거니 해서, 별 다른 생각 없이 N = 0만 아니면 그냥 답이 언젠간 다 나올꺼라고 때려 맞추고 겁없이 무한루프를 걸어줬다.

그래서 나온 코드가 아래와 같다.

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int main() {
    int count;
    cin >> count;

    for (int i = 1; i <= count; i++) {

        int N;
        cin >> N;

        if (N == 0) {

            cout << "Case #"<< i <<": INSOMNIA"<< endl;
            continue;
        }

        bool check[10] = {0,};

        int k;
        for (k = 1;; k++) {

            int nk = k * N;

            while (nk > 0) {
                int digit = nk % 10;
                check[digit] = true;
                nk /= 10;
            }

            // if condition meets, break
            bool condition = true;
            for (int j = 0; j < 10; j++) {
                if (check[j] == false) {
                    condition = false;
                    break;
                }
            }

            if (condition == true) {
                break;
            }

        }

        cout << "Case #"<< i <<": "<< k * N << endl;

    }

    return 0;
}

빠르게 풀었어야 했으니 코드 퀄리티는 무시하도록 하자

코드는 딱히 설명이 필요없을 정도로 간단하다. (= 설명하기 귀찮다) 말한대로 루프 돌면서 k * N값을 계산하고, 거기에 담긴 숫자들을 찾아서 bool check[10]에 마킹해놓는다. check에 담긴 마킹이 전부 true라면 0부터 9까지 모든 숫자가 발견된 시점이라고 판단하고 루프를 탈출한다.

당시에는 문제풀기 바빠서 0일때만 insomnia 처리를 해준것에 대해 아무런 근거가 없었는데, 나중에 코드잼 퀄리파잉 기간이 다 끝나고 풀이가 올라와서 보니 좀 더 확실한 증명을 찾을 수 있었다.

N = 0 이 아닌경우,

1. 숫자 0에 대해서 : N과 곱하는 자연수가 10일때만 봐도 N값과는 상관없이 적어도 하나의 0을 발견한다.
2. 나머지 1~9에 대해서 : N보다 크면서 제일 작은 10의 승수를 P라고 해보자. (N=1,692일 경우 P=10,000) N에다 자연수를 곱해 나갈때, 결과값이 P를 넘는 시점부터 9P를 넘어서는 시점까지, 결과값의 가장 왼쪽 숫자가 무조건 1~9 까지의 숫자를 순차적으로 찍게 된다.
   왜냐? 1~9 중에 하나라도 스킵하려면 아무리 적어도 N이 P보다는 커야 가장 왼쪽 숫자에 자리 올림수를 넘겨 주던가 할텐데, 이미 P의 정의 자체가 N보다 크단걸 이야기 하고 있으니 스킵 불가능.

이래서 0만 아니면 안심하고 무한루프를 돌릴 수 있었다고 한다.

B.Revenge of the Pancakes

링크 : link

문제 요약

한쪽엔 웃는 얼굴이 그려져 있는 팬케이크가 앞뒤 구분없이 스택마냥 쌓여있다. 손님들에게 나갈 팬케이크들은 무조건 웃는 얼굴이 위로 올라가 있어야 하니, 뒤집는 횟수를 최소화 해서 쌓여있는 팬케이크들을 전부 웃는 얼굴이 위로 올라오게 뒤집어라.
단, 뒤집는 건 팬케이크 맨 위부터 임의의 중간까지를 뚝 떼서 위 아래를 돌려 다시 스택에 쌓는 방법만 허용한다.

뒤집는 방법을 말로 설명하기 좀 힘든데 그냥 테이블로 설명하자면,

팬케이크	설명
- - - + + - +	‘-‘는 아랫면 ‘+’는 웃는 얼굴쪽면이라고 가정하자
(- - - +) + - +	위에서 네번째까지의 팬케이크를 뒤집어 보자면..
(- + + +) + - +	요렇게 뒤집어 엎어 놓을 수 있습니다 (위 아래가 뒤집히면서 아랫면, 웃는면이 뒤집힘)

팬케이크 뒤집기 설명

사실 설명은 복잡한데, 솔루션은 되게 간단하다. 그냥 문자열을 오른쪽에서부터 읽어나가면서 +에서 -로 바뀌는 시점, 또는 -에서 +로 바뀌는 시점의 갯수만 세면 된다. 왜냐면 다른 면이 시작되는 부분을 기준으로 뒤집어야 제일 효율적일테니. 거기에 문자열이 -로 시작했으면 맨 마지막으로 전체 스택 뒤집는 횟수 +1 더해주면 되고.

아까 위에서 언급한 예제를 이용해서 풀어보자면 다음과 같다.

팬케이크	설명
- - - + + - +	‘-‘는 아랫면 ‘+’는 웃는 얼굴쪽면이라고 가정하자
(- - -) + + - +	위에서 세번째왜 네번째면이 서로 다르니 뒤집는다
+ + + + + - +	뒤집음
(+ + + + +) - +	마찬가지로 위에서부터 쭉 보다 다른 면을 만나면 뒤집는다
- - - - - - +	뒤집음
(- - - - - -) +	????
+ + + + + + +	PROFIT!!

그래서 나온 코드가 아래와 같다.

#include <iostream>

using namespace std;

int main() {

    int count;
    cin >> count;

    cin.ignore();

    for (int i = 1; i <= count; i++) {

        string cakes;
        getline(cin, cakes);

        // top goes cakes[0]
        reverse(cakes.begin(), cakes.end());

        bool plusStart = cakes[0] == '+';
        int switchCount = plusStart ? 0 : 1;

        for (int j = 1; j < cakes.length(); j++) {
            if (cakes[j - 1] != cakes[j]) {
                switchCount += 1;
            }
        }

        cout << "Case #"<< i <<": " << switchCount << endl;

    }

    return 0;
}

사실 reverse로 문자열을 뒤집어 놓는것 보다 그냥 역순으로 for문 돌리는게 낫겠지만, 당시엔 그냥 바로바로 직관적으로 짜는게 더 중요했었고 이미 reverse라는 함수도 이미 있고 하니까 그냥 사용했다.

코드 설명은 간단하니 넘어가도록 하자. 참고로 A,B번 둘 다 이렇게 Large set까지 풀린다.

나머지 두 문제는 나중에..