과자 많이 먹기 - 순차 탐색 알고리즘

알고리즘 연습 Level 6 | 프로그래머스

 

Q.

과자를 좋아하는 동우는 책상 위에 일렬로 놓아진 과자를 발견하였습니다. 과자에는 맛을 숫자로 평가한 종이가 붙어 있습니다. 동우는 맨 왼쪽부터 순서대로 과자를 먹기로 하였습니다. 동우는 먹을 과자를 고를 때 이전에 먹은 과자보다 맛이 더 좋은 과자만 먹습니다.

제일 처음에 맛이 3인 과자를 먹었다면, 다음에는 4보다 작은 맛의 과자는 먹지 않습니다.

책상위에 놓인 과자의 맛이 입력되면, 동우가 최대 과자를 몇 개를 먹을 수 있는지 반환해주는 eatCookie 함수를 완성하세요.

예를 들어 [1, 4, 2, 6, 3, 4, 1, 5] 가 입력된다면 동우는 1, 3, 5, 6, 8번째 과자(각각의 맛은 1, 2, 3, 4, 5)를 골라 총 5개를 먹을 수 있고, 5개보다 더 많이 먹을 수 있는 방법은 없으므로 5를 리턴하면 됩니다.

A.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include<iostream> #include<vector> #include<algorithm> using namespace std;   int eatCookie(vector<int> cookies) { int answer = 0;   int size = cookies.size(), cnt = 0; vector<int>result(size + 1, 0);   for (int i = 0; i < size; i++, cnt = 0) { for (int j = 0; j < i; j++) { if (cookies[i] > cookies[j] && cnt < result[j]) cnt = result[j]; } result[i] = ++cnt; answer = max(answer, result[i]); }   return answer; }   int main() { vector<int > test{ 1,4,2,6,3,4,1,5 };   // 아래는 테스트로 출력해 보기 위한 코드입니다. cout << eatCookie(test); }

먼저 들어온 과자 개수보다 1 많은 배열을 하나 생성한다.

동우가 선택해야 하는 과자는 1 이상의 자연수로, 많이 먹기 위해서는 작은 숫자를 선택해야 한다.

하지만 무작정 가장 작은 수를 선택하는 것은 아래와 같은 반례가 존재한다.

7 8 9 10 1 2

작은 수를 선택하여 1을 먹었는데 다음 먹을 과자는 2밖에 존재하지 않는다.

그러나 7을 먹을 경우 연이어 8, 9, 10의 과자로 총 4개를 먹을 수 있다.

따라서 문제의 핵심은 적은 값을 선택하되 뒤에 선택한 과자(값)보다 큰 과자(숫자)가 얼마나 많이 있느냐가 핵심이다.

따라서 result의 각각의 인덱스에 0번 과자(예시의 1), 1번 과자(4), 2번 과자(2)…순서로 각각에 대해 특정 과자를 선택했을 때 연이어 선택할 수 있는 과자의 수를 누적하고, 이를 마지막 값과 비교하여 반환한다.