Google Code Jam 2020 Qualification Round 후기

지난 일요일에 27시간동안 구글코드잼 2020 Qualification Round가 있었고 통과했다. 점수체계도 모르고 참가하면 다 통과하는 연습라운드이거니하고 참가했었는데 Qualification Round에서 총 30점 이상 받아야한다는 규칙이 있었다. 그래도 5문제 중 풀만한 난이도의 문제 3개만 풀면 통과 가능한 점수를 받을 수 있고 시간제한도 넉넉하기 때문에 충분히 시간을 투자하고 참가했다면 거진 통과할 수 있었을 것 같다.

Qualification Round에서 푼 문제들을 간략하게 정리해보겠다.

1. Vestigium

각 행과 열에 중복된 숫자없이 1~N사이의 원소가 한번씩 등장하는 N x N 정사각형을 Latin Square라고 한다. 주어진 정사각형이 Latin Square가 맞는지 확인하라.

입력값:

주어진 N x N 사이즈의 정사각형

출력값:

k = trace = 왼쪽 위에서 시작해서 오른쪽 아래에서 끝나는 중앙 대각선에 위치한 값들의 합
r = 중복된 숫자가 존재하는 행의 갯수
c = 중복된 숫자가 존재하는 열의 갯수

문제풀이:

각 행과 열에 중복된 값이 있는지는 Hash Set으로 확인
arr[0][0], arr[1][1]과 같이 행 인덱스와 열 인덱스가 같을 때가 trace값을 구성하는 대각선에 포함된 위치이다.

T = int(input())

for t in range(1, T + 1):
    N = int(input())
    board = []
    for n in range(1, N + 1):
        row = input().split(' ')
        board.append([int(x) for x in row])
    k = 0
    r = 0
    c = 0
    checkCol = [{'.'} for _ in range(0, N)]
    for i in range(0, N):
        checkRow = {'.'}
        for j in range(0, N):
            if i == j:
                k += board[i][j]
            checkRow.add(board[i][j])
            checkCol[j].add(board[i][j])
            if i == N - 1 and len(checkCol[j]) != N + 1:
                c += 1
        if len(checkRow) != N + 1:
            r += 1
    print("Case #{}: {} {} {}".format(t, k, r, c))

Node.js 환경에서 입출력을 받는 것을 직접 짜보는게 낯설어서 대회때 피했던 자바스크립트로도 다시 풀어봤다. JS를 더 연습할 필요가 있어서 JS로 푸는 것도 좋을 것 같아 아쉽지만, 파이썬 코드가 훨씬 간단하기 때문에 이번 코드잼은 파이썬으로 풀어야할 것 같다. 별개로 아래 코드에 쓰인 JS로 모듈 import하는 법, 입출력 모듈인 readline, async await, IIFE는 이참에 한 번 정리해봐야겠다. ~~(정리하면 링크 추가할 예정)~~

const solution = board => {
    let k = 0, r = 0, c = 0;
    const cols = [];
    for (let i = 0; i < board.length; i++) {
        const rows = new Set();
        for (let j = 0; j < board.length; j++) {
            if (i === 0) {
                cols.push(new Set());
            }
            if (i === j) {
                k += board[i][j];
            }
            rows.add(board[i][j]);
            cols[j].add(board[i][j]);
            if (i + 1 === board.length && cols[j].size !== board.length) {
                c++;
            }
        }
        if (rows.size !== board.length) {
            r++;
        }
    }
    return [k, r, c];
}

const { createInterface } = require('readline');

(async () => {
    const rl = createInterface({
        input: process.stdin,
        output: process.stdout
    });
    
    let T = 0, t = 1, N = 0, board = [];
    
    rl.on('line', line => {
        if (T === 0) {
            T = parseInt(line);
            return;
        } else {
            if (N === 0) {
                N = parseInt(line);
                board = []
                return;
            } else {
                board.push(line.split(' ').map(e => parseInt(e)));
                if (board.length === N) {
                    const [k, r, c] = solution(board);
                    console.log(`Case #${t++}: ${k} ${r} ${c}`);
                    N = 0;
                }
            }
        }
        
    })

    await rl.close;
})();

2. Nesting Depth

입력값:

"010" "123"과 같이 1-9사이의 숫자로 이루어진 문자열 S
1 <= S.length <= 100

출력값:

입력값에 최소한의 괄호를 삽입한 문자열을 출력.
각 숫자는 그 숫자의 크기만큼의 괄호에 감싸져야한다.
1은 (1) 1 depth만큼 2는 ((2)) 2 depth 만큼.
12000의 경우 (1(2))000 이런식으로 표현할 수 있다.

문제풀이:

현재 숫자보다 이전 숫자보다 작으면 현재 숫자 직전에 두 수의 차이만큼 괄호를 닫아줘야한다.
현재 숫자보다 이전 숫자가 크면 현재 숫자 직전에 두 수의 차이만큼 괄호를 열어줘야한다.
마지막값이 0이 아니라면 입력값을 다 순회한 후에 아직 닫히지 않은 괄호가 있다. 이를 처리해줘야한다.

T = int(input())
for t in range(1, T + 1):
    str1 = input()
    res = []
    isOpen = 0
    for i in range(0, len(str1)):
        x = int(str1[i])
        if isOpen < x:
            res.append('(' * (x - isOpen))
        if x < isOpen:
            res.append(')' * (isOpen - x))
        isOpen = x
        res.append(str1[i])
    res.append(')' * isOpen)
    print("Case #{}: {}".format(t, ''.join(res)))

3. Parenting Partnering

입력값:

n개의 일정들이 [시작시간(int), 끝시간(int)] 담긴 배열이 주어진다.
일정들은 정렬되지 않았다.

출력값:

Cameron과 Jamie가 위 일정들을 소화하는 것이 가능한지 불가능한지 프린트.
가능하다면 Cameron의 C를 Jamie의 J를 따서 주어진 일정들에 따라 나열한 문자열을 프린트.

문제풀이:

우선 일정들을 시작시간 순서대로 오름차순 정렬을 한다. 이 때 나중에 본래의 순서로 다시 복구하기 위해 인덱스를 함께 저장해준다. 아래 코드에서 쓰인 정렬된 일정은 [시작시간, 끝시간, 인덱스] 형태를 가지고 있다.
C 또는 J의 이전 일정 끝시간이 현재 일정의 시작시간에 끝나거나 더 빨리 끝났다면 현재 일정을 새로 할당 받을 수 있다.
둘 다 아직 이전 일정이 안 끝났다면 이는 불가능한 스케쥴이다.

def solution(sched, t):
    isJ = 0
    isC = 0
    res = []
    for i in range(N):
        if isJ and isJ <= sched[i][0]:
            isJ = 0
        if isC and isC <= sched[i][0]:
            isC = 0
        if isJ == 0:
            res.append(['J', sched[i][2]])
            isJ = sched[i][1]
            continue
        if isC == 0:
            res.append(['C', sched[i][2]])
            isC = sched[i][1]
            continue
        print("Case #{}: {}".format(t, 'IMPOSSIBLE'))
        break
    else:
        res = sorted(res, key = lambda x : x[1])
        print("Case #{}: {}".format(t, ''.join([r[0] for r in res])))



T = int(input())

for t in range(1, T + 1):
    N = int(input())
    sched = []
    for n in range(N):
        cur = [int(x) for x in input().split(' ')]
        cur.append(n)
        sched.append(cur)
    solution(sorted(sched, key = lambda x : x[0]), t)

탐욕법으로 해결할 수 있는 유명한 문제(2 worker scheduling)라고 한다.

4. ESAb ATAd

이 문제는 안 풀고 넘어갔다. 변명을 하자면 당일에 다른 시험도 있었고, 그 시험 끝나고 다시 코드잼을 풀러왔는데 인터랙티브 문제유형을 파악하고, 테스팅 툴도 다운받고 이해하고 5문제 중 가장 긴 지문을 읽고 문제 파악해서 해결 할 엄두가 안났다. 한편으론 내가 독해가 필요한 문제에 약한 것 같다는걸 새삼 다시 느꼈다. 영문 독해가 문제가 아니라 한국어로 된 문제도 쓸데없는 말과 중요한 말들이 섞여있는 문제들을 이해하는데 시간이 오래 걸리는 편인 것 같다. 평소에도 요점을 간단히 듣는걸 선호하고 장황한 내용의 문제를 많이 연습 안 한 탓도 있는 것 같다. 이런 문제의 출제의도 자체가 상대가 난해하고 횡설수설한 설명을 듣고 빠르게 요점을 파악하고 문제를 해결할 수 있느냐는 식의 커뮤니케이션 능력을 보려는건가 싶기도하다. 그런 커뮤니케이션 능력은 중요하니까 연습해야겠다. 😔

대회가 끝난 후 다시 살펴보고 있는데 여전히 어렵게 느껴진다. 이번주 안에 이해를 마치고 풀이를 업데이트해볼 예정이다.

5. Indicium

1번 문제 Vestigium에서 나온 주제인 Latin Square에 관한 문제이다. 연계된 문제인가 싶어 재밌어보여서 풀기 시작했다. Latin Square는 1~N의 숫자로만 구성되고 각 행와 열에 중복된 값이 없는 N x N 정사각형을 말한다.

입력값:

N: 정사각형의 크기
K: 왼쪽 위 - 오른쪽 아래 대각선의 합인 trace 값

출력값:

trace의 값으로 K를 갖은 N x N Latin Square을 만드는 것이 가능한지 불가능한지 출력
가능하다면 해당하는 Latin Square를 만들어 출력

Test set 1 (Visible Verdict) :

T = 44
2 ≤ N ≤ 5

Test set 2 (Hidden Verdict):

1 ≤ T ≤ 100
2 ≤ N ≤ 50.

문제풀이:

처음에는 예제를 손으로 적어보며 일정한 규칙을 찾아보고 적용해보았다가 실패했다. 1부터 N까지의 숫자를 같은 행을 하나씩 shift & push 해서 board를 만들고, 행의 순서를 바꿔가며 보드의 trace값과 그 보드를 180도 돌렸을 떄 trace값을 확인해 보는 방식이었다.

손으로 규칙을 찾는게 불가능하단 생각이들어 방법을 바꾸었다. 1~N값의 합으로 K를 만들수 있는 모든 조합을 백트래킹으로 구하고, 또 백트래킹으로 board에 빈칸들을 채워나갔다. 이 방식으로 Test set 1은 통과했는데 Test set 2를 실패했다. N이 조금 커지면 만들 수 있는 라틴스퀘어의 수가 기하급수적으로 커져서 내가 접근한 방식으로는 풀 수 없는 것 같다. (N = 11의경우 776966836171770144107444346734230682311065600000의 서로 다른 라틴스퀘어가 있다고한다)

~~Test Case2도 통과하는 코드로 고쳐서 업데이트 할 예정이다.~~

def getBoard(line):
    
    isSloved = [False]
    board = []
    rows = []
    cols = []
    
    for i in range(N):
        board.append([])
        rows.append(set())
        rows[i].add(line[i])
        for j in range(N):
            if i == j:
                board[i].append(line[i])
                cols.append(set())
                cols[i].add(line[i])
            else:
                board[i].append(0)
    
    def isAvailable(r, c, v):
        if v in rows[r] or v in cols[c]:
            return False
        return True
    
    def place(r, c, v):
        board[r][c] = v
        rows[r].add(v)
        cols[c].add(v)
    
    def remove(r, c, v):
        board[r][c] = 0
        rows[r].remove(v)
        cols[c].remove(v)
    
    def go(r, c):
        if isSloved[0]:
            return
        if r + 1 == N and c + 1 == N:
            isSloved[0] = True
        else:
            if c + 1 == N:
                backtrack(r + 1, 0)
            else:
                backtrack(r, c + 1)
    
    def backtrack(r, c):
        if board[r][c] == 0:
            for x in range(1, N + 1):
                if isAvailable(r, c, x):
                    place(r, c, x)
                    go(r, c)
                    if not isSloved[0]:
                        remove(r, c, x)
        else:
            go(r, c)
    
    backtrack(0, 0)
    return [isSloved[0], board]
    

    
def find(n, k, nums):
    if len(nums) == n:
        return getBoard(nums) if sum(nums) == k else [False, []]
    for x in range(1, n + 1):
        nums.append(x)
        res = find(n, k, nums)
        if res[0]:
            return res 
        nums.pop()
    return [False, []]

T = int(input())

for t in range(1, T + 1):
    N, K = [int(x) for x in input().split(' ')]
    res = find(N, K, [])
    if res[0]:
        print("Case #{}: POSSIBLE".format(t))
        for i in range(N):
            print(" ".join([str(x) for x in res[1][i]]))
    else:
        print("Case #{}: IMPOSSIBLE".format(t))

이후에는 1라운드, 2라운드, 3라운드가 순서대로 진행되며 일정 등수 이상을 받아야 그 다음 라운드로 진출할 수 있다. 1라운드의 경우 3개의 sub round (1A라운드, 1B라운드, 1C라운드) 중 한 번만 일정 등수를 받으면 된다.

1라운드 1500등 이내 (1500등*3번 이라 대략 4500명)
2라운드 1000등 이내
3라운드 25등 이내

그리고 마지막 라운드인 Final Round는 한 번 진행되며 구글 캠퍼스에서 진행되어왔다. 올해는 독일 Munich 구글 오피스에서 진행될 예정이라고 한다. 하지만 코로나 여파로 어떻게 될지 지켜봐야 알 수 있을 것 같다.

등수에 따라 부상도 있다.

1등 $15,000 USD
2등 $2,000 USD
3등 $1,000 USD
4~25등 $100 USD
26~1000등 티셔츠

Qualification 라운드에 참가할 때 빠르게 문제를 해결해나가는 탑랭크 참가자들을 실시간으로 볼 수 있었다. 티셔츠를 받는 정도만되도 엄청 실력있는거라 생각한다. 난 2라운드에 진출하는걸 목표로 잡아보려고한다.

hon9g

Google Code Jam 2020 Qualification Round 후기

1. Vestigium

2. Nesting Depth

3. Parenting Partnering

4. ESAb ATAd

5. Indicium

티스토리툴바

Google Code Jam 2020 Qualification Round 후기

1. Vestigium

2. Nesting Depth

3. Parenting Partnering

4. ESAb ATAd

5. Indicium

'🐺 매일 알고리즘' Related Articles

티스토리툴바