본문 바로가기

해시를 사용한 집합과 맵24

[자바] 백준 2910 - 빈도 정렬 (java) 문제 : boj2910 필요 알고리즘 개념 해시를 사용한 집합과 맵 N은 1000인데 C가 10억이나 된다. 해시를 사용하지 않을꺼라면 값 압축을 해야하는데 그게 더 귀찮으므로 해시를 사용하는게 편하다. 자바로 따지면 HashMap이 필요하다. 정렬 커스텀 정렬이 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 정렬 및 출력에 필요한 정보는 3가지이다. 1. 숫자 2. 해당 숫자가 처음 나온 위치 번호 3. .. 2022. 9. 13.
[자바] 백준 25393 - 교집합 만들기 (java) 문제 : boj25393 필요 알고리즘 개념 이분 탐색 (binary search) 이 문제에서 매개 변수 탐색 알고리즘을 사용하기 위해 기본적으로 알아야 한다. 매개 변수 탐색 (parametric search) 이분 탐색에서 약간 응용된 알고리즘이다. 이분 탐색은 값 A를 찾는 것이고, 매개 변수 탐색은 값 A를 찾을 수도 있고, 그 보다 크거나 작은 수의 위치도 찾을 수 있다. 해시를 사용한 집합과 맵 자바를 기준으로 해시맵 자료구조를 알고 사용할 줄 알아야 한다. 애드 혹 애드 혹 문제이다. 이게 뭐냐면 그냥 아이디어 상품같은거라고 생각하면 된다. 보통 정형화된 방법으로 풀리지 않고 아이디어가 필요한 문제에 태그로 붙곤한다. 어찌보면 그리디에 가깝다. 이게 태그에 달려있다고 그걸보고 풀 수 있는건.. 2022. 8. 10.
[자바] 백준 24524 - 아름다운 문자열 (boj java) 문제 : boj24524 'S 에서의 순서대로 이어 붙여' 부분이 가장 중요하다. 예제 입력 2번처럼 순서가 안맞으면 카운팅을 하면 안된다. 그럼 이걸 어떻게 알 수 있을까? 이하의 말로 설명한 로직을 생각해보자. 1. s의 각 문자열의 문자(character)를 처음부터 순서대로 확인하면서.. 2. 각 문자가 t에 존재하는 문자가 아니라면 무시한다. 3. 현재 s에서 보고 있는 문자를 c라고 하자. t에서 c가 나온 위치 직전의 문자를 bf라고 하자. 예를들어 c가 'a'이고, t가 "bac"라면 bf는 'b'이다. 이제 여기가 중요하다. 현재까지 s에서 나온 각 문자의 횟수를 cnt[] 라고 하자. 즉 c가 현재까지 나온 횟수는 cnt[c]이다. 이 때, cnt[c] >= cnt[bf] 라면, 현재 .. 2022. 7. 24.
[자바] 백준 18114 - 블랙 프라이데이 (boj java) 문제 : boj18114 1. 한 개만 선택해서 C가 되는 경우 (코드 19~22line 참고) 이 경우는 간단하다. N개를 입력받으면서 해당 값이 C인 경우를 찾으면 된다. O(N) 2. 두 개를 선택해서 C가 되는 경우 (코드 24~31line 참고) 이 경우도 어렵지 않다. 미리 N개를 입력받으면서 배열에도 기록해두고, HashSet에도 기록을 해둔다고 해보자. 이후 배열을 순회하면서 현재 보고 있는 값이 A라고 할 때, HashSet에 C-A가 존재하는지만 확인해주면 된다. 주의점은 A != C-A 여야 한다(동일한 물건을 두 개 고르면 안되고, 모든 물건은 무게가 다르므로 A와 C-A가 동일할 수 없다). O(2N) 3. 세 개를 선택해서 C가 되는 경우 (코드 32~41line 참고) 이 경우.. 2022. 7. 21.
[자바] 백준 11101 - 꿍의 여친 만들기 (boj java) 문제 : boj11101 문자열 파싱문제이다. 로직을 다음과 같이 나눠보자. 설명은 이하의 예제 입력 1의 테스트케이스 2를 기준으로 하겠다. 1 ab:13,b:17,cab:21 ab&b|b&cab 1. 각 테스트케이스의 첫줄을 받아 문자열을 key, 시간을 value로 하는 Map 형태로 만든다. -> ':'와 ','을 기준으로 StringTokenizer로 문자열을 나누게 되면 ab, 13, b, 17, cab, 21이 순서대로 들어가 있게될 것이다. 따라서 순서대로 {ab:13, b:17, cab:21}의 Map 형태로 만들어줄 수 있다. 이후 맵에서 쉽게 "ab"의 시간을 알 수 있다. 2. 각 테스트케이스의 둘째줄을 받아 '|' 을 기준으로 나눈다. -> 'ab&b'와 'b&cab'로 나뉠 것이.. 2022. 6. 30.
[자바] 백준 21939 - 문제 추천 시스템 Version 1 (boj java) 문제 : boj21939 우선 한글적으로 좀 해맬만한 부분이 있어서 그것부터 써보겠다(제가 그래서 틀렸었단 얘깁니다 ㅠ). add의 '(추천 문제 리스트에 없는 문제 번호 P만 입력으로 주어진다. 이전에 추천 문제 리스트에 있던 문제 번호가 다른 난이도로 다시 들어 올 수 있다.)' 라는 설명과 solved의 '(추천 문제 리스트에 있는 문제 번호 P만 입력으로 주어진다.)' 라는 설명 때문이었다. 결론적으로 '추천 문제 리스트'는 처음 N개의 입력만을 뜻한다. 그리고 '이전에 추천 문제 리스트에 있던 문제 번호'라는 말은 즉, N개에 존재했었으나 solved로 제거된 경우엔 add로 동일한 번호가 들어올 수 있다는 말이었다. 마찬가지로 solved의 설명 또한 해석하자면 결국 N개에 존재했던 녀석들만 .. 2022. 5. 25.
[ABC252] B - Takahashi's Failure (AtCoder Beginner Contest 252 in Java) 문제 : abc252_b N개의 입력값 중 가장 큰 수를 제외한 데이터는 의미가 없다. 결국, N개의 입력값 중 가장 큰 수의 인덱스들이 K개의 입력값 중에 포함된다면 Yes, 아니라면 No를 출력해주면 되는 문제이다. 따라서 내 경우엔 N개를 입력받으면서 max 값을 찾는다. 이 때 새로운 max값이 나타난다면 HashSet을 초기화하고, max값과 동일한값이 나타날 시 HashSet에 추가하는 식으로 진행했다. 이후 K개를 입력받으면서 HashSet에 있는지만 판단해줬다. 코드 : github ... private void solution() throws Exception { int n = nextInt(); int k = nextInt(); HashSet hs = new HashSet(); int .. 2022. 5. 22.
[자바] 백준 1897 - 토달기 (boj java) 문제 : boj1897 문제에서 제시된 로직대로 진행한다면, 항상 L 길이의 단어는 L+1 길이의 단어가 된다. 또한 이 때, L 길이의 단어에 있는 각 문자의 순서는 L+1 길이의 단어에서 나타나는 문자의 순서와 동일하면서, 딱 하나의 문자만 추가될 것이다. 그렇다면 현재 L길이의 단어를 보고 있을 때, L+1 길이의 단어들 중 이동 가능한 문자로 진행을 하는걸 더이상 진행할 수 없을때까지 해보면 될 것이다. 즉, 그렇게 안생겼지만 bfs나 dfs로 풀면 된다. 간선은 [L 길이의 문자 A] -> [A와 문자 순서까지 생각했을 때, 1개의 문자만 추가된 문자 B] 와 같이 생성하면 될 것이다. 미리 입력을 받으면서 글자의 길이에 따라 나누어두면 훨씬 효율적으로 진행할 수 있다. 또한 String이므로 .. 2022. 5. 20.
[자바] 백준 25192 - 인사성 밝은 곰곰이 (boj java) 문제 : boj25192 'ENTER'가 나온 후 새로 나온 String의 수를 세면 된다. 이 때, ENTER가 나오면 '새로 나온'이 리셋된다고 생각하면 된다. 즉, ENTER A ENTER A 라면 A는 중복이지만 ENTER일 때 초기화됬으므로 2가 답이 된다. 반면에 ENTER A A 라면 A가 중복되므로 1이 답이 된다. 따라서 필요한건 빠른 시간 내에 String이 중복되었는지 확인할 수 있는 자료구조 혹은 알고리즘이다. HashSet이 딱이므로 HashSet을 사용해서 짜주면 된다. 코드 : github ... private void solution() throws Exception { int n = nextInt(); int cnt = 0; HashSet hs = new HashSet();.. 2022. 5. 16.
[자바] 백준 14426 - 접두사 찾기 (boj java) 문제 : boj14426 정해는 대놓고 Trie 쓰라고 낸 거 같은 문제이다. 하지만 N, M, 문자열의 길이가 애매하게 적고 메모리가 상당히 많다. 그래서 밑져야 본전이니 메모리를 많-이 써서 한번 해보고 통과하면 통과되는거고, 안되면 Trie 쓰려고 했는데 이렇게 썼단 이유는 됬다는 그런 얘기이다. 일단 단순히 브루트포스로 풀려고 하면 O(500xNxM) 이므로 불가하다. 하지만 메모리를 더 써서, 미리 N개에 대해 접두사 HashSet을 만들어두면 어떨까? 이 경우 String이라 hash function에 다소 부하는 걸리겠지만, 대강 O(1)이라고 치면 O(500N + M) 으로 가능하다. hash function의 부하를 생각해도 대강 통과는 될 것 같아서 해봤다. 추가로 약간이라도 hash .. 2022. 5. 16.