백준 알고리즘 16466번: 콘서트 [C++]

문제 출처: https://www.acmicpc.net/problem/16466

16466번: 콘서트

1. 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
	int N;
	cin >> N;

	long long * A = new long long [N];

	for (int i = 0; i < N; i++)
		cin >> A[i];

	sort(A, A + N);
	int answer = 1;
	for (int i = 0; i < N; i++)
	{
		if (answer != A[i]) break;		//다르다면 중지
		for (int j = i + 1; j < N; j++)		//중복된 값 무시
		{
			if (A[i] == A[j]) i = j;
			else break;
		}
		answer++;
	}
	cout << answer;
	delete[] A;
}

(실행)

2. 풀이

해당 문제는 정말 간단하다. 그냥 입력된 값을 정렬을 한 이후에 1부터 순서대로 존재하는지 확인하는 문제이다. 그런데 데이터 케이스에는 중복된 값이 존재하기에 중복된 값을 제거하는 과정이 없다면 문제를 틀리게 되므로 그 부분을 알아차리면 쉽게 해결할 수 있을 것이다.

int N;
cin >> N;

int * A = new int [N];

for (int i = 0; i < N; i++)
	cin >> A[i];

우선 N을 입력받고 N의 크기만큼 A를 할당해준다. 그리고 반복문을 이용하여 배열의 값을 입력합니다.

sort(A, A + N);
int answer = 1;
for (int i = 0; i < N; i++)
{
	if (answer != A[i]) break;		//다르다면 중지
	for (int j = i + 1; j < N; j++)		//중복된 값 무시
	{
		if (A[i] == A[j]) i = j;
		else break;
	}
	answer++;
}

sort를 이용하여 배열을 정렬하고 answer를 이용하여 배열의 값이 1부터 순서대로 저장되었는지 확인해주는데 다르다면 반복문을 종료하지만 아니라면 또 다시 반복문을 이용하여 같은 값이 있는지 확인을 하고 있다면 다른값이 나올 때까지 반복해줍니다. 그리고 answer의 값을 1증가시켜서 다른 값이 나올 때까지 반복을 진행합니다.

cout << answer;
delete[] A;

반복문이 모두 종료되면 answer를 출력해주고 동적할당을 해제해줍니다.

3. 느낀점

데이터 케이스에 중복된 값이 저장될 거라고는 생각을 하지 못해서 생각보다 시간이 걸려서 조금 아쉬웠습니다.