[백준 2154] 수 이어 쓰기 3 (C#, C++) - soo:bak

문제 링크

2154번 - 수 이어 쓰기 3

설명

자연수 N이 주어지는 상황에서, N (1 ≤ N ≤ 100,000)이 주어질 때, 1부터 N까지의 수를 이어쓴 문자열에서 N이 가장 처음 나타나는 위치를 구하는 문제입니다.

예를 들어 N = 12라면 문자열은 “123456789101112”가 됩니다. 이 문자열에서 “12”가 처음 나타나는 위치는 13번째입니다. 위치는 1부터 시작하는 1-index로 출력합니다.

N이 최대 100,000이므로 전체 문자열의 길이는 약 500,000자 정도로 직접 생성해도 충분합니다.

접근법

1부터 N까지의 수를 순서대로 이어붙여 문자열을 만든 후, N이 처음 나타나는 위치를 찾습니다.

먼저 StringBuilder나 문자열 변수를 사용하여 1부터 N까지 각 수를 문자열로 변환하여 순서대로 이어붙입니다. 반복문으로 1부터 N까지 순회하면서 각 수를 문자열에 추가합니다.

이후, 완성된 문자열에서 N을 문자열로 변환한 값을 찾습니다. 문자열 검색 함수(IndexOf, find)를 사용하면 처음 나타나는 위치의 인덱스를 얻을 수 있습니다. 이 인덱스는 0부터 시작하므로 1을 더해 1-index로 변환하여 출력합니다.

예를 들어, N = 11인 경우:

문자열은 “1234567891011”이 됩니다. “11”을 찾으면 인덱스 12(0-based)에서 처음 나타나므로, 1을 더해 13을 출력합니다. “1”로 시작하는 부분이 여러 곳에 있지만, “11” 전체가 일치하는 첫 위치는 12입니다.

각 수를 이어붙이는 과정은 O(N log N)입니다. 각 수의 자릿수가 log₁₀ i이기 때문입니다. 문자열 검색은 O(문자열 길이)이므로 전체 시간 복잡도는 O(N log N)입니다.

---

Code

C#

using System;
using System.Text;

namespace Solution {
class Program {
    static void Main(string[] args) {
    int n = int.Parse(Console.ReadLine()!);

      StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= n; i++)
      sb.Append(i);

    string target = n.ToString();
    int idx = sb.ToString().IndexOf(target, StringComparison.Ordinal);
      Console.WriteLine(idx + 1);
    }
  }
}

C++

#include <bits/stdc++.h>

using namespace std;

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

  int n; cin >> n;
  string s;
  for (int i = 1; i <= n; i++)
    s += to_string(i);

  string t = to_string(n);
  size_t pos = s.find(t);
  cout << pos + 1 << "\n";

  return 0;
}