C++로 시애틀에서 플로리다로 더 많이 이동했는지 확인하는 방법

두 종류의 문자 'S'와 'F'로 구성된 문자열 S가 주어진다고 가정해 보겠습니다. S[i]가 'S'라면 i번째 날에 시애틀(Seattle)에 있는 것이고, 'F'라면 플로리다(Florida)에 있는 것입니다. 이때 우리가 확인해야 할 것은 시애틀에서 플로리다로 이동한 횟수가 플로리다에서 시애틀로 이동한 횟수보다 많은지입니다.

예를 들어 입력이 S = "SSFFSFFSFF"라면 출력은 True가 됩니다.

접근 방법

이 문제는 간단한 관찰 하나로 해결할 수 있습니다. 시애틀과 플로리다 사이를 오가려면 반드시 왕복으로 이동해야 하기 때문에, 전체 여정의 시작 지점과 마지막 지점만 비교하면 됩니다.

시애틀('S')에서 출발해 플로리다('F')에 도착했다면, 시애틀→플로리다 이동 횟수가 플로리다→시애틀 이동 횟수보다 정확히 1회 더 많습니다. 반대로 시작과 끝이 같은 도시라면 두 방향의 이동 횟수가 동일합니다.

따라서 다음 단계로 문제를 해결할 수 있습니다.

• n := 문자열 S의 길이
• S[0]이 'S'이고 S[n-1]이 'F'이면 true 반환
• 그렇지 않으면 false 반환

예제 코드

아래 C++ 구현을 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
bool solve(string S)
{
    int n = S.size();
    if (S[0] == 'S' && S[n - 1] == 'F')
        return true;
    else
        return false;
}
int main(){
    string S = "SSFFSFFSFF";
    cout << solve(S) << endl;
}

입력

"SSFFSFFSFF"

출력

1

출력값 1은 true를 의미합니다. 문자열이 'S'로 시작하고 'F'로 끝나기 때문에, 시애틀에서 플로리다로 이동한 횟수가 그 반대 방향보다 정확히 한 번 더 많다는 것을 알 수 있습니다.