[킥스타트] Google Kick Start 2020 Round D 문제 풀이

이번 포스팅에서는 킥스타트 2020 Round D에 대한 문제 풀이를 공유하고자 한다.

 

1. Record Breaker

배열을 반복하면서 조건문을 통해 카운팅을 하면 쉽게 풀 수 있는 문제이다. 시간복잡도는 O(N)

 

2. Alien Piano

이 문제는 Greedy 알고리즘을 사용해서 풀었다. 먼저 배열을 통해 각각의 note의 pitch를 받아서 채워준다. 이 때 연속해서 같은 값이 나오게 되면 같은 alien piano key를 사용하게 되므로 배열에 넣어주지 않아도 된다. 이렇게 배열을 넣어 주었을 때 만약 다음과 같이 배열이 생겼다고 가정해 보자. 이 때는 연속해서 두 숫자가 같은 경우는 존재하지 않을 것이다.

[1, 8, 9, 7, 6, 5, 4, 3, 2, 1, 3, 2, 1, 3, 5, 7]

이제 배열을 돌면서 이전 원소에 비해 큰 값이라면 upCnt 를 하나 증가시켜주고, downCnt = 0, 이전 원소에 비해 작은 값이라면 downCnt 를 하나 증가시켜 주고 upCnt = 0. 그러면 연속해서 Strict Increase 또는 Strict Decrease가 4개 이상이 되면 규칙을 한 번 어겨야 함을 알 수 있다. alien piano key가 4개 밖에 없기 때문이다.

그렇게 배열을 처음부터 끝까지 탐색하면서 규칙을 위반할 때 마다 하나씩 세어주면 O(K)의 시간 복잡도로 문제를 풀 수가 있다.

 

 

3. Beauty of tree

일단 미리 말하면 나한테는 되게 어려웠다. ㅠㅠ 킥스타트 대회에서도 전체 인원의 5%만 AC를 했던 고난이도 문제였던 것 같다. 이 문제는 트리, DFS 그리고 약간의(?) 수학적인 지식이 있어야 수월하게 풀 수 있었던 문제이다.

먼저 트리를 입력을 받으면 key: 부모 노드, value: 자식 노드 배열 으로 HashMap을 하나 만든다.

이제 이 Map과 전체 트리 원소 갯수 N, 문제에서 주어진 skips 값 A, 그리고 길이가 N인 숫자 배열 probA 네 가지 값을 바탕으로 dfs를 진행한다. dfs이기 때문에 자료 구조는 stack을 사용한다. 이 스택에는 Frame이라는 클래스로 만들어진 객체를 넣는다. Frame은 노드의 인덱스(root의 경우 0, 위의 예제에서는 0~7), 자식노드 인덱스, 그리고 자식노드의 갯수를 가지고 만든다.

path 라는 길이가 N인 숫자 배열을 만든다. path[i] = j 라는 의미는 현재 depth가 i일 때 인덱스가 j인 노드를 거쳐 간다는 의미이다. 예를 들어 path[1] = 1 이라는 말은 depth가 1일 때 Node 2를 지나간다는 의미이고, path[2] = 6 이라는 말은 depth가 2일 때 Node 7을 지나간다는 의미이다. 인덱스와 노드의 숫자가 1씩 차이가 있으니 혼동하지 않도록 주의하자.

probs 배열도 역시 길이가 N인 숫자 배열이다. probs[i] = j 라는 의미는 인덱스가 i인 노드에서 시작해서 가질 수 있는 색칠된 노드의 갯수이다. 예를들어 위의 예제에서 skip = 2 라고 하면 probs = [3, 1, 4, 1, 1, 1, 1, 1] 이다. 이렇게 트리에서 주어진 모든 노드에 대해서 skip값 A, B에 따른 probA, probB 배열을 구한다.

그리고 나서 이제 계산을 해 줘야 하는 부분은 A에 의해 생기는 Beauty 값과 B에 의해서 생기는 Beauty 값을 각각 구하고 A와 B에 모두 색칠이 되어도 하나로 계산이 되므로 A와 B에서 공통된 교집합 부분을 빼 주면 정답이 된다. 예제의 경우 13/8 + 11/8 - 22/64 = 77/32 = 2.65625

이 문제에서는 DFS를 사용하기 때문에 시간 복잡도는 O(N)이 됨을 알 수 있다.

 

 

4번 문제는 패스... ㅠㅠ

2020년 킥스타트 기출문제를 한 번 다 풀어보고 그 다음 4번 문제들만 다시 도전해 보려고 한다..

 

이전 문제들

• 2020 Kickstart Round A
• 2020 Kickstart Round B
• 2020 Kickstart Round C