[BOJ] The Pleasant Walk 19829번 C++

 

 

문제

There are n houses along the road where Anya lives, each one is painted in one of k possible colors.

Anya likes walking along this road, but she doesn't like when two adjacent houses at the road have the same color. She wants to select a long segment of the road such that no two adjacent houses have the same color.

Help Anya find the longest segment with this property.

입력

The first line contains two integers nand k --- the number of houses and the number of colors (1≤n≤100000, 1≤k≤100000).

The next line contains nintegers a1,a2,…,an the colors of the houses along the road (1≤ai ≤ k).

 

출력

Output a single integer --- the maximum number of houses on the road segment having no two adjacent houses of the same color.

 

 

접근 방식

 

정렬되지 않은 배열에서 조건을 만족하는 가장 긴 부분집합의 길이를 찾는 문제이다

투 포인터를 이용해서 해결할 수 있다

여기서는 단순히 이웃한 말의 색이 다르면 되기 때문에

만약 이웃한 말의 색이 같다면 이전 까지의 부분집합의 최대 길이를 비교해서 ans에 초기화해주고

left 값을 right부터 시작해 다시 부분 집합을 구하면 된다

 

 

코드

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> horses(n);
    for (int i = 0; i < n; i++) cin >> horses[i];

    int left = 0, ans = 0;
    for (int right = 1; right < n; right++) {
        if ( horses[right] == horses[right - 1]) {
            ans = max(ans, right - left);
            left = right;
        }        
    }

    ans = max(ans, n - left);
    cout << ans << endl;
    return 0;
}