본문 바로가기

HashSet15

[자바] 백준 2015 - 수들의 합 4 (java) 목차 문제 : boj2015 필요 알고리즘 누적 합 (prefix sum), 해시를 사용한 집합과 맵 (hashmap) 누적합과 해시를 사용해 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제에서 A배열에서 1부터 X번까지의 누적합을 f(x)라 해보자. 즉 f(x)는 다음과 같다. 이 때 1 2024. 4. 3.
[자바] 백준 25757 - 임스와 함께하는 미니게임 (java) 문제 : boj25757 필요 알고리즘 개념 해시를 사용한 집합과 맵, 문자열 문자열을 사용해 해싱하는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 Y, F, O에 대해 임스는 무조건 포함되어야 하니 각각 추가로 1, 2, 3명의 인원수가 필요하다. Y에 따른 추가 인원수를 p라고 해보자. 이제 알아야 하는건 '최대 몇 번이나 임스와 함께 게임을 플레이할 수 있는지'와 '임스는 한 번 같이 플레이한 사람과는.. 2022. 10. 24.
[자바] 백준 8975 - PJESMA (java) 문제 : boj8975 필요 알고리즘 개념 해시를 사용한 집합과 맵 해시를 통해 어떠한 문자열이 존재하는지 빠르게 확인이 가능해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 해시에 대해 알고 있다면 문제 파악만 잘 됬다면 어렵지 않게 풀 수 있다. N개의 문자열에 대해, M개의 문자열을 하나씩 입력받다가 N개에서 존재했던 문자열 중 ⌈N/2⌉개가 나온 경우 몇번째인지 출력해주면 된다. 예를들어 예제 입력 1을 보자.. 2022. 9. 13.
[자바] 백준 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.
[자바] 백준 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.
[ABC251] C - Poem Online Judge (AtCoder Beginner Contest 251 in Java) 문제 : abc251_c 만약 공통된 String 부분이 없다고 생각해보자. 그럼 단순히 입력 중 최대 T값이 인덱스를 출력해주면 될 것이다. 다만 이 문제에서는 S를 기준으로 중복된 값이 들어왔다면 해당 값은 무시해줘야 한다. 동일한 String이 들어왔는지 확인하는 가장 간단한 자료구조는 HashSet을 사용하는 것이다. 따라서 HashSet으로 이미 들어온 값이라면 무시하고, 그렇지 않다면 HashSet에 등록하고 최대값인지 체크하면 된다. 코드 : github ... private void solution() throws Exception { int n = nextInt(); HashSet hs = new HashSet(); int max = 0; int maxIdx = 0; for (int i .. 2022. 5. 15.

티스토리툴바