Google KickStart Round E 2020 Review

전체 2386등으로 마무리, 4문제중 2솔했다.

뒤에 두 문제는 볼시간도 없어서 내용 아예 모르고, 앞에 1,2번 문제는 쉬운편이었는데 2번 문제 구현을 너무 멍청하게 했다.

대회 끝나고 tmwilliamlin 유튜브에서 2번문제 구현한걸 봤는데, 내 머리는 장식이라는 생각이 많이 들었다.

 

아무튼 본격적으로 내가 푼 문제들 리뷰 시작

 

1. Longest Arithmetic

주어진 배열에서 가장 긴 Arithmetic한 배열을 찾는 문제이다.

단순한 구현문제로 주어진 조건 그대로 구현하면 된다.

윌리엄도 똑같이 했다.

 

2. High Buildings

안드레와 슐레씨가 한줄로 늘어진 구글 캠퍼스 빌딩들 각각 왼쪽끝, 오른쪽 끝에서 서로를 쳐다본다.

이때 보이는 빌딩은 각자가 있는 빌딩보다 같거나 높은 것 만 보인다고 가정한다.

전체 빌딩의 갯수와 안드레, 슐레씨에게 보이는 빌딩의 갯수, 안드레, 슐레 둘 모두에게 보이는 빌딩의 갯수가 주어질때 가능한 빌딩의 배열울 출력하는 문제이다.

 

간단한 constructive algorithm이다.

한줄로 늘어진 캠퍼스를 3부분으로 나누어 생각한다. 좌우 양끝에는 안드레와 슐레씨가 서 있고, 가운데에는 둘 모두에게 보이는 빌딩이 있다.

문제 그대로 구현하면 되는데 이때 문제에서 말하지 않은 빌딩의, 둘 모두에게 보이지 않는 빌딩들, 위치가 상당히 중요하다.

둘 모두에게 보이지 않는 빌딩의 위치는 무조건 안드레가 서 있는 위치와 둘 모두에게 보이는 빌딩 사이 이거나 그 반대이다.

 

1,2번 문제 전부 TC가 2개씩 있었는데 한번에 다 통과되서 각 TC간의 디테일한 차이는 모른다.