Google Kickstart 2021 Round A

아쉽다.. 4번 플로우 문젠줄 알고 그래프 그리다가 시간이 끝나버렸다 ㅠ

 

소스 코드 위치: [Google Kickstart 2021 Round A]

A. K-Goodness String

양 끝에서 한 칸씩 이동하면서 같은 문자의 수(c)를 셈한다. 같아야 하는 문자의 수가 정확히 K이어야 함으로 abs(K - c)를 답으로 내면된다.

B. L Shaped Plots

2차원의 각 좌표는 L의 꺽이는 위치의 후보가 된다. 모두 순회해봐야 하니 이 과정은 O(N^2)이 걸린다.

동서남북 4방향 0을 만나기 전까지 연속된 1의 길이를 각 방향에 대해 구한다. 이 때 for문을 한 번 더 돌려서 구하지않고 prefix sum을 구해서 계산하도록 한다. 방향이 4방향이니 4개의 prefix sum 배열을 사용한다.

그리고 조합. (북동) (동남) (남서) (서북) 이렇게 네 가지 경우에 대해 L을 셈한다. 가령 (북동)의 경우 북이 더 긴 경우와 동이 더 긴 경우를 따로 셈해주면 된다.

C. Rabbit House

그리디. 큰 값을 기준으로 먼저 생각해보자.

1. 상자가 가장 많이 쌓인 곳은 더 이상 상자를 쌓을 필요가 없다.

2. 상자가 가장 많이 쌓인 곳이 y만큼 쌓여있고 이와 인접한 각 방향에 대해서 x만큼 쌓여있다면 x가 y보다 작다면 y - 1까지 상자를 쌓아야한다.

1. 2.를 마치고나면 그 다음 가장 많이 쌓인 곳을 기준으로 두 과정을 계속 반복한다. 이는 힙(우선순위 큐)로 구현하면 간단하다.

D. Checksum

Analysis 참고했다..ㅠ

 

cell(i, j)를 2차원 상에서 i행 j열이라고 정의하자.

1. cell(i, j)에 대해 A[i][j] != -1이라면 오염된 값이 아니니 pass

2. cell(i, j)에 대해 A[i][j] == -1이라면 오염된 값

  2-1. i행에 포함된 오염된 값이 하나이거나 j열에 포함된 오염된 값이 하나면 그 값은 시간을 들이지 않고 바로 알 수 있다.

  2-2. i행에 포함된 오염된 값이 최소 두 개 이상이고, j열에 포함된 오염된 값이 최소 두 개 이상이면 이 값들이 이루는 사이클을 깨기 위해선 최소 한 개 이상의 값을 B배열에 정의된 시간을 들여야 한다.

 

  행과 열을 노드로 나타내보자. 행과 열은 각각 독립적이므로 이분그래프로 나타낼 수 있는데, 여기서 cell(i, j)가 오염됐다면 이는 이분 그래프 상에서 간선으로 표현할 수 있고, 가중치를 B[i][j]로 둘 수 있다. 여기서 2-2.에 서술된 사이클을 이분그래프 상에서 그대로 사이클로 나타낼 수 있다.

  여기서 관찰해야하는 점은 2-1.이다. 2-1.은 이분그래프 상에서 트리로 나타낼 수 있는데, 이는 곧 트리 상에서 리프 노드부터 루트까지 타고 올라가면서 값을 알아낼 수 있음을 확인할 수 있다.

  따라서 2-2.가 이분 그래프 상에서 표현된 것을 트리로 변환해야 한다. 여기까지 오면 MST임을 알 수 있고, 최소가 아닌 최대 스패닝 트리로 구성하면 된다.

 

Analysis에서는 prim을 권고하고 있으나 난 그냥 kruscal을 사용했다.