[Kickstart][2020][Round C] 1. Countdown

문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff43/00000000003380d2

---

크기가 N인 양수 배열이 주어질 때, K 카운트다운이 배열에 몇 번 발생하는지 구해라.

K 카운트 다운은 K 부터 1까지 1씩 감소하는 등차수열이다. ex) 3카운트다운 = 3, 2, 1

4 3 2 1 5 3 3 2 1 배열에서 3 카운트 다운은 2번 발생한다.

---

정답 가능한지 여부를 저장하는 플래그 변수를 추가한다.

배열을 앞에서부터 탐색하면서 K가 나올 때 해당 플래그를 true로 갱신한다. (K 카운트다운 시작)

탐색중인 수가 K가 아닌 경우는 이전 배열 값 -1 이 탐색 중인 값과 같지 않은 경우 정답 가능 플래그를 false로 갱신한다. (등차수열 판단)

현재 탐색중인 변수가 1이고 정답 가능 플래그가 여전히 true라면 정답이 가능한 수이기 때문에 정답에 + 1을 해주고 정답 가능 플래그를 false로 갱신한다.

 

시간 복잡도는 O(N). N = 배열 크기

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/kickstart/2020/roundC/1.%20Countdown.cpp