Lv 0. 문자열안에 문자열 *다시 풀어보기* **매우중요**

https://school.programmers.co.kr/learn/courses/30/lessons/120908

 

#include <string>
using namespace std;

int solution(string str1, string str2) {
    if (str1.find(str2) != string::npos) {
        return 1;
    }
    return 2;
}

위의 코드의 경우는 아래에 내가 작성한 코드에서 잘못된 부분이 어느 부분인지 찾지를 못해서 지피티에 수정할 부분을 질문하였을때, 잘못된 부분을 찾아내지 못하고 지피티를 통해서 더욱 간결하게 해결할 수 있는 방향을 제시받아서 작성한 코드이다. 

스트링에서 일부분의 스트링이 존재하는지에 대해서 함수가 있다는걸 알고 있었는데, 이 문제를 풀때 정확하게 기억이 나지 않아서 사용하지 않았고, 해당 함수의 경우는 find() 함수를 사용하면 된다는 것을 이 풀이를 통해 알 수 있다. 

이때에 find() 함수와 string::npos에 대해서 알기 위해서 지피티에 검색해보고 정보를 얻어보면, 

---

위의 코드에서 사용된 `find()` 함수는 C++의 `string` 클래스의 멤버 함수 중 하나입니다. 이 함수는 문자열에서 다른 문자열을 찾아 위치를 반환하는데, 반환 값은 찾은 위치의 인덱스입니다.

- **`find()` 함수**: `str1.find(str2)`는 `str1` 문자열에서 `str2` 문자열을 찾아 그 위치를 반환합니다. 만약 `str2`를 찾을 수 없다면 `string::npos`라는 특별한 값을 반환합니다.

- **`string::npos`**: 이 값은 `string` 클래스의 정적 상수 값으로, 문자열에서 특정 문자열을 찾지 못했을 때 반환되는 특수한 상수입니다. `string::npos`의 값은 `size_t` 자료형의 최대 값으로, 일반적으로 컴퓨터 아키텍처에 따라 매우 큰 양수값입니다.

따라서 위의 코드에서는 `str2` 문자열을 `str1` 문자열에서 찾고, 만약 찾았다면 `1`을 반환하고 찾지 못했다면 `2`를 반환합니다. 이렇게 함으로써 문자열 안에 `str2`가 포함되어 있는지 여부를 확인할 수 있습니다.

 

 

아래에 첨부할 풀이의 경우 내가 처음에 설정한 방향인데, 해당 풀이의 경우는 분명 잘못된 풀이인데, 이 풀이에서 어디가 잘못되어서 특별한 케이스들을 제대로 걸러내지 못하는지 알아내지 못하고 있어서 다시 한번 보면서 탐구해볼 생각이다. 뭔가 되게 잘 들어맞을거 같은데 반례가 있다. 아직 그것을 딱 집어내지 못하였다. 

---

위와 같은 정보를 얻을 수 있다. 추가적으로 size_t에 대하여 궁금하여서 검색해보았고 결과를 추가해본다. 

---

`size_t` 자료형의 크기는 컴퓨터 아키텍처에 따라 다를 수 있습니다. 일반적으로 다음과 같이 크기가 정해집니다.

- 32비트 컴퓨터에서: `size_t`는 4바이트 또는 32비트 크기를 가집니다. 이 경우 `string::npos`는 4바이트 정수형의 최대값인 2,147,483,647일 것입니다.

- 64비트 컴퓨터에서: `size_t`는 8바이트 또는 64비트 크기를 가집니다. 이 경우 `string::npos`는 8바이트 정수형의 최대값인 9,223,372,036,854,775,807일 것입니다.

따라서 컴퓨터 아키텍처에 따라 `size_t`의 크기가 다르며, 따라서 `string::npos`도 아키텍처에 따라 다른 값을 가질 수 있습니다.

---

위와 같은 정보를 얻을 수 있었다. 

스트링 속에 다른 스트링이 존재하는지 찾아볼때는 find() 함수를 사용. 형태는 str1.find(str2)!=string::npos

왜냐하면 없으면 string::npos를 반환하기 때문에. 반환 형태가 없다면 string::npos라는걸 알아야 사용할 수 있는 방법이다. 

 

 

 

++++++++++++++++++++++++++

 

처음에 아래와 같은 코드를 제출해서, 예제 케이스에 대해서는 통과해서 제출해보니 틀렸다. 

#include <string>
#include <vector>

using namespace std;

int solution(string str1, string str2) {
    int answer = 0;
    bool chk=false;
    for(int i=0; i<str1.length()-str2.length();i++){
        for(int j=0; j<str2.length();j++){
            if(str1[i+j]!=str2[j]){
                chk=false;
                break;
            } 
            chk=true;
        }
        if(chk==true) return 1;
    }
    return 2;
}

뭐가 잘못됐을까 생각해보다가, i<str1.length()-str2.length() 가 잘못되었다고 생각해서 i<= 로 수정하였다. 

#include <string>
#include <vector>

using namespace std;

int solution(string str1, string str2) {
    bool chk=false;
    for(int i=0; i<=str1.length()-str2.length();i++){
        for(int j=0; j<str2.length();j++){
            if(str1[i+j]!=str2[j]){
                chk=false;
                break;
            } 
            chk=true;
        }
        if(chk==true) return 1;
    }
    return 2;
}

이와 같이 수정하여도 예제 케이스에서 두개정도가 통과가 안되고 실패하고 있었다.

뭔가 극단에서 통과하지 못하는 경우가 있는것 같아서 더욱 생각을 해보았다. 

 

위의 풀이를 지피티에 제출해서, 내 풀이가 무엇이 잘못되었는지 물어봐서 받게된 답변을 추가해보면, 

---

코드를 살펴보니 `chk` 변수를 초기화하지 않은 상태에서 사용하는 문제가 있습니다. 따라서 `chk` 변수를 각 문자열 비교마다 초기화해주어야 합니다. 또한, 문자열의 길이를 저장할 변수를 두 번 구하는 대신, 한 번만 구하면 더 효율적일 것입니다.

다음은 수정된 코드입니다:

```cpp
#include <string>
using namespace std;

int solution(string str1, string str2) {
    int len1 = str1.length();
    int len2 = str2.length();

    for(int i = 0; i <= len1 - len2; i++) {
        bool chk = true; // chk 변수 초기화
        for(int j = 0; j < len2; j++) {
            if(str1[i + j] != str2[j]) {
                chk = false;
                break;
            } 
        }
        if(chk) return 1;
    }
    return 2;
}

```

위의 코드는 먼저 `str1`과 `str2`의 길이를 한 번만 계산하고, `chk` 변수를 각 반복문 시작 시 초기화하여 문제를 해결합니다. 이제 이 코드를 사용하면 원하는 결과를 얻을 수 있을 것입니다.

---

위와 같은데, 

 

위의 코드에 대해서 bool chk 의 위치에 대해서 변경을 해보아서 제출해도 차이가 없었는데, 

int len1=str1.length();

int len2=str2.lenght(); 를 활용한 코드로 변형하니까, 내가 먼저 작성한 코드도 정상적으로 통과를 하였다. 

도대체 무슨 차이가 있어서 이렇게 따로 변수를 선언해서 해당 str1.lenght(), str2.length(); 값을 사용하는것이 옳게 되는 것일까? 

 

+++++++++++++++

lenght()에 대한 정보를 검색해서 자세히 알아보니 문제가 될마한 부분을 발견하였다. 

일단 내가 int len1=str1.lenght(); 형태로 정의하면, 이 값은 signed int가 되는 것일텐데, 

lenght()의 경우는 unsigned int를 반환한다고 한다. 

이 문제의 경우는 str1과 str2가 str1.lenght()<str2.lenght() 가 될 수 있는 경우가 있는데, 내가 str1.lenght()-str2.lenght()를 계산해서 사용하는데, 이때 unsigned int - unsigned int 형태의 계산이고, 이게 음수가 나올 수 있기 때문에, 여기서 오버플로우가 발생할 수 있겠다는 생각이 들었다. 

 

그래서 나의 코드를 

#include <string>
#include <vector>

using namespace std;

int solution(string str1, string str2) {
    bool chk=false;
    for(int i=0; i<=int(str1.length()-str2.length());i++){
        for(int j=0; j<str2.length();j++){
            if(str1[i+j]!=str2[j]){
                chk=false;
                break;
            } 
            chk=true;
        }
        if(chk==true) return 1;
    }
    return 2;
}

이런식으로 수정해서 제출하니 정상적으로 동작하였다 

결국에 저 str1.lenght() - str2.length() 부분이 unsigned int 끼리의 연산이니까 해당 부분에서 int overflow가 발생하게 되는것이 문제였다. 그래서 int로 캐스팅해서 제출해보니 문제 없이 동작하였다. 

그대로 반복문에 str1.lenght() 형태로 작성하는건 개별적으로 사용할때는 몰라도 이렇게 사칙연산을 할때, 특히 뺄셈 연산을 할때는 아주 큰 문제가 발생할 수 있는 부분이니까 이렇게 작성해서는 안되겠다. 

아주 간단해보이지만 중요한 부분이라고 생각한다. 이렇게 제출해선 안된다. 

다음부터는 확실하게 새롭게 변수를 int로 설정하고 int에 대입하는 형식으로 프로그램을 작성하도록 하자.