본문 바로가기

HashMap14

[자바] 백준 2015 - 수들의 합 4 (java) 목차 문제 : boj2015 필요 알고리즘 누적 합 (prefix sum), 해시를 사용한 집합과 맵 (hashmap) 누적합과 해시를 사용해 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제에서 A배열에서 1부터 X번까지의 누적합을 f(x)라 해보자. 즉 f(x)는 다음과 같다. 이 때 1 2024. 4. 3.
[자바] 백준 20920 - 영단어 암기는 괴로워 (java) 목차 문제 : boj20920 필요 알고리즘 정렬, 해시를 사용한 집합과 맵 해당 단어가 몇 번 나왔는지 알기 위해 HashMap을 쓸 수 있어야 한다(다른 방법들도 있긴하다). 그 외에는 문제에서 제시된 방법대로 정렬이 가능한지 묻는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우엔 Word라는 클래스를 만들고 name이 단어, cnt가 해당 단어가 몇 번 나왔는지를 뜻하도록 했다. 우선은 동일한 단어가 .. 2023. 4. 9.
[자바] 프로그래머스 - 호텔 방 배정 (Lv4, Java) 문제 : Programmers-호텔 방 배정 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 해시를 사용한 집합과 맵 자바의 HashMap을 적절하게 사용할 줄 알아야 한다. 근데 이렇게 알고리즘 분류만 봐서는 아마 풀이를 생각하긴 힘들 것 같다. 구현 난이도보다는 아이디어가 필요한 문제이다. 그룹 관련된 개념(유니온 파인드 등)이 있다면 좀 더 쉽게 생각해낼 수 있어보인다. 생각 과정 (오답) * 제가 풀이를 생각하는 과정이고 오답노트처럼 적어놓은 것이므로, 이하 생각 과정에 나온 알고리즘을 모두 몰라도 문제 푸는데 지장 없습니다. 그냥 바로 풀이만 보시려면 아래쪽에 '풀이'로 넘어가시면 됩니다. 아직 선택되지.. 2022. 10. 13.
[자바] 백준 25601 - 자바의 형변환 (java) 문제 : boj25601 필요 알고리즘 개념 그래프 탐색 (bfs, dfs) 그래프 탐색을 할 수 있어야 한다. bfs, dfs 등 해시를 사용한 집합과 맵 String에 대한 간선 표현을 위해 HashMap 등의 자료구조를 사용할 수 있어야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이게 뭔가 복잡해보일 수 있는데, 결국 그냥 그래프 정점과 간선이 주어지고 특정 지점에서 다른 지점으로 그래프 탐색이 가능하냐고 묻.. 2022. 10. 7.
[자바] 백준 16165 - 걸그룹 마스터 준석이 (java) 문제 : boj16165 필요 알고리즘 개념 해시를 사용한 집합과 맵 해시맵에 대해 제대로 이해하고 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제의 두 쿼리를 나눠서 생각해보자. 우선 '1' 쿼리의 경우 멤버의 이름이 주어지면 팀명을 출력해야 한다. 이 부분은 입력을 받으면서 멤버의 이름을 key, 팀명을 value로 하는 해시맵을 구성해두면 각 쿼리마다 O(1)로 출력해줄 수 있다. while.. 2022. 9. 14.
[자바] 백준 5263 - samba (java) 문제 : boj5263 필요 알고리즘 개념 해시를 사용한 집합과 맵 해시를 사용하지 않고 이 문제를 풀려면 값 압축이 필요하다. 그게 더 귀찮기도 하고, 시간복잡도적으로 비효율적이므로 해시를 사용하자. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 입력된 숫자를 '숫자 - 입력된 횟수' 형태로 나눌 수 있어야 이 문제를 풀 수 있다. 예를들어 예제 입력 1의 경우 다음과 같이 나타낼 수 있다. 123 - 6번 1678 - 2.. 2022. 9. 13.
[자바] 백준 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.
[자바] 백준 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.

티스토리툴바