반응형
문제
https://www.acmicpc.net/problem/10815
풀이
각 수가 적힌 숫자 카드를 상근이가 가지고 있다는 것은 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)$ 이므로 통과가 가능할 것입니다.
반응형
'PS > 백준' 카테고리의 다른 글
[BOJ] 백준 1620 나는야 포켓몬 마스터 이다솜 (Swift) (0) | 2023.03.14 |
---|---|
[BOJ] 백준 11425 문자열 집합 (Swift) (0) | 2023.03.14 |
[BOJ] 백준 1436 영화감독 숌 (Swift) (0) | 2023.03.13 |
[BOJ] 백준 1018 체스판 다시 칠하기 (Swift) (1) | 2023.03.13 |
[BOJ] 백준 7568 덩치 (Swift) (1) | 2023.03.13 |