[Algorithm][String][정올] 1133 : Uniqueness

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

순서

I. 문제
II. 접근
III. 구현

---

I. 문제

N개의 문자열이 주어졌을 때, 동일한 문자열이 존재하는지 판단하는 프로그램을 작성하라.

문자열이란 사이에 공백이 없는 연속된 알파벳 소문자열을 뜻한다.

문자열의 길이는 최소 1글자, 최대 20글자이다.

입력되는 문자열의 개수는 2개 이상 10,000개 이하이다.

입력형식

입력의 첫 번째 줄에는 입력될 문자열의 개수 N이 입력된다. 그 다음 줄에는 N개의 문자열이 공백을 사이에 두고 입력된다. 전제조건을 어긋나는 입력이 들어오는 경우는 없다.

출력형식

입력에서 동일한 문자열이 존재하지 않을 경우는 "unique"를 출력한다.(큰 따옴표 제외) 동일한 문자열이 발생한 경우에는 한 줄에 해당 문자열과, 문자열이 몇 번째로 입력되었는지를 출력해야 하는데, 이 경우 우선 앞에 동일한 문자열이 발견된 문자열을 출력한다.

다음 공백을 출력한 다음, 공백을 사이에 두고 몇 번째로 입력이 되었는지를 출력한다. 동일한 문자열이 존재하는 문자열이 여럿 발견 되었을 경우, 매 줄마다 입력된 순서대로 앞에 나온 형식에 맞춰서 출력을 한다. 자세한 사항은 입력예시를 참고한다.

[입력]
10
alice bob libe lie libe libe alice bob alice alice

[출력]
alice 1 7 9 10
bob 2 8
libe 3 5 6

---

II. 접근

큰 틀은 다음과 같다.

1. 이전에 중복이 있는가?
2.1 중복이 없다면 새롭게 struct 데이터를 생성해 줌 + string 저장
2.2 중복이 있다면 해당 struct 위치만 찾아 Existidx 벡터에 현재 idx 추가시켜줌
3. 출력 시 Existidx의 길이가 1이면 출력 x
4. isUnique 변수를 두어 Unique인지 확인하여 출력

---

이 문제를 접근할 때 고민했던 점은 3가지가 있다.

1. string을 받을 때 이전 데이터와 중복이 있는지 어떻게 알 것인가?
2. 중복이 있다면 해당 string의 위치를 어떻게 쌓아서 저장할 것인가?

내가 생각한 방법은 다음과 같다.

방법 1.
ans2 : 구조체를 둔다. 구조체에는 string과 순서를 저장하는 <vector>를 멤버로 함.
ans1 : 위의 구조체 자체의 vector<struct>를 두어 매 데이터마다 확인함.

#include <string>
#include <vector>
using namespace std;

struct dataStruct{
    string str;
    vector<int> Existidx;
};

vector<dataStruct> stuvec;

stuvec을 매번 쭉 탐색하여 stuvec[i].str과 비교함

 

방법2.
ans1 : Hash map과 위의 구조체를 동시에 이용한다 c++ STL <map>
ans2 : Hash map에 저장된 key value에 구조체 idx를 저장하여 활용

#include <map>
#include <string>

map<string, int> Map;

struct dataStruct {
	string str;
	vector<int> Existidx;
};

dataStruct stuarr[10000+10];
string tempstr;

cin>> tempstr;
Map[tempstr]이 없다면 // 처음이라면
Map[tempstr] = idx; // 해쉬맵에 몇 번째의 string인지 저장(위치x) 
idx++;
stuarr[Map[tempstr]].str =tempstr // 해당 struct array의 string에 저장함.

stuarr[Map[tempstr]].Existidx.push_back(num); // 해당 struct array에 위치 push_back

STL을 사용하지 않은 C스타일의 코딩도 연습해야하는데... 이런문제보면 막막하다...

---

구현

구현 1은 N2 방법이기 때문에 시간이 많이 소요됐고,
구현 2는 hash map을 사용하여 상대적으로 빠른 시간내에 처리되었다.

하지만 vector, array 하드코딩, hash map을 STL이 아닌 C 방식으로 하기에는 둘다 부족하다,,,,,

1. Vector와 Struct만 사용

<hide/>
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct dataStruct {
	string str;
	vector<int> Existidx;
};

int N;
bool isUnique;
vector<dataStruct> stuvec;

void input() {
	isUnique = 1;
	cin >> N;
	
	for (int i = 0; i < N; i++) {
		int alreadyExist = 0;
		string tempstr;
		cin >> tempstr;
		
        // 처음에는 vector에 struct 하나 새로 만들어줌.
        // 만들어주지 않으면 인덱스 접근 못하기 때문 -> 벡터가 아닌 배열로 만들면 필요 x
		if (i == 0) {
			stuvec.push_back(dataStruct{ tempstr });
			stuvec[i].Existidx.push_back(i+1);
			continue;
		}

        // 그 다음부터 struct vector를 탐색하며 중복을 찾음 N2방법
		for (int j = 0; j < int(stuvec.size()); j++) {
			// 기존에 같은게 있다면	
			if (stuvec[j].str == tempstr) {
				stuvec[j].Existidx.push_back(i + 1); // 해당 구조체의 idx만 추가해줌
				isUnique = 0; // Unique하지 않음
				alreadyExist = 1; // 같은것을 찾은경우 플래그
			}
		}

        // 플래그로 판단해서 중복찾지 못한경우 새로 struct 만들어 줌.
		if (!alreadyExist) {
			stuvec.push_back(dataStruct{ tempstr });
			stuvec[int(stuvec.size())-1].Existidx.push_back(i + 1);
		}
	}
}

void print() {
    // 배열 벡터를 쭉 돌며 출력해야함.
	for (int i = 0; i<int(stuvec.size()); i++) {
		// 사이즈가 1이면 출력 안함
        if (stuvec[i].Existidx.size() == 1) 
			continue;
		
        // 사이즈가 2 이상이면 해당 포맷대로 출력
		cout << stuvec[i].str;
		for (int j = 0; j<int(stuvec[i].Existidx.size()); j++)
			printf(" %d", stuvec[i].Existidx[j]);
		printf("\n");
	}

}

int main() {

	input();

	if (!isUnique)
		print();
	else
		printf("unique\n");

	return 0;
}

 

2. Hash Map과 Struct 사용

<hide/>
#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <map>
using namespace std;

int N;
string inputtemp;
map<string, int> Map;

struct Data {
	string str;
	vector<int> callorder;
};


int main() {
	cin >> N;

	Data srtdata[10000+10];
	int isunique{ 1 };
	int mapidx{ 1 };

	for (int i = 0; i < N; i++) {
		
		cin >> inputtemp;
        
		// 만약 처음이라면
        // if문 안에서 Map[inputtemp]가 존재하지 않으면 자동으로 하나 만들어 짐!!
        // 따라서 새로 정의 안해도 되고
		if (!Map[inputtemp]) {
            //아래와 같이 바로 사용해도 된다.
			// mapidx는 string의 등장 순서대로 저장하기 위함
            Map[inputtemp] = mapidx;
            
			mapidx++;
            
            // 새롭게 만들어진 Map을 이용해 struct array에 접근해 string 저장
			srtdata[Map[inputtemp]].str = inputtemp;
		}
		else isunique = 0;
        
        // 모든 경우에 현재 나온 순서 저장함.
		srtdata[Map[inputtemp]].callorder.push_back(i + 1);
	}

	if (isunique == 1)  cout << "unique" << endl;
    
    // 출력부분
	else {
		int idx{ 1 };
		while (idx != mapidx ) {
			if (srtdata[idx].callorder.size() == 1);

			else {
				cout << srtdata[idx].str;
				for (int j = 0; j < int(srtdata[idx].callorder.size()); j++) {
					printf(" %d", srtdata[idx].callorder[j]);
				}
				printf("\n");
			}
			idx++;
		}
	}
	return 0;
}