15786번. Send me the money

문제 분석

원본 알파벳과 입력받은 알파벳을 비교하는 문자열 문제이다. 

원본 알파벳이 순서대로 다 있다면 true를, 아니라면 false를 출력한다. 

 

알고리즘 설계

이중포문을 이용해 구현했다. 

원본을 a , 비교할 알파벳을 b로 설정하고 while문으로 b를 입력받는다.

 

a는 for(int i=0; i<n; i++)로 

b는 for(int j=start; j<b.size(); j++)로 코드를 작성했는데

이때 j의 값 start는 초기값을 0으로 설정해주고, 만약 일치하는 알파벳을 찾으면 그 이후부터 비교해줘야하므로

start =j+1로 넣어준다. 

 

시간 복잡도

while문으로 m개 문자열 입력받기 - n번

이중 포문 - n제곱

-> o(n3) 가 나왔다.

실제 코테에서는 쓰기 힘들 코드이다... 

다른 방법으로도 풀어봐야겠다. 

 

코드

#include <iostream>
#include <vector>
using namespace std;
/*
1.원본 알파벳 수n 포스트잇개수m 입력받기
2. 포스트잇 애들 입력받기
3. 가능성 여부 판단
4. 출력하기
*/
int main() {
    //1
    int n, m;
    cin >> n >> m;
       
    //2
    string a, b;    
    cin >> a;

    
    while(m--) {
        int cnt = 0;
        cin >> b;       

        int start = 0; //j값 시작 조절하기
        for (int i = 0; i < n; i++) {
            for (int j = start; j < b.size(); j++) {
                if (a[i] == b[j]) {
                    cnt++;
                    //cout << "J: " << j << " post[j]: " << post[j] << '\n';
                    start = j + 1; //j값 조절 2
                    break;
                }
                if (cnt == n)break;
            }            
        }
  
        if (cnt == a.size()) cout << "true" << '\n';            
        else  cout << "false" << '\n';        
        
    }

    return 0;
}

 

느낀 점

이중포문에서 초기값을 항상 0으로만 쓰는 형태에 익숙했는데

이 문제에서는 한번 확인한 문자는 지나치고, 그 다음 문자부터 또다시 비교해야하므로 이 부분을 start 변수로 구현해본것이 생각의 전환이 되었다. 

시간 복잡도로 따지면 좋은 코드는 아니지만, 혼자 힘으로 풀었다는 것에 의의를 둔다.

find() 함수로도 다시 풀어보고 코드를 추가해봐야겠다.