백준 23878 lonely Photo [c++]

lonely photo 골드 4

문제 링크

문제

Farmer John has recently acquired $N$ new cows 3 <= N <= 5*10^5, each of whose breed is either Guernsey or Holstein. The cows are currently standing in a line, and Farmer John wants take a photo of every sequence of three or more consecutive cows. However, he doesn’t want to take a photo in which there is exactly one cow whose breed is Guernsey or exactly one cow whose breed is Holstein — he reckons this singular cow would feel isolated and self-conscious. After taking a photo of every sequence of three or more cows, he throws out all of these so-called “lonely” photos, in which there is exactly one Guernsey or exactly one Holstein.

Given the lineup of cows, please help Farmer John determine how many lonely photos he will throw out. Two photos are different if they start or end at different cows in the lineup.

입력

The first line of input contains N.

The second line contains a string of N characters. The ith character is G if the ith cow in the line is a Guernsey. Otherwise, it will be an H and the ith cow is a Holstein.

출력

Please print the number of photos Farmer John will throw out because they are lonely.

풀이

소의 종류는 G, H 2가지가 있는데 소의 사진을 찍었을때, 외로운 소가 있는 사진은 버린다고 한다. 이때 버려야 하는 사진의 수를 출력하는 문제이다.

사진은 소 3마리 이상이 찍히도록 한다.

외로운 소는 사진을 찍었을때, 혼자만 다른 종이면 외로운 사진이다. 모든 경우를 O(N^2)로 탐색하면 500000!으로 시간안에 불가능하다.

어느 중간 위치에 소를 H 종류라고 가정해보자.

H 왼쪽에 G가 있다면 G왼쪽에 H가 있든, G가 있든 외로운 사진이 찍히게 된다.

GGH HGH // 두 경우 모두 외로운 사진.

오른쪽으로 봐도 마찬가지이다.

소를 순차적으로 탐색해가면서, 왼쪽에 나와 다른 소를 count한다. 또한 오른쪽도 나와 다른 소를 count한다. (같은 종류의 소가 나오면 stop)

왼쪽에서 가능한 외로운 사진과, 오른쪽에서 가능한 외로운 사진을 더해줄 수 있다. (바로 다음에 다른 종이 나온 경우는 제외해야 한다. ex count = 1)

또한 왼쪽과 오른쪽의 사진을 합쳐도 외로운 사진이 된다. 그래서 leftCount와 rightCount의 곱도 더해줘야 한다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    string str;

    cin >> n >> str;

    long long lonely = 0;

    for(int i = 0; i < n; i++)
    {
        long long lCnt = 0;
        long long rCnt = 0;
        for(int k = i - 1; k >= 0 && str[k] != str[i]; k--)
        {
            lCnt++;
        }
        for(int k = i + 1; k < n && str[k] != str[i]; k++)
        {
            rCnt++;
        }
        lonely += lCnt * rCnt;
        long long zero = 0;
        lonely += max(zero, lCnt - 1);
        lonely += max(zero, rCnt - 1);
    }

    cout << lonely << endl;
    return 0;
}

• ps
• math