백준 1515번 [수 이어 쓰기](C++) -yes6686- 티스토리

백준 문제 풀이: 1515 [수 이어 쓰기]

---

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

문제 설명:

1부터 차례대로 자연수를 이어 붙였을 때, 주어진 문자열 s가 처음으로 포함되는 최소의 자연수를 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
#include <string>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	string s;
	cin >> s;

	string kk = "1"; // 처음 숫자는 1부터 시작
	int ans = 1; // 최소 자연수를 찾기 위한 변수
	for (int i = 0; i < s.size(); i++) { // 주어진 문자열을 한 글자씩 탐색

		while (true) {
			// 현재 문자열 kk에서 s[i]가 존재하지 않는다면 다음 숫자를 이어붙임
			if (kk.find(s[i]) == string::npos) {
				kk = to_string(ans); // 현재 숫자를 문자열로 변환
				int k = stoi(kk); // 정수로 변환 후 증가
				k++;
				kk = to_string(k); // 다시 문자열로 변환
				ans++;
			}
			else {
				// 마지막 문자일 경우 종료
				if (i == s.size() - 1) break;
				int idx = kk.find(s[i]); // 현재 문자 위치 찾기
				kk = kk.substr(idx + 1); // 찾은 위치 이후의 문자열 유지
				break;
			}
		}
	}
	cout << ans << '\n'; // 최소 자연수 출력
}

예제 입력:

1515

예제 출력:

15

---

코드 설명

• 핵심 알고리즘: 1부터 시작하는 자연수를 차례로 생성하면서 주어진 문자열 s를 부분 문자열로 만들 수 있는지 확인합니다.
• 구현 세부사항:
  • 자연수를 문자열로 변환하여 한 자리씩 s와 비교하면서 매칭을 시도합니다.
  • s의 모든 문자가 차례대로 매칭되었을 때 반복을 종료합니다.
• 시간 복잡도: O(N), 최대 100,000개의 숫자를 비교해야 할 수 있음

---

결과

주어진 문자열이 연속된 자연수들 속에 처음으로 포함되는 최소 숫자를 정확히 계산합니다. 문자열 매칭을 활용한 구현 문제를 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!