[구름LEVEL] 1등과 2등

난이도	정답률
★★	65.2%

 

구름LEVEL

문제

어느 한 연구결과에 의하면 어느 대회에서 1등을 한 사람은 그 다음 대회에선 2등을 할 확률이 높고, 2등을 한 사람은 그 다음 대회에서 1등을 할 확률이 높다고 합니다.

등수를 나열한 이 문자열에서 "12"와 "21"의 부분 문자열이 각각 1번 이상 존재하면 이 연구결과는 맞다고 판단하고, 그렇지 않다면 틀리다고 판단합니다. 예를 들어, "2112"의 경우 21과 12를 각각 찾을 수 있지만, "212"의 경우 21을 찾으면 12를 못 찾고, 12를 찾으면 21을 찾지 못합니다.

연구결과가 참이면 Yes, 거짓이면 No를 출력합니다.

 

해결

key point, string을 잘 다룰 수 있어야 한다.

1. 12을 먼저 찾았을 때 겹치지 않는 범위에서 21을 찾으면 return 1 → Yes 출력
2. 21을 먼저 찾았을 때 겹치지 않는 범위에서 12을 찾으면 return 1 → Yes 출력
3. 1, 2번 모두 해당되지 않다면 No 출력

• func() 함수에 먼저 찾을 숫자를 넣는다.
• 예시로 12를 넣었다면, findnum은 12가 되고 findnum2는 21이 된다.
• string.find() 함수는 인자로 들어온 문자가 string안에 존재하면 가장 먼저 찾은 문자열의 시작 위치를 반환하고 없다면 string::npos를 반환한다. 이 함수를 이용하여 12의 시작위치를 idx변수에 저장하고 chk배열에 12에 해당되는 위치에 1을 저장한다.
  
  string.substr() 함수는 string.substr(index, length) index부터 length만큼 string을 잘라서 문자열을 반환해준다.
  length를 지정하지 않으면 index위치부터 끝까지의 문자열이 반환된다. 
• 그리고 21을 찾았을 때 해당 인덱스가 chk[]배열에 1로 되어있다면 12와 겹친다는 의미이므로 현재 찾은 범위 이후의 문자열 중에서 21을 다시 찾아보고 있다면 return 1을 한다.
• 애초에 chk[]배열과 비교를 했을 때 겹치는 부분이 없었다면 return 1이며, 이 외 모든 경우에 대해서는 false가 된다.
• 21을 먼저 탐색하는 경우도 마찬가지로 진행되며 func(12), func(21) 두 번의 실행에서 한 번이라도 return 1; 된 적이 없다면 No를 출력한다.

 

코드

#include <iostream>
#include <string.h>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int chk[100005], idx, idx2, findnexti;
string s, ss;
 
int func(string findnum) {
    memset(chk, 0, sizeof(chk));
    string findnum2 = findnum == "12" ? "21" : "12";
 
    if (s.find(findnum) != string::npos) {
        idx = s.find(findnum);
        chk[idx] = 1; chk[idx + 1] = 1;
        if (s.find(findnum2) != string::npos) {
            idx2 = s.find(findnum2);
            if (chk[idx2] || chk[idx2 + 1]) {
                if (chk[idx2]) {
                    chk[idx2 + 1] = 1; 
                    findnexti = idx2 + 1;
                }
                else {
                    chk[idx2] = 1; 
                    findnexti = idx + 1;
                }
                ss = s.substr(findnexti + 1);
                if (ss.find(findnum2) != string::npos) {
                    return 1;
                }
            }
            else {
                return 1;
            }
        }
    }
    else {
        return 0;
    }
    return 0;
}
 
int main() {
    cin >> s;
    if (func("12")) {
        printf("Yes");
    }
    else if (func("21")) {
        printf("Yes");
    }
    else {
        printf("No");
    }
    return 0;
}
 

더 간결하고 쉬운 방법

알아보기 복잡했던 함수내용을 아래처럼 간단하게 바꿀 수 있습니다.

• 주어진 문자열을 str이라고 했을 때
• 단순히 12을 찾았고, 12을 찾고 난 이후 문자열에 대해서 21을 찾았다면 true
• 21을 찾았고, 21 이후 문자열에 대해서 12을 찾았다면 true
• 그 외는 false로 취급하여 No를 출력한다.

if (str.find("12") != string::npos && str.substr(str.find("12") + 2).find("21") != string::npos ||
        str.find("21") != string::npos && str.substr(str.find("21") + 2).find("12") != string::npos)
    cout << "Yes";
else
    cout << "No";

이렇게 무조건 "12"나 "21"을 찾고 난 이후의 substring만 보면 되는 이유는

1. string.find()함수가 처음으로 찾은 문자열의 첫 번째 index를 반환해주기 때문이다. 
2. 12가 먼저 시작할 경우, 21이 먼저 시작할 경우 두 경우 다 고려하여 조건식을 만들었기 때문이다.

위에 작성한 원래 코드에서는 21을 찾았을 경우 그 앞에도 12가 있지 않을까 싶어서 코드가 복잡해지고 길어졌는데 12가 앞에 있는 경우는 이미 func(12)에서 찾았을 것이고 21을 찾았다면 그 이후 substring에 대해서만 생각하면 됐었다.

그래서 뒤에 소개한 방법으로 간결하게 코드를 구성해도 문제를 해결할 수 있다.