[백준 8715] Permutacja (C#, C++) - soo:bak

문제 링크

8715번 - Permutacja

설명

주어진 수열이 1부터 n까지의 수를 정확히 한 번씩 포함하는 순열인지 판별하는 문제입니다.

접근법

순열이 되려면 모든 수가 1 이상 n 이하여야 하고, 같은 수가 두 번 나오면 안 됩니다.

따라서 크기 n + 1의 방문 배열을 두고, 수열을 앞에서부터 보면서 범위를 벗어난 수가 나오거나 이미 나온 수가 다시 나오면 바로 NIE를 출력하면 됩니다.

끝까지 문제가 없으면 1부터 n까지가 정확히 한 번씩 나온 것이므로 TAK를 출력하면 됩니다.

---

Code

C#

using System;
using System.IO;

class FastScanner {
  private readonly Stream _stream = Console.OpenStandardInput();
  private readonly byte[] _buffer = new byte[1 << 16];
  private int _index;
  private int _size;

  private int Read() {
    if (_index >= _size) {
      _size = _stream.Read(_buffer, 0, _buffer.Length);
      _index = 0;
      if (_size == 0)
        return -1;
    }

    return _buffer[_index++];
  }

  public int ReadInt() {
    int c = Read();
    while (c <= 32) {
      c = Read();
    }

    int value = 0;
    while (c > 32) {
      value = value * 10 + (c - '0');
      c = Read();
    }

    return value;
  }
}

class Program {
  static void Main() {
    var fs = new FastScanner();
    int n = fs.ReadInt();
    bool[] seen = new bool[n + 1];

    for (int i = 0; i < n; i++) {
      int value = fs.ReadInt();

      if (value < 1 || value > n || seen[value]) {
        Console.WriteLine("NIE");
        return;
      }

      seen[value] = true;
    }

    Console.WriteLine("TAK");
  }
}

C++

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

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

  int n;
  cin >> n;

  vector<bool> seen(n + 1, false);

  for (int i = 0; i < n; i++) {
    int value;
    cin >> value;

    if (value < 1 || value > n || seen[value]) {
      cout << "NIE\n";
      return 0;
    }

    seen[value] = true;
  }

  cout << "TAK\n";

  return 0;
}