개발하는 고라니

16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net [DFS] 백준의 다리 놓기(?) 시리즈 문제였나 그거랑 좀 비슷한 것 같다. 나의 문제 접근법은 다음과 같다. 지도를 입력 받으며 '0'인 곳은 Queue에 넣는다. DFS를 이용해 1로 이루어진 덩어리(모양)을 탐색하고, 그 덩어리에 ID(인덱스)를 부여하며, 그 id가 갖는 크기를 Map에 저장한다. Queue에서 하나씩 빼며 상하좌우 인접한 덩어리의 크기를 모두 더한다. (단, 덩어리가 중복되지 않게 하기 위해 Set을 이용했다.) 3번을 반복하..

2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net [이분 탐색 or Set 이용] 카테고리가 이분 탐색으로 되어있지만, 이 문제는 Set을 이용해 값이 있는지 여부를 체크하는 것도 가능하다. Set은 값을 포함하는지에 대한 시간 복잡도가 O(1)이므로 굉장히 빠르다. 다른 컬렉션인 List의 contain()은 O(N)이다. 그래서 이분 탐색을 이용한 풀이와 Set을 이용한 풀이를 해보았다. (+추가) 출력의 횟수가 최대 T * 1,000,000번 할 수 있으므로 System.out.println()을 이용한다면 메..