해시13 백준 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. 백준 2143 자바 - 두 배열의 합 (BOJ 2143 JAVA) 문제 : boj2143 1. 부 배열을 이따 생각하고, 일단 X랑 Y라는 두 배열이 있는데 두 배열의 각 원소를 하나씩 더한 합이 T가 되는 경우부터 생각해보자. 아래와 같은 X, Y 배열이 있다. 1.1 가장 간단히 X[i] + Y[j] 가 T가 되는걸 찾는 방법은 모든 X의 원소에 대해 Y의 모든 경우의 수를 전부 확인해보면 된다. X[0]+Y[0] 확인, X[0]+Y[1] 확인, ... , X[1]+Y[0] 확인, X[1]+Y[1]확인, ... X[2]+Y[3] 확인. 이 경우 X의 개수 * Y의 개수 만큼 봐야 한다. O(XY) 1.2 1.1보다 더 빠르게 할 수 있는 방법이 있다. Y를 정렬한 후 O(YlogY), 각 X에 대해 T-X[i]가 Y에 있는지를 이분탐색으로 찾는 방식이다. 이 경우 .. 2021. 12. 13. 백준 16499 자바 - 동일한 단어 그룹화하기 (BOJ 16499 JAVA) 문제 : https://www.acmicpc.net/problem/16499 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/16400/BOJ_16499.java 만약 N개의 문자열에 대해 알파벳 순서까지 모두 같아야 한다고 하자. 그럼 단순히 HashSet에 입력받은 단어를 넣어보면 알아서 중복값이 제거되니, 해시셋의 크기가 답이 된다. 그럼 순서만 달라야 하는 경우는 어떻게 해야 할까? 여기서 서로의 동일성을 판별할 수 있는 기준은, N개의 단어에 대해 각각 '알파벳 소문자가 몇 번씩 나왔는지' 이다. 알파벳 소문자는 총 26개 이므로, 26칸짜리 배열을 만들어 두고, 입력 받은 각 문자열에 대해 각 character를 보면서 각.. 2021. 10. 26. 이전 1 2 다음
