2020 GoogleKickStart Round E CodeReview

Proc A

 

array안에서 가장 긴 arithmetic subarray를 찾는 문제이다.

문제를 풀 당시에는 몰랐는데 업솔하고, 또 코드리뷰를 하면서 내가 작성한 솔루션이 개선 불가능하게 작성되었다는 사실을 발견했다.

 

my solution

내 코드는

1. 배열의 첫항부터 끝항까지 순회한다.

2. 순회하며 앞뒤항의 diffrence를 구한다.

3. 이를 common diffrence와(바로 전에 구한 diffrence) 비교하여 같으면 카운트해준다.

4. 다르면 max카운터와 비교하여 큰 값을 저장하고 common diffrence를 update한다.

 

시간 복잡도는 O(n)으로 TC 2개 모두 무난하게 통과한다.

하지만 구글 오피셜 editorial과 tm윌리엄 린의 코드를 참고하여 코드를 들여다보니 내 코드는 그냥 말도 안되는 방식으로 동작하고있었다.

 

우선 구글은

1. 먼저 배열의 첫 항을 기준으로 잡고 여기서부터 common diffrence와 비교하며 카운트를 해준다.

2. 그리고 나서 기준(인덱스)이 절대로 카운트보다 작을 수 없다는 당연한 사실을 이용하여 인덱싱을 해준다.

 

이를 통해 알 수 있는 사실은....

만약 크기가 5인 [1, 2, 3, 4, 7]라는 배열이 주어 질 경우

-----------------------------------------------------

 

딱 여기까지 글로 정리하다가 놀라운 사실을 발견했다.

그냥 내가 쓴 솔루션이 말도 안되게 스마트하다🤩🤩

 

전에 먼저 윌리엄 린의 코드를 좀 더 효율적으로 짠 이미지를 먼저 확인해보자

tmwilliamlin

I=max(I+1, ans);

이 부분이 구글 솔루션을 보고 윌리엄의 코드에 내가 추가한 한 줄이다.

인덱스 i가 굳이 ans보다 뒤로 갈 이유가 없다.

 

그리고 내 코드는 절대 인덱스가 뒤로갈 수 없다는 사실을 이용해 무조건 1씩 증가하면서 가능한 답을 찾아낸다.

 

A번 결론

개선 불가능한 코드가 아니라 가장 이상적인 방법이었다.

 

Proc B

 

8/25 4시

술먹고 보는중이라 그런지 답지 보면서 푸는데 다틀린다 Huh.....

대회 당시에 어떻게 푼건지 참.... 오늘은 스킵

 

솔루션에도 나와있고, 윌리엄도 같은 방식으로 풀었는데 그냥 constructive algorithm 일명 빡구현이다.

대회 당시 내 솔루션은 둘 모두에게 안보이는 빌딩이 있을때, 없을때를 기준으로 구현을 시작했는데,

구글 솔루션과 윌리엄의 코드를 보면 그냥 안보이는 빌딩의 위치가 중요하다는 점을 키포인트로 구현을 해놨다.

 

1. 우선 무조건 안되는 경우를 짤라준다

2. 왼쪽에서만 보이는 빌딩을 구현해준다

4. 둘 모두에게 보이는 빌딩을 구현해준다

이때 안보이는 빌딩이 왼쪽에서만 보이는 빌딩과 둘 모두에게 보이는 빌딩 사이에 올 수 있으면 여기서 구현해준다

4. 둘 모두에게 보이는 빌딩이 2개 이상이면 이 빌딩 사이에 안보이는 빌딩을 구현한다

5. 이제 오른쪽에서만 보이는 빌딩을 구현해준다

이때 안보이는 빌딩이 둘 모두에게 보이는 빌딩과 오른쪽에서만 보이는 빌딩 사이에 올 수 있는데 가능하면 구현해준다

 

막상 대회 당시에는 여러 가지 문제로 복잡해 보이는 문제였는데 멀쩡한 정신으로 몇번 보다보니 그냥 보통 난이도의 문제로 보인다.