[백준 1235번] 학생 번호

https://www.acmicpc.net/problem/1235

1235번: 학생 번호

 

📍 문제

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

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

이름번호

오민식	1212345
김형택	1212356
이동호	0033445

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

이름번호

오민식	345
김형택	356
이동호	445

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

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

 

📍 입력

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

---

📍 해결순서 및 주의사항

1. 입력받은 문자열을 뒤집어서 벡터에 넣는다 → vector을 활용하기!!
2. 각문자열별로 0-res 까지 잘라서 set에 넣었다.
3. 셋 자체적으로 이미 같은 원소가 있다면 이를 insert 하지 않는 특성을 이용했다. → 이는 이미 중복값이 있다는 의미
4. 마지막에 입력받은 학생수 == set.size() 가 같다면 결과값 나오게 했고 그게 아니면 중복값이 있는 것이니 res 를 올려줬다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<string> v;
    int n, res=1;
    cin>>n;
    while(n--){
        string str;
        cin>>str;
        reverse(str.begin(),str.end());
        v.push_back(str);
    }
    while(true){
        set<string> s;
        for(int i=0;i<v.size();i++){
            s.insert(v[i].substr(0,res));
        }
        if(s.size()==v.size()) break;
        else res++;
    }
    cout<<res;

    return 0;
}

📍 참고사항

https://blockdmask.tistory.com/70

[C++] vector container 정리 및 사용법