HashSet15 [자바] 백준 14425 - 문자열 집합 (boj java) 문제 : boj14425 해쉬에 대한 개념을 알고, HashSet 자료구조를 알고 있다면 간단하게 풀 수 있다. N개를 HashSet에 넣고, M개를 입력받으면서 HashSet에 존재하는지 확인하면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashSet; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTok.. 2022. 5. 13. 백준 1940 자바 - 주몽 (boj 1940 java) 문제 : boj1940 고유한 번호를 a라고 할 때, 결국 알아야 하는 것은 n개의 a에 대해 현재 보고 있는 a값을 기준으로 m-a가 n개 중에 존재하는지만 알 수 있으면 된다. 따라서 HashSet을 사용하면 쉽게 풀 수 있다. 이 때, 만약 '고유한 번호'가 아니라 중복되는 것이었다면 HashMap으로 개수도 체크해야 했을 것이다. 로직은 그럼 다음과 같다. A. N개를 입력받으면서 HashSet에 넣는다. B. N개를 순회하면서 m-a가 HashSet에 존재하는지 확인한다. 존재한다면 카운트를 +1 시킨다. C. 이 때 m이 짝수이고 m/2인 값이 존재한다면 m-a == a 이므로 이 경우는 빼야하니 카운트 -1 시킨다. D. 최종적으로 중복된 경우를 빼기 위해 카운트/2를 해서 출력해주면 된다... 2022. 4. 19. 백준 19585 자바 - 전설 (boj 19585 java) 문제 : boj19585 다른 의미로 전설이었다. 보통은 포기하고 넘어갔을텐데 이론상(?) 가능할 것 같아서 계속 하다보니 오기가 생겨서 끝까지 해보기로 했었다 ㅋㅋㅋ 풀고보니 자바한정으로 통과하기 어려운 문제였다. 시간초과난 로직으로 다른 언어론 통과가 되더라 ㅠ 시도한 내용들은 이하와 같다. 1. 이왜플(이게 왜 플래)을 외치며 모든쌍을 HashSet에 넣었다가 당연히 시간초과(이하 TLE). -> 색상과 닉네임이 둘 다 최대 4000개씩 이므로 모든 쌍을 만들면 O(4000^2) 이라고 대충 생각해서 해봤었다. 하지만 String이란 점을 간과했다. String + String이 결국 두 문자열 길이의 합 만큼 시간복잡도가 들어가므로, 실제론 O(4000^2 * (1000+1000)) 이다. Str.. 2022. 4. 15. 백준 5568 자바 - 카드 놓기 (BOJ 5568 JAVA) 문제 : boj5568 우선 항상 문제를 풀 때, 그냥 무지성으로 모든 경우를 봐도 주어진 시간, 메모리 내에 가능한지부터 확인하는 습관을 들이는게 좋다. 이 문제의 경우엔 최대 10개 중 최대 4장을 선택하면 되므로, 최대 10C4번만 보면 된다. 따라서 그냥 모든 경우를 보면 된다! -> 모든 경우를 확인하려면 k번의 반복문이 필요하다. 이렇게 반복문의 개수가 고정되지 않을 때는 재귀로 짜면 매우 편하다. 재귀를 쓰기 싫다면 스택을 쓰면 재귀로 짠 것과 동일하게 짤 수 있다. 그럼 '만들 수 있는 정수'의 종류는 어떻게 알 수 있을까? 마찬가지로 제한 조건을 확인해보면서 생각해보면 된다. 우선 1부터 99까지의 정수이므로 0이 없어서, 숫자 앞에 0이 오는 경우는 무시해도 됨을 알 수 있다. 그리고 .. 2022. 3. 16. 백준 13211 자바 - Passport Checking (BOJ 13211 JAVA) 문제 : boj13211 hashset의 개념을 안다면 바로 풀 수 있다. 혹시 모를 경우 brute force로는 O(NM) 이므로 풀 수 없다. 그러니 정렬 후 이분탐색 O(NlogN + MlogN)으로 풀면 된다. 하지만 정렬 후 이분탐색을 아는 사람이 hashset의 개념을 모를리 없으므로 사실상 해시로 풀면 되는 문제이다. 이 경우 O(N+M) 이 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashSet; public class Main { private void solution() throws Exception { BufferedReader br = new Buf.. 2022. 2. 10. 이전 1 2 다음
