[백준 21144] Missing Number (C#, C++) - soo:bak

문제 링크

21144번 - Missing Number

설명

1부터 n까지 숫자를 순서대로 이어붙인 문자열에서 정확히 하나의 숫자가 빠져 있는 상황이 주어질 때, 빠진 숫자를 찾는 문제입니다.

접근법

문자열을 앞에서부터 순서대로 읽어가며 현재 문자열 위치에서 기대되는 숫자가 나타나는지 차례로 탐색합니다.

기대되는 숫자가 나타나면 그 숫자의 길이만큼 문자열의 탐색 위치를 이동하고, 나타나지 않으면 그 숫자가 빠진 것이므로 그 숫자를 출력합니다.

만약, 끝까지 찾지 못하면 마지막 숫자 n이 빠진 것입니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var str = Console.ReadLine()!;

    var pos = 0;
    var missing = -1;
    for (var i = 1; i <= n; i++) {
      var s = i.ToString();
      var ok = pos + s.Length <= str.Length && 
               str.Substring(pos, s.Length) == s;
      if (ok) pos += s.Length;
      else if (missing == -1) missing = i;
    }
    
    if (missing == -1)
      missing = n;

    Console.WriteLine(missing);
  }
}

C++

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

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

  int n; string s;
  cin >> n >> s;

  int pos = 0, missing = -1;
  for (int i = 1; i <= n; i++) {
    string t = to_string(i);
    bool ok = pos + (int)t.size() <= (int)s.size() &&
              s.compare(pos, t.size(), t) == 0;
    if (ok) pos += t.size();
    else if (missing == -1) missing = i;
  }

  if (missing == -1)
    missing = n;
  
  cout << missing << "\n";

  return 0;
}