[ 프로그래머스 징검다리 건너기 (Lv3) ] (C++)

프로그래머스의 징검다리 건너기(Lv3) 문제이다.

 

[ 문제풀이 ]

사람들이 밟을 때 마다 숫자가 줄어드는 디딤돌을 밟으면서 징검다리를 건널 때, 최대 몇 명까지 건널 수 있는지 구해야 하는 문제이다. 문제를 접근하는 큰 틀부터 구체적인 부분까지 순차적으로 알아보도록 하자.

 

#1. 기본 원리

먼저 당연한 이야기부터 하고 들어가보자. 디딤돌은 밟을 때 마다 숫자가 하나씩 줄어들게 되고 사람들은 최대 K칸 만큼 건너뛸 수 있다고 되어있다. 그렇다면 ! 우리는 "연속해서 K개의 디딤돌이 0이 되는 가장 빠른 구간" 을 찾으면 될 것이다.

그 전까지는 디딤돌이 몇 개가 0이되든 어떤 상태로 0이 되든 사람이 무조건 지나갈 수 있다는 것을 의미하기 때문에 연속해서 K개의 디딤돌이 0이 되는 구간을 구하면 될 것이다.

본인은 이 K개의 디딤돌이 연속으로 0이 되는 가장 빠른 구간을 "각 구간에서의 최댓값"을 이용해서 구하였다.

한 가지 예를 들어보자.

[ 2 , 3 , 1 , 4  ] 이렇게 디딤돌이 있고 K = 3 인 경우를 생각해보자.

그리고 지금부터는 디딤돌을 하나씩 탐색해 볼 것인데 탐색을 할 때에는 "현재 탐색 중인 디딤돌이 주어진 길이(K)를 가지는 구간에서의 가장 마지막 디딤돌" 이라고 생각을 하고 탐색을 할 것이다. 무슨 말인지 직접 해보면서 알아보자.

가장 처음에 '2'가 적힌 디딤돌을 보자. 위에서도 말했듯이 "현재 탐색 중인 디딤돌이 구간에서의 가장 마지막 디딤돌" 이라고 생각을 할 것이다. 그렇다면 가장 처음에 나온 '2'라는 숫자를 가진 디딤돌을 현재 구간에서의 가장 마지막 디딤돌이라고 생각을 해보자. 이 구간에서의 최댓값은 '2'가 될 것이다.

다음으로 '3'이 적힌 디딤돌을 보자. 이 '3'는 배열의 Index번호로 따지면 1번 Index이다. 그리고 이 1번 Index가 K = 3인 구간에서 가장 마지막 디딤돌이 되려면 해당 구간은 -1번 Index ~ 1번 Index로 이루어진 구간이 될 것이다.

-1번 Index라는 것은 존재하지 않고, 0번 Index에는 '2'라는 숫자가 존재했다. 그렇다면 이 1번 Index가 구간의 가장 마지막 디딤돌이 되었을 때의 가장 최댓값은 1번 Index값인 '3'이 될 것이다.

다음으로 '1'이 적힌 디딤돌을 보자. 이 '1'은 배열의 Index번호로 따지면 2번 Index이다. 그리고 이 2번 Index가 K = 3인 구간에서 가장 마지막 디딤돌이 되려면 해당 구간은 0번 Index ~ 2번 Index로 이루어진 구간이 될 것이다.

이 때 0번 Index, 1번 Index, 2번 Index 중 최댓값은 1번 Index의 값인 '3'이기 때문에 2번 Index를 구간의 가장 마지막 디딤돌이라고 생각한다면 이 때의 최댓값은 '3'이 된다.

그렇다면 ! 여기서 더 진행하기에 앞서 한가지를 체크하고 넘어가보자. 2번 Index를 구간에서의 가장 마지막 디딤돌이라고 했을 때, 해당 구간에서의 최댓값이 '3'이라는 것을 우리는 알 수 있었다. 그렇다면 이 '3'은 무엇을 의미하는 것일까 ??

바로 "2번 Index를 가장 마지막 디딤돌로 가지는 구간은 최대 3명만 지나갈 수 있습니다" 를 의미한다.

실제로 맞는지 확인을 한번 해보자.

가장 앞에 [ 2 , 3 , 1 ] 만 봤을 때, 가장 큰 숫자인 '3'이 0이 되기 전까지 3명이 지나갈 수 있다. '3'이 0이 되어버리면 K = 3에 의해서 더 이상의 사람이 지나갈 수 없게 되어진다.

즉 ! 우리는 "해당 디딤돌을 가장 마지막 디딤돌로 가지는 구간에서의 최댓값을 통해서 해당 구간을 몇 명이 지나갈 수 있는지" 를 파악할 수 있다.

그럼 3번 Index인 '4'를 한번 살펴보자.

3번 Index를 K = 3인 구간에서 가장 마지막 디딤돌이 된다면, 아마 그 범위는 1번 Index ~ 3번 Index가 될 것이다.

이 때의 최댓값은 '3', '1', '4' 중에 최댓값인 '4'가 될 것이다.

그렇다면 3번 Index를 구간에서의 가장 마지막 디딤돌로 가정한다면, 이 구간은 사람이 4명 지나갈 수 있습니다 라는 것을 의미한다.

그렇다면 이 [ 2 , 3 , 1 , 4 ] K = 3 인 경우에 정답은 뭘까 ???

정답은 '3'이 된다. 왜 ?? 3번 Index를 구간에서의 마지막 디딤돌로 삼았을 때 해당 구간을 4명이 지나갈 수 있지만, 2번 Index를 구간에서의 마지막 디딤돌로 삼았을 때는 3명만 지나갈 수 있기 때문에 전체 징검다리로 보면 이 징검다리는 3명밖에 지나갈 수가 없다. 이 부분에 대한 이야기는 밑에서 더욱 자세하게 할 것인데, 이 내용을 까먹지는 말자.

 

#2. 구현 기본원리

문제는 #1의 내용을 구현해야 한다는 것이다. 굉장히 쉽게 한번 접근해보자.

전체 구간에서 K 길이 만큼의 구간을 탐색해보면서 최댓값을 찾을 수 있을 것이다.

하지만 ! 이렇게 접근하게 될 경우, 전체 구간이 최대 200,000이 되고, K의 값이 200,000이 되서 2중 for문으로 탐색을 하게 되면 어마어마한 탐색을 하게 된다. 즉 ! 이렇게 간단하게 해결을 할 수는 없다. 그럼 지금부터 본인이 구현한 방법을 알아보자.

본인은 이 과정을 Dequeue를 이용해서 구현해 보았다. 먼저 Dequeue에 대해서 간략하게만 알아보고 가자.

Queue는 선입선출, 즉, 먼저 들어간 데이터가 가장 먼저 나오는 성격을 가진 자료구조이다. 그리고 값을 삽입할 때는 가장 마지막에, 값을 삭제할 때는 가장 앞에있는 데이터만을 삭제할 수 있는 자료구조이다.

Dequeue는 Queue와는 조금 다르다. Queue와 다르게 삽입 삭제를 가장 앞과 마지막에 자유롭게 할 수 있다.

즉 ! 가장 앞에 삽입하고 싶은 데이터는 가장 앞쪽에 삽입이 가능하고, 가장 뒤쪽에 삽입하고 싶은 데이터는 가장 뒤쪽에 삽입이 가능하다. 삭제 또한 마찬가지이다. 이러한 성격을 가진 자료구조가 Dequeue이다. 본인은 이 Dequeue를 이용해서 문제에 접근해 보았다.

일단 Dequeue를 어떻게 관리할 것인지에 대해서 부터 미리 말해놓고 그 과정을 구체적으로 살펴보자.

A. "현재 디딤돌을 탐색하고자 하는 구간에서의 마지막 디딤돌이라고 생각했을 때, 최댓값을 가장 앞에 오도록 삽입" 할 것이다.

B. "Dequeue에서 가장 앞에 존재하는 데이터를 제외한 그 외의 데이터는 다음 구간에서의 최댓값이 될 수 있는 후보를 삽입" 할

     것이다.

C. 위의 2가지 조건을 만족하지 않는 데이터는 Dequeue에서 삭제를 할 것이다.

Dequeue를 위와 같이 관리할 것이고 지금부터 편의상 "조건 A, B, C"와 같은 표현들로 위의 말들을 표현할 것이다. 이제 하나의 예시를 가지고 진행해보자. 가장 간단하게 문제에서 주어진 예시를 가지고 진행해보자.

[ 2 , 4 , 5 , 3 , 2 , 1 , 4 , 2 , 5 , 1 ] K = 3 인 경우이다.

그리고 지금부터 Dequeue의 상태를 간단하게 [ ] 와 같이 표현할 것인데, [ A  B ]가 있을 경우 A가 상대적으로 더 앞쪽에 있는 데이터 이고 B가 상대적으로 더 뒤에 있는 데이터라고 가정하고 표현하겠다.

 

1. 0번 Index : '2'

0번 Index를 마지막 디딤돌이라고 생각하게 되면 이전의 구간은 존재하지 않으므로 이 구간에서의 최댓값은 0번 Index인 '2'가 된다. 조건 A에 의해서 이 '2'라는 숫자는 현재 구간에서의 최댓값이 되므로 Dequeue의 가장 앞에 삽입할 것이다.

Dequeue의 상태 : [ 2 ]

2. 1번 Index : '4'

1번 Index를 마지막 디딤돌이라고 생각하게 되면 이전의 구간은 0번 Index와 1번 Index를 포함하는 2개의 구간만이 존재하게 될 것이다. 현재 디딤돌인 '4'가 구간에서의 최댓값이 되기 때문에 이 '4'를 가장 앞에 오도록 삽입해 줄 것이다.

그리고 기존에 있었던 '2'에 대해서 생각을 해보자. 이 '2'는 이제 더 이상 "현재 구간에서의 최댓값"은 될 수가 없다. 이미 '4'가 나와버렸기 때문이다. 그렇다면 ! 이 '2'가 이 다음 구간에서의 최댓값의 후보가 될 수는 있을지에 대해서 생각을 해보자.

절대로 될 수가 없다. 왜그럴까 ?? 왜냐하면 이 '2'보다 더 큰 '4'가 '2' 이후에 나와버렸기 때문이다.

실제로 이 '2'가 포함되는 구간을 살펴보면 [ 0번 Index ~ 1번 Index ] or [ 0번 Index ~ 2번 Index ] 일 때만 포함이 되어진다.

그 이후로 넘어간다면 구간이 1번 Index ~ 3번 Index가 되어버리기 때문에 이 '2'는 더 이상 특정 구간에서의 최댓값 후보가 될 수도 없다. 조건 C에 의해서 더 이상 Dequeue안에 존재할 이유가 없는 데이터가 되어 버린 것이다. 그러므로 삭제를 진행해주자.

Dequeue의 상태 : [ 4 ]

3. 2번 Index : '5'

2번 Index를 마지막 디딤돌이라고 생각하게 되면 해당 구간은 0번 Index ~ 2번 Index 일 것이다.

조건 A에 의해서 이 '5'라는 숫자는 "현재 구간에서의 최댓값" 이 되기 때문에 가장 앞에 오도록 삽입을 할 것이다.

그리고 이제 남아있는 '4'에 대해서 생각을 해보자. 이 '4'는 일단 '5'라는 숫자 때문에 더 이상 "현재 구간에서의 최댓값"은 될 수가 없다. 그렇다면, "이후에 나오는 구간에서의 최댓값 후보" 는 될 수 있는지 생각을 해보자.

이 '4'도 절대로 이후에 나오는 구간에서의 최댓값이 될 수가 없다. 왜 ??? 1번 Index인 '4'를 포함할 수 있는 모든 구간을 적어보면 [ 0번 Index ~ 2번 Index ] , [ 1번 Index ~ 3번 Index ] 가 될 것이다. 그 이후에 구간은 더 이상 이 '4'를 포함하지 않게 된다.

즉 ! 그 이후의 구간에서는 '4'를 더 이상 포함하지 않기 때문에 최댓값의 후보 조차 될 수가 없다.

조건 C에 의해서  더 이상 Dequeue에 존재할 이유가 없는 데이터가 되어버렸으므로 과감하게 삭제해주자.

Dequeue의 상태 : [ 5 ]

그리고 지금부터는 한 가지 더 이야기 할 것이다. 왜 지금부터일까 ? 바로 처음으로 제대로 된 구간이 나왔기 때문이다.

이 전의 0번 Index와 1번 Index 같은 경우에는 사실 K = 3을 만족하는 제대로된 구간이 아니였다.

2번 Index인 지금부터야 제대로 된 구간이 나오기 때문에 지금부터는 한 가지를 더 이야기할 것이다.

바로 ! #1의 가장 마지막 부분에서 했던 이야기이다. 특정 구간에서 지나갈 수 있는 사람의 수는 구간에 따라서 값이 모두 다를 것이다. #1에서 했던 예시를 다시한번 가져와보면, 2번 Index를 마지막 디딤돌로 삼았을 때 해당 구간에서의 지나갈 수 있는 사람은 '3'명 이였고, 3번 Index를 마지막 디딤돌로 삼았을 때 해당 구간에서의 지나갈 수 있는 사람은 '4'명 이였다.

하지만 ! 전체 징검다리로 본다면 더 작은 값인 '3명'만 지나갈 수 있다고 이야기를 했었다.

즉 ! 우리는 "각 구간에서의 최댓값을 통해서 해당 구간을 지나갈 수 있는 사람의 수" 를 지금 구하고 있고, 최종 정답은 "각 구간에서 지나갈 수 있는 사람의 수들 중에서 가장 작은 값" 이 될 것이다.

그렇기 때문에 "현재까지 설정되어 있는 징검다리를 건널 수 있는 가장 작은 값"을 알고 있어야만 정답 도출이 가능하다.

따라서 지금부터는 "현재까지 지나갈 수 있는 사람의 수" 를 이야기 할 것이다.

현재까지의 상태를 정리해보면 다음과 같다.

Dequeue의 상태 : [ 5 ]

현재 까지 탐색 결과, 징검다리를 건널 수 있는 사람의 최대 수 = 5명

4. 3번 Index : '3'

3번 Index를 마지막 디딤돌이라고 생각하게 되면 해당 구간은 1번 Index ~ 3번 Index 일 것이다.

먼저, 조건 A를 살펴보자. 이 구간에서 '3'이 최댓값이 될 수 있을까 ?? 이미 2번 Index에 있는 '5'라는 숫자 때문에 "현재 구간에서의 최댓값"은 될 수가 없다. 그렇기 떄문에 가장 앞쪽에 삽입하지는 않을 것이다.

그럼 두 번째로 조건 B를 살펴보자. 이 '3'이 이 후에 나올 구간에서의 최댓값의 후보가 될 수 있을까 ??

일단 지금 상황으로만 봤을 때는 후보가 될 수가 있다. 왜그럴까 ??? 이 '3'이 포함되는 구간을 한번 생각을 해보자.

[ 1번 Index ~ 3번 Index ] , [ 2번 Index ~ 4번 Index ] , [ 3번 Index ~ 5번 Index ]

이렇게 3가지 구간에 '3'이 포함될 것이다. 그런데 1~3, 2~4 구간에서는 '5'라는 숫자가 이미 존재해 버리기 때문에 최댓값이 될 수가 없다. 하지만 가장 마지막 구간인 '3 ~ 5' 구간을 살펴보자. 우리는 아직 3번 Index까지 밖에 탐색을 하지 않았고, 4번 Index, 5번 Index에는 무슨 값이 있을지 모르는 상태이다. 즉 ! 현재까지만 봤을 때는 이 '3'이 이 후의 구간에서 최댓값이 될 수도 있다는 것을 의미한다.

그럼 조건 B에 의해서 가장 앞이 아닌 곳에 이 '3'을 삽입할 것이다. 그리고 ! 3번 Index까지의 최댓값은 '5'이기 때문에 현재 까지 탐색 결과 징검다리를 건널 수 있는 사람의 최대 수는 5명이라는 사실이 변하지 않는다.

Dequeue의 상태 : [ 5 3 ]

현재 까지 탐색 결과, 징검다리를 건널 수 있는 사람의 최대 수 = 5명

5. 4번 Index : 2 & 5번 Index : 1

너무 동일한 내용을 계속 이야기 해왔고 앞으로도 해야될 것 같으니 이번에는 4번 5번 Index를 묶어서 이야기 해보자.

4번 Index '2'와 5번 Index '1'은 조건 A는 만족하지 않는다. 하지만 그 이후에 나오는 구간에 대해서는 최댓값이 될 수 있는 후보들이 된다. 이유는 '3번 Index : 3'을 진행했을 때와 동일하다. 구간을 생각해보면 최댓값의 후보들이 될 수 있는 값들이다.

4번 Index '2'에 의해서 Dequeue의 상태는 다음과 같이 변할 것이다.

Dequeue의 상태 : [ 5 3 2 ]

아직까지는 현재 구간에서 최댓값인 '5'가 포함되어 있으므로 징검다리를 건널 수 있는 사람의 최대 수 = 5명 이라는 것이 변하지 않는다.

그리고 5번 Index '1'에 의해서 Dequeue의 상태는 [ 3 2 1 ] 로 변하게 될 것이다. 왜냐하면 이제는 '5'가 더 이상 구간에 포함되지 않으므로 Dequeue에서 삭제될 것이고, 최댓값은 '3'으로 갱신되어진다. 또한, '1'은 후보가 될 수 있으므로 Dequeue의 뒤쪽에 삽입 되어 지기 때문에 [ 3 2 1 ] 이 될 것이다.

그리고 ! 여기서 징검 다리를 건널 수 있는 사람의 최대 수가 갱신되어진다. 왜냐하면 현재 구간에서의 최댓값은 '3'이 되고 이 '3'이 의미하는 것은 "이 구간은 사람이 최대 3명밖에 지나갈 수 없어요" 를 의미한다.

따라서 징검다리 전체로 보게 되면 징검다리를 건널 수 있는 사람이 3명으로 갱신되어진다.

Dequeue의 상태 : [ 3 2 1 ]

현재 까지 탐색 결과, 징검다리를 건널 수 있는 사람의 최대 수 = 3명

6. 6번 Index : 4

6번 Index를 마지막으로 이야기할 것이다. 뒤에 숫자들이 더 나오지만 지금까지 했던 내용들과 동일한 이유로 삭제되거나 삽입될 것이기 때문에 이 숫자만을 마지막으로 이야기 하겠다.

현재의 Dequeue는 [ 3 2 1 ] 인데 여기서 '3'은 더 이상 구간에 영향을 미치지 않는 숫자이므로 삭제될 것이다.

그러므로 Dequeue의 상태는 [ 2 1 ] 이 될 것이다. 이 때, '4'가 등장하게 되면 Dequeue에 있는 '2'와 '1'은 어떻게 될까 ??

더 이상 현재 구간에서의 최댓값도 아니고, 그 이후에 나오는 구간에서의 최댓값도 될 수 없다.

그 이유는 3번에서 다뤘던 2번 Index : 5 와 동일하다. 따라서 Dequeue에 더이상 존재할 필요가 없는 값이므로 조건 C에 의해서 삭제될 것이다. 그리고 '4'가 Dequeue에 들어가게 될 것이다.

Dequeue의 상태 : [ 4 ]

 

지금까지 내용을 한번 정리해보자. 본인이 위의 글에서 중간중간 색깔 표시를 해 놓았다.

그 색깔별로 정리를 하면 다음과 같다.

[ 삭제하는 경우 ] - 빨강 & 파랑

1. 빨강색 삭제의 경우 더 이상 해당 원소가 "구간의 범위를 벗어난 경우 삭제" 를 의미한다.

2. 파랑색 삭제의 경우 해당 원소가 "현재 구간에서의 최댓값도 될 수 없고, 다음 구간에서의 최댓값의 후보가 될 수도 없을 경우

    삭제" 를 의미한다.

[ 삭제하지 않는 경우 ] - 초록

1. 초록색 같은 경우, 해당 원소가 "현재 구간에서의 최댓값은 아니지만 이 후에 나올 구간에서 최댓값의 후보가 될 수 있는 값들

    일 경우 삭제하지 않는다는 것"을 의미한다.

 

#3. 구현

실제로 구현을 해보자. 먼저 Dequeue를 이용해서 구현을 할 것인데, 우리에게 필요한 정보는 2가지가 있다.

1. 해당 디딤돌의 값 (숫자)

2. 해당 디딤돌의 Index번호

이렇게 2가지가 필요하다. 해당 디딤돌의 값은 당연히 필요할 것이고, 해당 디딤돌의 Index번호는 탐색에 있어서 현재 구간에 영향을 미치는지 안미치는지를 판단하기 위해서 필요한 정보이다.

따라서 본인은 Dequeue를 pair<int, int> 형태로 선언해서 관리해 주었다. 다음은 실제 코드이다.

	01.	int answer = 987654321;
	02.	deque<pair<int, int>> DQ;

	03. for (int i = 0; i < stones.size(); i++)
	04. {
	05. 	while (DQ.empty() == false && DQ.front().second < i - k + 1) DQ.pop_front();
	06. 	while (DQ.empty() == false && DQ.back().first < stones[i]) DQ.pop_back();
	07. 	DQ.push_back(make_pair(stones[i], i));
	08. 	if (i >= k - 1 && DQ.front().first < answer) answer = DQ.front().first;	
	09. }

line 3)에서 보게 되면 "현재 디딤돌을 구간의 마지막 디딤돌이라고 가정" 하기 위해서 모든 디딤돌을 탐색하기 위한 반복문이다.

line 5)는 "빨강색 삭제" 를 의미한다. 즉 ! Index번호를 통해서 더 이상 구간에 영향을 미치지 않는 원소인지 판단 후, 더 이상 영향을 미치지 않는다면 Dequeue에서 삭제를 해주는 과정이다. 상대적으로 Dequeue의 앞에 있는 숫자일수록 이전 구간에서의 최댓값일 것이다. 따라서 이 경우 삭제는 pop_front()로 진행을 해 주었다.

line 6)은 "파랑색 삭제"를 의미한다. 즉 ! 기존에 Dequeue에 존재하는 값들이 새로 들어오는 값에 의해서 "현재 구간에서의 최댓값도 될 수 없고, 이 후 구간에서의 최댓값도 될 수 없는 경우" Dequeue에서 삭제를 해주는 과정이다.

line 7)은 실제로 값을 삽입하는 과정인데, 위의 설명과는 다르게 무조건 push_back()으로만 삽입을 하게 된다.

위의 설명에서는 "현재 구간에서의 최댓값은 가장 앞에, 그 외의 값들은 상대적으로 뒤쪽에 삽입" 한다고 했었는데 이렇게만 삽입을 한 이유가 line6)을 먼저 진행해 주었기 때문이다.

현재 값이 현재 구간에서의 최댓값이였다면 line6)에 의해서 Dequeue에 있는 모든 원소들은 삭제가 되어 Dequeue가 텅 비어있는 상태일 것이다. 따라서 push_back()으로 삽입을 한다고 하더라도 가장 앞에 있는 것과 동일한 상태가 된다.

반대로, 현재 구간에서의 최댓값은 아니지만, 최댓값의 후보가 될 수 있는 숫자라면 line6)에서 Dequeue가 텅 비지 않을 것이다. 분명히 현재 구간에서의 최댓값은 남아 있을 것이다. 이럴 경우에는 현재 구간에서의 최댓값은 아니지만, 최댓값의 후보가 될 수 있는 숫자이기 때문에 push_back()을 하게되면 상대적으로 뒤쪽에 삽입이 될 것이다.

line 8) "현재 까지 탐색 결과, 징검다리를 건널 수 있는 사람의 수" 를 계산하는 과정이다.

#2에서 내용을 진행할 때, 2번 Index인 '5'부터 제대로 된 구간을 갖기 때문에 2번 Index부터 이 값을 계산을 했었다.

마찬가지로, 제대로 된 구간을 갖는지 판단하기 위해서 "i >= k - 1" 이라는 조건문을 넣어주었고, 기존의 사람수를 갱신해 주는 과정이다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <queue>
using namespace std;
 
int solution(vector<int> stones, int k) 
{
    int answer = 987654321;
    deque<pair<int, int>> DQ;
 
    for (int i = 0; i < stones.size(); i++)
    {
        while (DQ.empty() == false && DQ.front().second < i - k + 1) DQ.pop_front();
        while (DQ.empty() == false && DQ.back().first < stones[i]) DQ.pop_back();
        DQ.push_back(make_pair(stones[i], i));
        if (i >= k - 1 && DQ.front().first < answer) answer = DQ.front().first;    
    }
    return answer;
}