Lv1_[크기가 작은 부분문자열, C++] 풀이 및 알고리즘 정리 - 프로그래머스

 

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

알고리즘

문자열로 구성된 숫자를 비교를 하는 방법에는

1. 문자열을 숫자로 변환해서 크기 비교
2. 문자열끼리 크기 비교

1. 문자열을 숫자로 변환해서 크기 비교는 문자열을 숫자(정수)로 변환은 stoi, stol, stoll 으로 변환해주면된다.
여기서 주의해야 할 점은 문자열의 길이가 너무 길어서 sto~ 로 변환시에 자료형의 크기를 넘어가는 경우이다.
ex) "interger MAX 2,147,483,647"이지만 string("11111111111") 이라면 stoi로 변환 시 'std::out_of_range'가 발생한다

2. 문자열끼리 크기 비교는 문자열끼리 크기 비교는 숫자크기 비교하듯이 해주면 되기 때문에 편리하다.
하지만 여기에도 주의할 점은 비교하는 string이 길이가 다를 때 원하는 결과가 나오지 않을 수 있습니다.
ex) "12", "9" 를 비교하면 ("12" < "9")의 결과가 나옴.
이유는 사전식 비교를 하기 때문에 맨 앞에 있는 '1', '9'를 우선비교하고 '9'가 더 크기 때문에 뒷부분은 비교하지 않아도 "9"가 더 큰 것으로 판단

그렇기 떄문에 자리수를 동일하게 해서 비교를 해야 정확한 결과를 얻을 수 있습니다.
ex) "12", "09" → ("12" > "09")

 

비교하는 방법을 알았으니 t의 부분 문자열을 p와 크기를 비교하면 된다.
t의 부분 문자열은 substr(시작 인덱스, 크기)을 통해서 추출 후 p와 비교하면 완료

• t = "10203"
• p = "15"

를 풀어 쓰면 "10", "02", "20", "03"이 나오고 "15"와 비교하면 "20"을 제외한 나머지 3개가 작거나 같음을 알 수 있다.

 

 

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int solution(string t, string p) {
    int answer = 0;
    int p_size = p.size();
 
    int zero_pos = -1;
    for(int i = 0; i < t.size()-(p_size-1); i++) {
        string tmp = t.substr(i, p_size);
        if(tmp <= p) {
            answer++;
        }
    }
 
    return answer;
}

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓