백준 25192: 인사성 밝은 곰곰이(C언어)

25192번: 인사성 밝은 곰곰이

문제

알고리즘 입문방 오픈 채팅방에서는 새로운 분들이 입장을 할 때마다 곰곰티콘을 사용해 인사를 한다.

이를 본 문자열 킬러 임스는 채팅방의 기록을 수집해 그 중 곰곰티콘이 사용된 횟수를 구해 보기로 했다.

ENTER는 새로운 사람이 채팅방에 입장했음을 나타낸다. 그 외는 채팅을 입력한 유저의 닉네임을 나타낸다.

닉네임은 숫자 또는 영문 대소문자로 구성되어 있다.

새로운 사람이 입장한 이후 처음 채팅을 입력하는 사람은 반드시 곰곰티콘으로 인사를 한다.

그 외의 기록은 곰곰티콘을 쓰지 않은 평범한 채팅 기록이다.

채팅 기록 중 곰곰티콘이 사용된 횟수를 구해보자!

입력

첫 번째 줄에는 채팅방의 기록 수를 나타내는 정수 N 이 주어진다. (1 ≤ N ≤ 100000)

두 번째 줄부터 N 개의 줄에 걸쳐 새로운 사람의 입장을 나타내는 ENTER, 혹은 채팅을 입력한 유저의 닉네임이 문자열로 주어진다. (1≤ 문자열 길이 ≤20)

첫 번째 주어지는 문자열은 무조건 ENTER이다.

출력

채팅 기록 중 곰곰티콘이 사용된 횟수를 출력하시오.

문제풀이

위의 내용을 정리해보면

1. 채팅방의 기록 수를 나타내는 정수 N을 입력받는다.

2. 처음 기록에는 반드시 ENTER을 입력받는다.

3. 다음 기록부터는 ENTER가 나올 때까지 혹은 N개의 정수만큼 입력이 끝났을 경우까지 중복된 이름을

제외하고 개수를 파악하여 출력한다.

 

정리한 바탕으로 일단 처음에 단순히 입력을 받다가 ENTER 혹은 N 개의 입력이 끝났을 경우 처음부터 끝까지 for 문으로

돌리면서 현재 확인하고자 하는 문자열과 같은지 비교하면서 진행을 했었는데 시간 초과가 나와서 방법을 바꿨다.

 

두 번째로 생각한 방법은 ENTER 혹은 N 개의 정수만큼 입력이 끝났을 경우 거기까지의 입력된 값을 병합 정렬을 통해서

문자열들을 순차적으로 정렬해 줬다. 그다음 입력을 받기 전에 정렬된 문자열에서 현재 확인하고자 하는 인덱스의 문자열과

다음 인덱스의 문자열들을 비교해서 같지 않다면 count의 개수를 하나씩 증가시켜서 개수를 세줬다.

최종코드

#include<stdio.h>
#include<string.h>

int n, count, num;
char arr[100000][21];
char sorted[100000][21];
char str[21];

void merge_sort(char a[][21], int m, int mid, int n) {
	int i = m;
	int j = mid + 1;
	int k = m;

	while (i <= mid && j <= n) {
		if (strcmp(a[i], a[j]) <= 0) {
			strcpy(sorted[k], a[i]);
			i++;
		}
		else {
			strcpy(sorted[k], a[j]);
			j++;
		}
		k++;
	}

	if (i > mid) {
		for (int t = j; t <= n; t++) {
			strcpy(sorted[k], a[t]);
			k++;
		}
	}
	else {
		for (int t = i; t <= mid; t++) {
			strcpy(sorted[k], a[t]);
			k++;
		}
	}

	for (int t = m; t <= n; t++) {
		strcpy(a[t], sorted[t]);
	}
	return;
}

void merge(char a[][21], int m, int n) {
	if (m < n) {
		int mid = (m + n) / 2;
		merge(a, m, mid);
		merge(a, mid + 1, n);
		merge_sort(a, m, mid, n);
	}
	return;
}

int main() {
	scanf("%d", &n);
	scanf("%s", str);
	for (int i = 1; i < n; i++) {
		scanf("%s", str);
		if (strcmp(str, "ENTER") != 0) {
			strcpy(arr[num], str);
			num++;
		}
		if (i == n - 1 || strcmp(str, "ENTER") == 0) {
			merge(arr, 0, num - 1);
			for (int j = 1; j <= num; j++) {
				if (strcmp(arr[j - 1], arr[j]) != 0 || j == num) {
					count++;
				}
			}
			num = 0;
		}
	}
	printf("%d", count);
}