[백준] 1764. 듣보잡

: 자료구조 - silver 4

 

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

1764번: 듣보잡

 

 

정답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct list {
	char name[21];
};

struct list list1[1000000]; 
struct list list2[500000]; 

int compare(const void* a, const void* b) {
	return (strcmp((char*)a, (char*)b));
} 

int main() {
	int n, m, t;
	scanf("%d %d", &n, &m);
	t = n + m;

	for (int i = 0; i < t; i++) {
		gets(list1[i].name);
	}
	qsort(list1, t,
		sizeof(list1[0]), compare);

	int count = 0; 

	for (int i = 0; i < t; i++) {
		if (strcmp(list1[i].name, list1[i + 1].name) == 0) {
			strcpy(list2[count].name, list1[i].name);
			count++;
			i++; 
		}
	}

	printf("%d\n", count); 
	for (int i = 0; i < count; i++) {
		puts(list2[i].name);
	}
	
	return 0;
}

 

---

해설

1. 듣도 못한 사람과 보도 못한 사람의 이름을 100만 칸짜리 하나의 배열에 함께 담아 알파벳순으로 정렬한다.

2. 정렬 시 중복되는 문자열은 함께 붙게 되므로, 반복문을 통해 중복되는 문자열을 찾아내 별도의 리스트에 복사한다.

3. 복사한 중복 리스트를 출력한다.

(원래의 배열이 알파벳순으로 정렬되어 있었으므로 이 배열도 자연히 정렬된 순서대로 원소를 담게 될 것이다.)

 

 

1. stdio.h, string.h, stdlib.h 세 가지의 헤더파일을 다운받는다.

각각 표준 입출력, 문자열 복사와 비교, 정렬을 위한 qsort 내장함수를 사용하기 위함이다.

문자열은 정렬을 위해 구조체로 만들어 놓는다. 이 구조체로 배열을 두 개 선언한다.

100만 칸짜리 배열은 입력값을 담고 정렬하는 배열, 50만 칸짜리 배열은 중복되는 것을 담는 배열이다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct list {
	char name[21];
}; //명단 한 칸의 자료형 (최대 20자)
//char*형으로 선언하면 오류가 남

struct list list1[1000000]; //입력값을 담는 리스트
struct list list2[500000]; //중복되는 것을 담는 리스트

 

 

2. qsort 내장함수에 사용할 비교함수이다.

strcmp는 두 문자열이 같으면 0, 다르면 알파벳순으로 비교한 결과를 1 또는 -1로 반환하므로

이 함수의 리턴값을 이용해 알파벳순 정렬을 할 수 있다.

int compare(const void* a, const void* b) {
	return (strcmp((char*)a, (char*)b));
} //정렬을 위한 비교함수

 

3. 입력값으로 받을 두 목록의 원소갯수를 각각 받은 뒤 둘을 합하여 t에 따로 저장한다.

그리고 t만큼의 원소를 list1에 통합하여 받는다.

이후 qsort를 이용해 입력값을 사전순으로 정렬한다.

int main() {
	int n, m, t;
	scanf("%d %d", &n, &m);
	t = n + m;

	for (int i = 0; i < t; i++) {
		gets(list1[i].name);
	} //n개와 m개의 이름을 같은 리스트에 입력

	qsort(list1, t,
		sizeof(list1[0]), compare);
	//퀵 정렬 (정렬할 배열, 자료갯수, 자료크기, 비교함수)

 

4. 중복된 문자열을 복사할 리스트의 인덱스로 사용할 변수를 0으로 초기화시킨다.

그리고 반복문을 돌려 중복을 찾아낸다. i번째 이름과 i+1번째 이름이 같다면 해당 문자열을 list2로 복사하고,

list2 배열의 인덱스를 하나 증가, i도 하나 증가(다음 문자열은 검사할 필요 없으므로) 시키면 된다.

	int count = 0; //list2 배열의 인덱스

	for (int i = 0; i < t; i++) {
		if (strcmp(list1[i].name, list1[i + 1].name) == 0) {
			//정렬된 명단의 다음 이름이 현재 이름과 같다면
			strcpy(list2[count].name, list1[i].name);
			count++; //list2 배열은 다음 인덱스로 넘기기
			i++; //list1 배열의 다음 원소는 동일하므로 패스
		}
	}

 

 

5. 이후 count 변수로 센 중복 리스트의 원소 수와, 해당 리스트에 담긴 모든 원소를 출력하면 된다.

	printf("%d\n", count); //중복 리스트의 원소수
	for (int i = 0; i < count; i++) {
		puts(list2[i].name);
		//중복 리스트의 원소
	}
	
	return 0;
}