[Programmers] Lv3. 징검다리 건너기

https://programmers.co.kr/learn/courses/30/lessons/64062

코딩테스트 연습 - 징검다리 건너기

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.

• 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
• 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
• 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

"니니즈 친구들"은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
"니니즈 친구들"은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.

디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항

• 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
• stones 배열의 크기는 1 이상 200,000 이하입니다.
• stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
• k는 1 이상 stones의 길이 이하인 자연수입니다.

접근 과정

  문제의 내용 중 아래의 두 조건을 제일 중요한 단서로 두고 접근해나갔다. 

       1. "니니즈 친구들"은 가장 가까운 돌로만 건너간다. ( 지나갈 때, 모든 디딤돌을 밟고 지나간다. )

       2. "니니즈 친구들"이 못 건너는 경우는 디딤돌 K개가 연속으로 0보다 작을 경우이다.

 

  그리고 고민 결과, 접근 방법은 아래와 같았다.

 

      - 초기 접근 방법 

          1. [ a , a + k )범위 중 가장 큰 수가 a번째 디딤돌에서 더 이상 못 지나가는 경우이다.

          2. 그러므로 for문으로 ( i = 0 ~ stones.size() )까지 순회하며               *max_element( stones.begin() + i, stones.begin() + i + k )의 결과 값이 제일 작은 경우를 찾아 반환한다.

 

  하지만 위의 초기 접근 방법대로 풀자 정확성은 통과 했으나 효율성에서 시간 초과가 나왔고,

  예상한 원인은 아래와 같았다.

 

    1. 무조건 k * (stones.size() - k - 1)번의 연산이 요구된다는 점이었다.

 

  이러한 문제점을 해결하기 위해 O( N )으로 풀 수 없을까 고민하던 중 다음과 방법을 생각했다.

 

      - 최종 접근 방법

          1. for( i = stones.size() - 1 ~ 0 ) 까지 순환하며 각 인덱스의 돌이 디딜 수 있는 횟수와 동일한 디딤돌의 개수를

             key를 기준으로 정렬되는 map<int ,int>에 ++map[ stones[ i ] 방식으로 카운팅하고,

             [ i, i + k )범위를 벗어나는 i + k번째 돌에 대해 --map[ stones[ i + k ]을 사용하여 삭제

                 => [ i, i + k )범위 내에서 디딜 수 있는 횟수가 가장 큰 것은 항상 map의 맨 마지막에 저장되어

                      있기에 ( *map.rbegin() ).first 형태로  바로 찾는 것이 가능하다.

                 => O( N )의 시간복잡도를 가지게 수정 

 

                 

결과 & 아쉬운 점

결과

  결과는 정확도 최소 0.01ms ~ 최대 0.22ms사이의 성능으로 통과됐고,

  효율성 최소 43.59ms ~ 최대 98.92ms사이의 성능으로 통가됐다.

 

  아쉬웠던 점은 최종 접근까지 다다르면서 너무 오랜 시간이 소요됐다는 점이였다.

  여기에는 못 적었지만 [ i , i + k )영역 내 가장 큰 디딤돌이 영역이 [ i - k, i )로 바뀌어 갈 경우

  가장 큰 디딤돌도 바껴야 하는데 이러한 방법을 찾는데 너무 오랜 시간이 소요됐다.