Programmer 2020_가장_긴_1_L

0과 1로 이루어진 어떤 문자열 inputString과 숫자 n이 주어졌을 때 0을 1로 n개 만큼 치환하여 가장 연속된 1의 길이를 찾으려고 합니다.

예를들면,

과 같이 주어졌을 떄, 0111011100111111111111111100011111과 같이 치환했을 경우 16이라는 가장 긴 연속된 1을 얻습니다.

inputString, n을 입력받아 가장 긴 연속된 1의 길이를 반환하는 solution을 작성해주세요.

문제 내용은 정말 간단한 것 같은데 생각보다 해결법이 금방 떠오르지 않았다.

0을 기준으로 스플릿 하는 방향으로도 접근해보고 했지만 마땅한 해결법 같지는 않다.

결국 가장 기본적인 방법인 완전 탐색으로 해결해야 한다는 결론에 이르렀는데, 문제는 어떻게 탐색할 것인가 이다.

임의의 문자열이므로 앞에서부터 차례로 0을 n개 만큼 1로 치환하면서 연속된 1의 길이를 구한다.

만약 01110011110011011111, 3 이라는 임의의 문자열과 치환 가능 수가 정해졌다면 아래와 같은 흐름으로 탐색이 되겠다.

즉, 앞에서 부터 0을 만난다면 n개 만큼 1로 치환하고 만일 그 다음 0을 만났다면 가장 먼저 치환했던 1을 0으로 바꾼 뒤 현재의 0을 1로 치환함으로써 계속 길이를 비교한다.

여기서 가장 먼저 치환했던 1을 0으로 바꾼다.는 부분에 주목하자. 딱 보았을 때 Fisrt in First out이 떠오르지 않는가? Queue를 이용해서 문제를 풀면 되겠다.

위와 같이 진행한다면 O(N)으로 문제 해결이 가능하다 (loop가 한 번 사용된다.)

코드를 살펴보자.

쉽지 않은 문제였다. 문제를 해결하기 위한 접근법이 금방 떠오르지 않았고, Queue를 이용하여 문제를 해결한다는 접근법을 파악했음에도 실제로 index (현재의 위치 - Queue에 삽입된 0의 위치 중 가장 처음것) 계산이 계속 헷갈려서 애를 먹었던 문제다.