C++) 17288, 3개만!

문제 링크 https://www.acmicpc.net/problem/17288

 

문제 내용

문자열을 입력 받아서

연속된 세 숫자의 오름차순 카운트하기(3미만, 3초과는 카운트 안함)

 

잘못 풀었던 풀이법

#include<iostream>
using namespace std;
string s;
short cntplus=1, cntans;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> s;
    for (unsigned short i = 1; i < s.length(); i++) {
        if (s[i] == s[i - 1] + 1)
            cntplus++;
        else
            cntplus = 1;
        if (cntplus == 3) {
            cntans++;
        }
        else if (cntplus > 3) {
            cntans--; cntplus = 1;
        }
    }
    cout << cntans;
}

처음에 3개를 한번에 확인하는 방법을 안쓰고 하나하나 비교하면서 cnt가 3일때에 정답에 대한 cnt++을 했는데, 3개가 초과되었을때에 조건을 잡기가 어려워서 다시 구성했다.

이 코드에 대한 반례는 123456에 대해 output값이 0이 아닌 1이 나온다. 즉, 3번을 초과하여 연속되는 처리에 대해 제대로 하지 못하는 것이다.

 

 

코드

#include<iostream>//17288, 3개만!
using namespace std;
string s;
int cnt = 0;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> s;
    for (unsigned short i = 0; i < s.length() - 2; i++) {
        if (s[i+1] == s[i] + 1 && s[i + 2] == s[i] + 2) {
            if (i + 3 < s.length() && s[i + 3] == s[i] + 3) {
                while (i + 1 < s.length() && s[i + 1] == s[i] + 1)
                    i++;
            }
            else {
                cnt++;
                i += 2;
            }
        }
    }
    cout << cnt;
}

풀이 및 분석

첫번째 for문은 첫번째부터 끝까지 순회하는 범위이고

그 안에 첫 번째 if문은 세 숫자가 연속적으로 오른차순인지 확인하고

그 안에 두 번째 if문은 네 숫자 이상이 연속인지 확인하고

그 안에 세 번째 if문은 네 숫자 이상이면 연속된 구간을 cnt를 증가시키지 않고 i의 범위를 증가시킨다.

이 세 번째 if문이 False일때 즉, else에 대한 처리는 cnt를 증가시키면서 i를 2씩 증가시킨다.

여기서 i를 2씩 증가시키는 이유는 세 숫자를 포함한 구간을 건너뛰고 그 다음 범위를 검사하기 위해서이다.

즉, 3 숫자가 연속적으로 오른차순일 때에만 cnt값을 증가시키는 것이다.