[정올] Uniqueness

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=413&sca=99 

JUNGOL

문제부터 간단하게 설명하면, 

 

N개의 문자열이 주어졌을 때, 동일한 문자열이 존재하는지 판단하는 프로그램을 작성해야 합니다. 만약 전부 다른 문자열이라면, unique를 출력하고, 아닌 경우에는 중복되는 문자열들에 대해서 등장한 번째를 출력해야 합니다.

 

실제로 문제를 한번 읽어보는 것을 추천합니다. 

 

<Solution>

map등의 자료구조를 이용하면 간단하게 해결할 수 있습니다.

 

만약 사용하지 않는다면, 

앞에서 부터 하나씩 보면서, used를 체킹하는 방식을 이용하면 됩니다. 

alice bob libe lie libe libe alice bob alice alice 

위의 예시에서는 처음 alice를 탐색할 때, 

used array의 index 1, 7, 9, 10이 체킹될 것을 알 수 있습니다. 

 

다음으로, bob을 탐색하고, libe를 탐색하고 이렇게 순차적으로 진행하면 됩니다. 이 때, 7번째 alice를 탐색하는 과정에서는 이미 alice는 used로 마킹되어 있으므로 패스하는 과정을 거치면 됩니다.

 

실제 구현은 아래와 같습니다. 

#include <iostream>
#include <string.h>
 
using namespace std;
 
int N;
char S[10000+10][20+10];
int used[10000+10];
void InputData(){
    cin >> N;
    for (int i=1; i<=N; i++){
        cin >> S[i];
    }
}
 
void solve(){
    int unique=1;
    int first = 0;
    for(int i = 1; i<N; i++){
        first = 0;
        if(used[i]) continue;
        for(int j = i+1; j<=N; j++){
            int r= strcmp(S[i], S[j]);
            if(r != 0) continue;
            // if 0 same
            unique = 0;
            used[j] = 1;
            if(first ==0){
                cout << S[i] << " " << i << " " << j;
                first =1 ;
            }
            else{
                cout << " " << j;
            }
             
 
        }
        if(first == 1){
            cout << "\n";
        } 
 
    }
    if(unique)cout << "unique\n";
 
 
}
 
int main(){
    InputData();
    solve();

    return 0;
}