[백준 2391] Sascha (C#, C++) - soo:bak

문제 링크

2391번 - Sascha

설명

발음된 단어와 길이가 같은 사전 단어들 중에서 가장 적은 치환으로 만들 수 있는 단어를 찾는 문제입니다. 동점이면 사전에 먼저 나온 단어가 선택됩니다.

접근법

먼저 발음된 단어와 사전 단어의 길이가 같다는 점을 이용합니다.

다음으로 각 사전 단어를 순서대로 보며 같은 위치의 글자를 비교해 다른 개수를 셉니다.

그 값이 가장 작은 단어를 갱신하며, 마지막에 선택된 단어를 출력합니다.

---

Code

C#

using System;
using System.Text;

class Program {
  static void Main() {
    var parts = Console.In.ReadToEnd().Split();
    var idx = 0;
    var t = int.Parse(parts[idx++]);
    var sb = new StringBuilder();

    for (var caseNum = 0; caseNum < t; caseNum++) {
      var spoken = parts[idx++];
      var w = int.Parse(parts[idx++]);

      var bestWord = "";
      var best = int.MaxValue;

      for (var i = 0; i < w; i++) {
        var word = parts[idx++];
        var diff = 0;
        for (var j = 0; j < spoken.Length; j++) {
          if (spoken[j] != word[j]) {
            diff++;
            if (diff >= best) break;
          }
        }

        if (diff < best) {
          best = diff;
          bestWord = word;
        }
      }

      sb.AppendLine(bestWord);
    }

    Console.Write(sb);
  }
}

C++

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

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

  int t; cin >> t;

  for (int caseNum = 0; caseNum < t; caseNum++) {
    string spoken; cin >> spoken;
    int w; cin >> w;

    string bestWord = "";
    int best = 1e9;

    for (int i = 0; i < w; i++) {
      string word; cin >> word;
      int diff = 0;
      for (int j = 0; j < (int)spoken.size(); j++) {
        if (spoken[j] != word[j]) {
          diff++;
          if (diff >= best) break;
        }
      }

      if (diff < best) {
        best = diff;
        bestWord = word;
      }
    }

    cout << bestWord << "\n";
  }

  return 0;
}