본문 바로가기

해시맵6

[자바] 프로그래머스 - 호텔 방 배정 (Lv4, Java) 문제 : Programmers-호텔 방 배정 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 해시를 사용한 집합과 맵 자바의 HashMap을 적절하게 사용할 줄 알아야 한다. 근데 이렇게 알고리즘 분류만 봐서는 아마 풀이를 생각하긴 힘들 것 같다. 구현 난이도보다는 아이디어가 필요한 문제이다. 그룹 관련된 개념(유니온 파인드 등)이 있다면 좀 더 쉽게 생각해낼 수 있어보인다. 생각 과정 (오답) * 제가 풀이를 생각하는 과정이고 오답노트처럼 적어놓은 것이므로, 이하 생각 과정에 나온 알고리즘을 모두 몰라도 문제 푸는데 지장 없습니다. 그냥 바로 풀이만 보시려면 아래쪽에 '풀이'로 넘어가시면 됩니다. 아직 선택되지.. 2022. 10. 13.
[자바] 백준 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.
백준 9612 자바 - Maximum Word Frequency (boj 9612 java) 문제 : boj9612 String에 대해 카운팅을 해야 한다. 따라서 HashMap 등을 사용하면 쉽게 계산할 수 있다. 주의점은 동일한 횟수가 존재할 경우, 사전순으로 뒤에 있는걸 택해야 한다. 코드에서 이하의 부분이 해당 역할을 한다. maxStr.compareTo(cur) < 0 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashMap; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in).. 2022. 4. 9.
백준 4351 자바 - Hay Points (BOJ 4351 JAVA) 문제 : boj4351 String으로 되어 있는 문자열과, 해당 항목에 대한 int를 저장할 수 있어야 한다. HashMap을 사용하면 효율적으로 저장하고, 찾을 수 있다. m개의 단어와 숫자를 받아 HashMap에 단어를 key, 숫자를 value로 저장한다. 그리고 n개를 입력받으면서 띄어쓰기를 기준으로 나누어 HashMap에 해당 단어가 있다면 점수를 더해나가면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { private void solution() throws Exception { BufferedReader br = new Bu.. 2022. 2. 19.
백준 20291 자바 - 파일 정리 (BOJ 20291 JAVA) 문제 : boj20291 1. A.B 의 형태로 입력이 주어질 때, 결국 A는 아예 필요없고 B만 보면 된다. 따라서 문자열 파싱을 통해 '.' 뒤의 문자만 빼낼 수 있어야 한다. 2. 확장자에 대한 카운팅이 필요하다. 해시를 사용하는것이 효율적이다. 해시맵을 사용해 key를 확장자로 두고, value를 카운팅으로 하면 된다. 3. 결과를 확장자 이름순으로 출력해야 한다. 해시맵에서 keySet을 빼내서 정렬해도 되겠지만, 애초에 메모리를 좀 더 써서 따로 key값만 가지고 있다면 더 효율적으로 정렬할 수 있다. 내 경우엔 리스트에 새로운 key가 나올 경우 담아두었다. 그리고 리스트를 정렬한 후, 오름차순으로 정렬되어있는 key가 담긴 리스트를 순회하며 key와 value를 얻어 출력해줬다. 코드 : .. 2022. 2. 17.