[백준 1515번] 수 이어 쓰기 (C++)

문제링크 : https://www.acmicpc.net/problem/1515

1515번: 수 이어 쓰기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    string s, tmp = " ";
    cin >> s;

    int idx = 0;
    int result = 1; //1부터 차례대로 확인
    bool flag = 1;
    while(flag)
    {
        tmp=to_string(result); //문자열로 변환
        for(int i=0; i<tmp.size(); i++)
        {
            if(s[idx]==tmp[i] && ++idx == s.size()) //문자가 같은지, 같다면 총 길이도 같은지
            {
                cout << result;
                flag = 0;
            }
        }
        result++; //다음 값 체크
    }

    return 0;
}

제목은 수 이어쓰기이나 문자열을 다루는 문제이다.

1부터 차례대로 수를 증가시켜가며 이 값이 입력받은 수와 일치하는지 확인시켜준다.

<예시 : 234092>
result = 1 : s[idx]와 일치하지 않으므로 넘김
result = 2 : s[idx]와 일치하므로 문자열 s의 인덱스를 나타내는 idx 값 증가 (idx = 1, 다음 값 확인)
result = 3 : s[idx]와 일치하므로 문자열 s의 인덱스를 나타내는 idx 값 증가 (idx = 2, 다음 값 확인)
result = 4 : s[idx]와 일치하므로 문자열 s의 인덱스를 나타내는 idx 값 증가 (idx = 3, 다음 값 확인)
result = 5 ~ 9 : s[idx]와 일치하지 않으므로 넘김 (idx = 3)
result = 10 : 뒷부분인 0이 s[idx]와 일치하므로 s의 인덱스를 나타내는 idx 값 증가 (idx = 4, 다음 값 확인)
result = 11 ~ 18 : s[idx]와 일치하지 않으므로 넘김 (idx = 4)
result = 19 : 뒷부분인 9가 s[idx]와 일치하므로 s의 인덱스를 나타내는 idx 값 증가 (idx = 5, 다음 값 확인)
result = 20 ~ 21 : s[idx]와 일치하지 않으므로 넘김 (idx = 5)
ressult = 22 : 뒷부분인 2가 s[idx]와 일치하므로 s의 인덱스를 나타내는 idx 값 증가 (idx = 6)
문자열 S의 사이즈가 idx의 값과 같으므로 (모든 값 탐색 완료했으므로) 현재값 result가 정답

위와 같이 result의 값을 증가시켜나가면서 문자열의 첫부분과 같은 값이 있는지 확인해주고, 같은 부분을 찾았다면 문자열의 인덱스를 한 칸 뒤로 위치시켜서 현재 위치 이후 값을 비교해준다.

 

위를 반복시켜서 idx와 문자열의 길이가 같아 지는 경우에 모든 값을 탐색 완료했다는 것을 의미하므로 탐색이 끝난다.