[프로그래머스] 접두사인지 확인하기(c++)

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

프로그래머스

---

---

답

#include <bits/stdc++.h>
using namespace std;


int solution(string my_string, string is_prefix) {
    int result;
    vector<string> prefix;
    
    for(int i=1;i<=my_string.size();i++){
        prefix.push_back(my_string.substr(0,i));
    }
    
    if(find(prefix.begin(),prefix.end(),is_prefix)!=prefix.end()){
        result=1;
    }
    else{
        result=0;
    }
    
    return result;

}

1. 변수

• 'result': 'is_preifx'가 'my_string'의 접두사인지 여부를 저장한다.
  (접두사면 1, 아니면 0)
• 'prefix': 'my_string'의 모든 가능한 접두사를 저장한다.

2. 접두사 생성

• 'for'을 사용하여 'my_string'의 모든 가능한 접두사를 생성한다.
  이를 위해 'substr'을 사용하여 0부터 'i'길이 까지의 부분 문자열을 추출한다.
  ('i'는 1부터 'my_string'의 길이까지 증가한다.)

3. 접두사 확인

• 'find'함수를 사용하여 'prefix' 안에서 'is_prefix' 문자열을 찾는다.
  만약 'is_prefix'가 'prefix' 안에 없다면, 'find'함수는 'prefix.end()'를 반환한다.
• 'if'문을 통해 'find'함수의 반환값이 'prefix.end()'와 다른지 확인한다.
  다르면'is_prefix'는 'my_string'의 접두사이므로 'result'를 1로 한다.
  같으면 'is_prefix'는 접두사가 아니므로  'result'를 0으로 한다.

4. 결과

• 'result' 변수를 반환한다.(1은 접두사,0은 아님)

 

 

참고

'std::find' 함수

• 주로 vector에서 특정 요소를 찾는데 사용한다.
  지전된 범위에서 값을 찾고, 그 값을 가리키는 반복자를 반환한다.
• '<agorithm>' 해더파일에 있다.

find(시작 반복자, 끝 반복자, 찾고자 하는 값);
if(find(prefix.begin(),prefix.end(),is_prefix)!=prefix.end()){

- '시작 반복자'와 '끝 반복자'는 검색할 범위를 지정하고, '찾고자 하는 값'이 찾으려는 요소이다.

  (찾는 값이 있으면 해당 값의 반복자를 반환하고, 찾는 값이 없으면 마지막 반복자 'end()'를 반환한다.)

- 마지막 반복자 'end()'와 다른지를 사용해서 vector안에 찾으려 하는 값이 있는지 확인 할 수 있다. 

 

 

'substr' 함수

• 문자열의 특정 부분을 추출하는데 사용한다.

str.substr(시작 인덱스, 길이);
my_string.substr(0,i)

- '시작 인덱스'는 추출을 시작하는 위치, '길이'는 추출할 문자열의 길이이다.

- 'my_string' 문자열에서 0번째(처음)부터 i만큼 을 추출할 수 있다.

 

 

가능한 모든 접두사를 생성하고 생성된 접두사에 'is_prefix'를 찾고 그에 따라 결과를 반환하는 프로그램이다.

그러나 이렇게 하면 모든 접두사르 생성하고 저장해야 하기 때문에 메모리 사용량이 크고

'find'함수를 사용할때 시간이 많이 소요된다.

 

하지만 이 문제에서는 시간소요와 메모리 사용에 대한 조건이 없었고, 큰 문자열을 담당하지 않기 때문에 이렇게 풀어도 됬었다.

 

좀더 효율적인 방법은 'substr'과 'find'를 사용하지 않고, 

'is_prefix'의 길이만큼 'my_String'의 시작 부분을 직접 비교하는 것이다.

이러면 추가 메모리를 사용하지 않고 접두사가 일치하는지 바로 확인 할 수 있다.

int solution(string my_string, string is_prefix) {
    if(is_prefix.size()>my_string.size()) return 0;

    for(int i=0;i<is_prefix.size();i++){
        if(my_string[i]!=is_prefix[i]) return 0;
    }
    return 1;
}

---

끝