[C++] 백준 1235번:학생 번호

문제

이번에는 학생들을 더욱 효율적으로 관리하기 위해 학생마다 고유한 학생 번호를 부여하기로 하였다. 학생 번호는 0부터 9 사이의 숫자로 이루어진 문자열로, 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같다.

학생들의 번호를 부여해 놓고 보니, 김진영 조교는 어쩌면 번호가 지나치게 긴 것은 아닌가 싶은 생각이 들었다. 예를 들어 아래와 같은 7자리의 학생 번호를 보자.

 

이름       번호

오민식  1212345

김형택  1212356

이동호  0033445

 

이처럼 학생 번호를 굳이 7자리로 하지 않고, 뒤에서 세 자리만을 추려서 남겨 놓아도 모든 학생들의 학생 번호를 서로 다르게 만들 수 있다.

 

이름      번호

오민식   345

김형택   356

이동호   445

 

하지만 세 자리보다 적게 남겨 놓아서는 모든 학생들의 학생 번호를 서로 다르게 만들 수 없다.

학생들의 번호가 주어 졌을 때, 뒤에서 k자리만을 추려서 남겨 놓았을 때 모든 학생들의 학생 번호를 서로 다르게 만들 수 있는 최소의 k를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 학생의 수 N(2≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 학생의 학생 번호가 순서대로 주어진다. 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같으며, 0부터 9 사이의 숫자로 이루어진 문자열이 주어진다. 문자열의 길이는 100보다 작거나 같다.

출력

첫째 줄에 구하고자 하는 가장 작은 k값을 출력한다.

 

풀이

학생 번호를 추리기 위해서는 추려진 학생 번호 모두 달라야 한다. 즉 뒤에서 k만큼의 자리수를 남겼을 때 동일한 학생 번호가 없어야 한다. (만약 같은 번호가 존재한다면 한 자리를 더해줘서 다시 검사해야 한다.)

학생 번호를 뒤부터 추린다고 하였기 때문에 입력 받은 학생 번호를 뒤집어서 저장해주었다.

ex)

123456 → 654321

123455 → 554321

123444 → 444321

그렇기 때문에 앞자리부터 비교하고 모두 다른 번호일 때의 자리수를 출력해주면 된다.

 

코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
int n;
string num;
 
int main() {
    cin >> n;
    vector<string> stdNumber(n);
 
    // 뒤집어서 저장
    for (int i = 0; i < n; i++) {
        cin >> num;
        string s = "";
        for (int j = num.size() - 1; j >= 0; j--) {
            s = s + num[j];
        }
        stdNumber[i] = s;
    }
 
    int size = stdNumber[0].size();
 
    vector<string> tmp(n);
 
    int add = 0;    // 추려야하는 자리
    for (int i = 0; i < n; i++) {
        tmp[i] = stdNumber[i][add];
    }
    add++;
 
    while (true) {
        // 같은 것이 있는지 저장 flag
        bool same = false;
        // 같은것이 있는지 완전 탐색
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                // 같다면 탐색을 종료하고
                if (tmp[i] == tmp[j]) {
                    same = true;
                    break;
                }
            }
        }
        // 한자리 더 추가
        if (same == true) {
            for (int i = 0; i < n; i++) {
                tmp[i] = tmp[i] + (stdNumber[i][add]);
            }
            add++;
        }
        // 모두 같지 않다면 자리수 출력
        else {
            cout << add;
            return 0;
        }
 
    }
}

 

메모

.