본문 바로가기

PS/백준

[BOJ] 백준 10815 숫자카드 (Swift)

반응형

문제

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

 

10815번: 숫자 카드

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,

www.acmicpc.net

풀이

각 수가 적힌 숫자 카드를 상근이가 가지고 있다는 것은 contains 메서드를 사용해서 확인할 수 있습니다.
Array의 contains는 $O(n)$이지만 Set 자료형의 contains는 $O(1)$ 만큼 소요됩니다.

따라서 상근이가 가지고 있는 숫자 카드를 Set 자료형으로 만들어 준 후,
각 수가 적힌 숫자 카드들을 하나씩 상근이가 가지고 있는지 contains로 확인해주면 됩니다.

contains로 확인을 하는 것이 $O(1)$이고,
최악의 경우에는 contains 연산을 50만번 하게 되므로, 50만번의 연산 만큼의 시간이 소요될 것입니다.

상근이가 갖고 있는 카드를 Set이 아닌 Array로 사용했을 때는
contains가 $O(n)$이고,
최악의 경우에는 contains 연산을 50만번 하게 되므로, $500,000^2 = 250,000,000,000$ 만큼의 시간이 소요될 것입니다.

당연히 시간 초과가 날 것입니다.

소스코드

후기

Set 자료형을 사용하면 쉽게 풀 수 있는 문제입니다.
상근이가 갖고 있는 카드를 정렬하여 이분탐색을 사용해도 최악의 경우에 50만 * $O(logn)$ 이므로 통과가 가능할 것입니다.

반응형