[C++] 백준 알고리즘 1235 학생 번호

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

1235번: 학생 번호

반례를 찾지 못해서 시간이 오래걸린 문제..

정작 반례를 찾은 다음에는 금세 구현할 수 있었다..

 

잘못된 접근)

처음에는 어떻게 접근을 했냐면,

첫번째 문자열이 12345이고

두번째 문자열이 56789

세번째 문자열이 00000 이라면

 

첫번째 문자열을 잘라내어 (12345를 1, 또는 12, 또는 123... 과 같이 잘랐었음)

두번째 문자열의 부분 문자열과 같은지..

세번째 문자열의 부분 문자열과 같은지..

비교 했다.

 

생각한대로라면, 문자열이 같으면 비교를 멈추고 더 긴 부분 문자열끼리 비교하고, 문자열이 모두 다르면 출력~ 하려고 했는데

첫번째 문자열과 두번째 문자열이 다르고

첫번째 문자열과 세번째 문자열이 달라도

 

두번째 문자열과 세번째 문자열이 같을 수 있었다.

급하게 풀려고 해서 그런지 이런 당연한 반례가 안떠올랐다.

 

밥을 든든히 먹고 다시 생각해보니 접근 방법이 틀렸다는 것을 깨달았다.

 

올바른 접근)

길이가 i인 (인덱스가 0부터 시작하는) 모든 부분 문자열들이 달라야한다.

그렇다면 길이가 i인 부문 문자열을 추출해냈을 때, 이 부분 문자열들끼리 중복되는게 없으면 된다!

나는 vector를 애용하는데

출처 - 네이버 웹툰, 좀비딸

하하. 가벼운 조크.

여튼 애용하는 vector는 중복인 원소도 다 저장한다.

하지만 set은 중복된 원소를 저장하지 않는다.

찾아보니까 multiset은 중복을 허용한다고 한다. 써보진않았다 ㅎ

 

또한, set은 내부적으로 이진탐색트리 형태로 저장하기 때문에 늘 정렬된 상태로 있는다고 한다.

 

여튼.. 그래서 부분 문자열이 모두 다르면 set에 저장된 데이터 갯수가 n과 같을 것이지 않은가?

요런 원리를 이용해보았다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int main(){
    int n, ans;
    cin>>n;
    string s;
    vector<string>students(n);
    for(int i=0; i<n; i++){
        cin>>s;
        reverse(s.begin(), s.end());
        students[i]=s;
    }
    vector<pair<string, int>>check;
    // 놓친 반례 : 1번째 문자열과 2, 3, ... n 번째 문자열을 비교했는데 이 경우
    // 1번 문자열과 i와 다르고 j와도 다를 수도 있지만, i와 j가 같은 경우도 있다.
    for(int i=1; i<=students[0].length(); i++){
        //set에는 중복저장이 안됨
        //따라서 길이가 n인 문자열이 모두 겹치지 않는다면 n이 set의 size와 같을것이다 =>이걸 만족하는 길이 n을 찾자!
        //n보다 set의 size가 작으면, 중복 문자열이 있어서 저장되지 않음을 의미
        set<string>s;
        for(int k=0; k<n; k++){
            s.insert(students[k].substr(0,i));
        }
        if(s.size()==n){
            ans=i;
            break;
        }
    }
    cout<<ans;
}