[백준][C++] 16171. 나는 친구가 적다 (Small)

16171. 나는 친구가 적다 (Small)

16171번: 나는 친구가 적다 (Small)

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

나는 친구가 많지만 풀어본 문제이다.

 

처음 접근부터 틀렸던 문제. 처음에는 순서대로 문자열을 비교해준 다음에, 만약 틀린 부분이 하나라도 있다면 그 자리에서부터 다시 검사하는 코드였다.

 

코드에서 생기는 치명적인 문제를 발견했다...

문자열이 아닌 순간부터 그 다음을 다시 체크하니 있는 문자열도 체크하지 못하는 것...

코드는 이러했었다.

for (int i = 0; i < str.size(); i++)
{
    if (sameCnt == target.size()) break;

    if (str[i] == target[sameCnt])
        sameCnt++;

    else
        sameCnt = 0;
}

 

그래서 안전하게 모든 문자를 첫 시작으로써 검사하기로 한다.

예를 들어...

input =>
ABAD
AD

1. A
- string[0] => A 통과
- string[1] => B 실패 (D와 같지 않음)

2. B
- string[0] => 실패 (A와 같지 않음)

3. A
- string[0] => A 통과
- string[1] => D 통과
모두 통과! break!

이렇게 돌아가는 로직이다. 코드는...

for (int i = 0; i < str.size(); i++)
{
    for (int j = i; j < str.size(); j++)
    {
        // target은 0부터 시작하기 때문에 idx => j - i
        if (str[j] == target[j - i])
        {
            if (++sameCnt == target.size())
            {
                break;
            }
        }
        else break;
    }

    if (sameCnt == target.size()) break;
}

cout << (sameCnt == target.size());

좋은 문제였다.

로직을 짜기 전에 테스트케이스를 생각하고 짜야겠다는 기본 중에 기본을 다시 상기했다...