해시를 사용한 집합과 맵24 [자바] 백준 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. 백준 3022 자바 - PRASE (BOJ 3022 JAVA) 문제 : boj3022 반복 로직만 잘 세우면 간단하게 풀 수 있다. 주의할 부분은 'If at any point a child takes a piece of food, and that child had already taken more food than the other children all together (not including the new piece of food),'에서 not including the new piece of food 부분이다. 즉, 현재 아이가 누군지는 알아야하지만 현재 집은것에 대해서는 카운티앟지 않은채로 수만 확인해야 한다. 따라서 현재까지 나온 아이의 총 수를 cnt, 현재 아이가 나왔던 횟수를 cc[아이이름] 이라고 해보자. 그럼 만약 현재 아이의 이름이 A라고 할.. 2022. 3. 14. 이전 1 2 3 다음
