[Codility] MaxNonoverlappingSegments

 

[Codility] MaxNonoverlappingSegments

 

https://app.codility.com/programmers/lessons/16-greedy_algorithms/

16. Greedy algorithms lesson - Learn to Code - Codility

---

 

해결전략

 

그리디 Greedy  

 

 

A[i]가 cur보다 클 때만 쌍을 선택하므로, 항상 A 벡터의 값이 증가하는 방향으로 요소를 선택한다.

---

 

정답코드

 

#include <vector>
 
int solution(vector<int> &A, vector<int> &B) {
    
    int n = A.size();
    if(n == 0) return 0;
    else if(n == 1) return 1;
 
    int answer = 1;
    int cur = B[0]; // cur는 현재 비교 기준이 되는 B 벡터의 요소이며 초기값은 B의 첫 번째 요소
    
    for(int i = 1; i < n; i++) // 첫 번째 요소는 이미 처리했으므로 두 번째 요소부터 마지막 요소까지 반복
    {
        if(A[i] > cur){  // 만약 A의 i번째 요소가 cur보다 크면
            cur = B[i];  // cur를 B의 i번째 요소로 갱신
            answer++;	 // answer를 1 증가
        }
    }
 
    return answer;
}

 

두 개의 벡터 A와 B가 주어졌을 때, 특정한 규칙에 따라 '선택'된 요소들의 갯수를 찾는다.

• A와 B는 같은 크기의 벡터라 가정.
• A와 B의 각 요소는 (A[i], B[i])와 같이 쌍으로 연결

(A[0], B[0])은 항상 선택된다. 따라서, answer의 초기값은 1이고, cur (현재 선택된 쌍의 B값)는 B[0]이다.

 

그 다음 요소부터, i번째 요소 쌍 (A[i], B[i])에 대해 A[i]가 cur보다 클 경우에만 선택된다. 이 때 cur는 직전에 선택된 쌍의 B값이다.

 

만약 새로운 쌍이 선택된다면, answer는 1 증가하고, cur는 선택된 쌍의 B값으로 갱신된다.
이러한 규칙에 따라 벡터 A와 B를 처음부터 끝까지 검사한 후, 마지막에 answer를 반환하면, 이것이 '선택된' 요소 쌍의 갯수가 된다.

 

 

---