[백준] 1235 - 학생 번호

1. 문제

1235번: 학생 번호

2. 개요

학생의 수 N과 각각의 학생 번호가 주어진다.

학생 번호의 뒤에서 K만큼의 수만을 이용해 모든 학생들의 학생 번호를 다르게 만드려고 한다.

이 때 필요한 K의 최솟값을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

Set을 만들어두고 idx를 1부터 시작한다.

각 학생 번호의 뒤에서 idx만큼의 수를 Set에 넣는다.

Set의 크기가 주어진 학생의 수보다 작다면 중복이 있다는 뜻이므로 idx를 1씩 늘려준다.

Set의 크기가 주어진 학생의 수와 같다면 중복이 없이 모두 다르다는 뜻이므로 idx를 출력한다.

3-2. Python

import sys

N = int(sys.stdin.readline())

shortnums = set()

nums = []
for i in range(N):
    nums.append(sys.stdin.readline().rstrip())

idx = 0
while len(shortnums) < N:
    idx += 1
    shortnums.clear()

    for num in nums:
        shortnums.add(num[-idx:])

print(idx)

3-3. C#

namespace boj_1235
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int N = int.Parse(sr.ReadLine());

            HashSet<string> shortnums = new();
            string[] nums = new string[N];

            for (int i = 0; i < N; i++)
                nums[i] = sr.ReadLine().TrimEnd();

            int idx = 0;

            while (shortnums.Count < N)
            {
                shortnums.Clear();
                idx++;

                foreach (string num in nums)
                    shortnums.Add(num[^idx..]);
            }

            sw.WriteLine(idx);
            sw.Close();
        }
    }
}