늘 겸손하게

안녕하세요 besforyou입니다 이번 글에서는 백준 문제 1764 풀이를 소개하겠습니다 문제 풀이 듣도 못한 사람의 이름 N개와 보도 못한 사람의 이름 M개 중 같은 이름의 개수와 같은 이름들을 사전순으로 출력하는 문제이다. N, M 값이 최대 500,000이 될 수 있으므로 순차 탐색 알고리즘을 쓰면 제한 시간안에 풀지 못한다. 그러므로 해쉬 맵을 사용하여 계산 시간을 줄여보자. 풀이 과정 N개의 듣도 못한 사람의 이름을 해쉬 맵에 저장한다. 듣지도, 보지도 못한 사람의 이름을 저장할 ArrayList를 생성한다. M개의 보도 못한 이름을 하나씩 읽으며 해쉬맵에 해당 이름이 존재하는지 탐색한다. 보도 못한 이름이 해쉬 맵 안에 존재하면 ArrayList에 push Collections.sort() 함..

안녕하세요 besforyou입니다 이번 글에서는 백준 문제 10816 숫자 카드 2번 풀이를 소개하겠습니다 문제 해설 N개의 숫자 카드가 먼저 주어지고 M개의 숫자가 주어지는데 N개의 숫자카드 중에서 주어진 숫자와 같은 숫자가 적힌 숫자 카드가 몇 개 있는지 찾는 문제이다. 문제 풀이 단순하게 N개의 숫자 카드를 배열에 저장하고, M개의 숫자가 주어질때마다 배열을 순차 검색해서 같은 숫자의 개수를 세는 방식은 시간 초과가 나온다. N개의 숫자카드가 주어지고 M개의 숫자가 주어질때 순차 검색으로 문제를 푸는 알고리즘의 시간 복잡도는 O(NM)이다. 1