[백준] 16466. 콘서트

: 자료구조 - bronze 1

 

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

16466번: 콘서트

 

 

 

정답

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

int compare(const void* a, const void* b) {
	int num1 = *(int*)a;
	int num2 = *(int*)b;
	if (num1 < num2) return -1;
	else if (num1 > num2) return 1;
	else return 0;
}

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

	int* tkt = malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &tkt[i]);
	}
	qsort(tkt, n, sizeof(int),
		compare);

	for (int i = 0; i < n; i++) {
		if (t < tkt[i]) break;
		else {
			for (int j = i + 1; j < n; j++) {
				if (tkt[i] == tkt[j]) i = j;
				else break;
			}
			t++;
		}
	}

	printf("%d", t);

	free(tkt);
	return 0;
}

---

해설

: 입력값을 오름차순으로 정렬한다.

1부터 n개의 정수들이 늘어선 수열에서 입력값 배열에 없는 가장 작은 수를 찾으면 된다.

1부터의 수를 담을 정수 변수를 하나 만들어 반복문으로 인덱스와 함께 증가시켜 나가다가,

일치하지 않는 수가 나오면 그 시점에서의 변수값을 출력한다.

 

 

1. qsort 내장함수를 사용하기 위해 stdlib.h 헤더파일을 가져온다. 오름차순 정렬을 위한 비교함수도 작성한다.

앞의 것이 뒤의 것보다 작다면 -1, 앞의 것이 뒤의 것보다 크다면 1을 반환시킨다. 같으면 0이다.

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

int compare(const void* a, const void* b) {
	int num1 = *(int*)a;
	int num2 = *(int*)b;
	if (num1 < num2) return -1;
	else if (num1 > num2) return 1;
	else return 0;
}

 

2. 입력값으로 정수가 최대 100만 개까지 들어오기 때문에 자료 갯수를 미리 알아낸 뒤 동적 할당을 해주어야 한다.

할당 후 배열에 입력값을 받고, qsort 함수로 오름차순 정렬한다.

배열에 없는 가장 작은 수는 t 변수에 받을 것이다. t는 당연히 1부터 시작한다.

 

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

	int* tkt = malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &tkt[i]);
	}
	qsort(tkt, n, sizeof(int),
		compare);

 

3. 반복문은 간단히 짤 수 있다. t에 있는 수가 tkt 배열의 원소보다 작으면 바로 반복문을 끝내면 된다.

만약 그렇지 않다면 t를 하나 올리고 다시 반복하면 되는데, 이때 주의할 점이 있다.

문제에서 명시되지 않았지만 테스트케이스 중에는 티켓의 목록에 중복되는 수가 있다고 한다.

때문에 반복 때마다 무조건 t를 하나씩 올리면 중복되는 수를 검사할 때도 t가 증가해 버려, 제대로 된 비교가 이루어지지 않게 된다. 안에서 한 번 더 for문을 돌려 어디까지 중복인지 찾은 뒤에, 해당 인덱스로 i값을 바꿔주면 된다.

이 반복문이 종료된 뒤의 t값을 결과로 출력한다.

	for (int i = 0; i < n; i++) {
		if (t < tkt[i]) break;
		else {
			for (int j = i + 1; j < n; j++) {
				if (tkt[i] == tkt[j]) i = j;
				else break;
			}
			t++;
		}
	}

	printf("%d", t);

	free(tkt);
	return 0;
}