HashMap6 [Kotlin] 백준 6523 : 요세푸스 한 번 더! 문제 링크 : https://www.acmicpc.net/problem/6523문제 해설일종의 구현 문제. 따로 특별한 알고리즘이 필요하진 않다. 문제에서 각 사람들은 두번째에 걸렸을 때 술을 마시게 되고, 누구든 세 번 걸린다면 모두 집에 간다는 내용이 있다. 술을 마시지 않고 집으로 가는 사람의 수를 출력해야 하기 때문에 누군가 두번째 걸렸을 때 술을 마신 사람의 수를 더하고, 세번째 걸린다면 해당 테스트 케이스를 종료하면 된다. 각 사람들이 걸린 횟수를 기록하기 위해 HashMap을 사용한다. 정수배열을 사용해서 기록할 수도 있겠으나, 크기가 최대 10억인 정수배열을 선언하게 되어 어마어마한 메모리를 차지하게 되는 문제가 있어서 사용할 수 없다. 현재 사람의 번호가 \(x\)일 때 다음 사람의 번호.. 2024. 6. 10. [Java] HashMap vs Hashtable(feat. ConcurrentHashMap) 목차 서론 스터디를 진행하던 도중 Hashtable에 대한 이야기가 조금 나왔었다. 사실 이전까진 Hashtable이라는 것이 있다는 것만 알고 Map의 구현체로 대부분 HashMap을, 아주 가끔 TreeMap을 사용했는데, Hashtable은 HashMap과 비슷하게 Key - Value 쌍의 Map 구현체인 것은 동일하지만 세부적인 내용에서 차이가 있는 구조라고 한다. 이 글에서는 HashMap과 Hashtable의 차이에 대해 조금 다뤄보려고 한다. HashMap HashMap은 자바 1.2에서 등장한 Map 인터페이스의 구현체이다. 기본적으로 HashMap은 동기화를 지원하지 않기 때문에 다중 스레드 환경에서는 동시성 이슈가 발생할 수 있다. 이러한 이유로 인해 HashMap에서는 연산 도중 M.. 2023. 3. 27. [Kotlin] 백준 22252 : 정보 상인 호석 문제 링크 22252번: 정보 상인 호석 암흑가의 권력은 주먹과 정보에서 나온다. 주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다. 정보 상인은 정보를 www.acmicpc.net 문제 해설 HashMap과 우선순위 큐를 사용하면 문제를 수월하게 해결할 수 있다. HashMap의 Key에 정보 고릴라의 이름을, Value에 정보 고릴라가 가진 정보들의 가치가 내림차순으로 정렬된 우선순위 큐를 저장한다. 여기까지 하면 사실상 문제 풀이는 끝난 것이나 다름 없다. 1번 쿼리의 경우에는 Map에 저장되지 않은 정보 고릴라의 이름이 나오면 새로운 우선순위 큐를 생성하여 Map에 저장하고 정보들의 가치를 저장하면 된다. 2번 쿼리의 .. 2023. 3. 23. [Kotlin] 백준 1354 : 무한 수열 2 문제 링크 1354번: 무한 수열 2 첫째 줄에 5개의 정수 N, P, Q, X, Y가 주어진다. www.acmicpc.net 문제 해설 주어진 조건대로 재귀를 돌리면 된다. 다만 주어진 수의 범위가 굉장히 크기 때문에 피보나치 수를 재귀로 구할 때와 동일하게 별도의 Map에 이미 계산한 \(A_i\)를 저장하여 계산 횟수를 줄이는 것이 좋다. Code private val map = HashMap() private var p = 0L private var q = 0L private var x = 0L private var y = 0L fun main() = with(System.`in`.bufferedReader()) { val input = readLine().split(' ').map { it.to.. 2023. 3. 11. [Kotlin] 백준 25325 : 학생 인기도 측정 문제 링크 25325번: 학생 인기도 측정 학생 이름이 공백으로 구분된 문자열 A가 주어진다. 문자열 A에는 중복된 학생 이름이 존재하지 않는다. 학생 이름은 알파벳 소문자로 이루어져 있다. 각 학생이 좋아하는 학생의 학생 이름 목록 www.acmicpc.net 문제 해설 맵과 정렬을 이용하여 풀 수 있는 문제다. 풀이 과정은 다음과 같다. 맵에는 Key로 학생의 이름을, Value로 학생들의 인기도를 저장한다. 학생 이름과 인기도를 필드로 갖는 Student 클래스에 Comparable 인터페이스를 구현하여 인기도는 내림차순, 인기도가 같으면 이름 기준 오름차순으로 정렬할 수 있게 한다. 인기도 저장이 끝난 이후에는 각 학생 이름과 인기도로 Student 객체를 생성하여 별도의 리스트나 배열에 저장한다.. 2022. 12. 25. [Kotlin] 백준 15595 : 정답 비율 계산하기 문제 링크 15595번: 정답 비율 계산하기 첫째 줄에 어떤 문제의 총 제출 횟수 N(1 ≤ N ≤ 200,000)이 주어진다. 둘째 줄부터 N개의 줄에 각 제출의 정보가 제출 번호 순서대로 주어진다. 제출 정보는 총 7가지가 공백 하나로 구분되어져 있 www.acmicpc.net 문제 해설 BOJ의 정답 비율을 계산하는 알고리즘을 직접 구현해보는 문제다. 입력에 많은 정보가 있지만 문제의 조건을 봤을 때 필요한 것은 문제를 맞은 사람의 수, 문제를 맞은 사람이 이전까지 틀린 횟수, 문제를 맞은 사람의 유저 아이디만 있으면 된다. 우선 문제를 맞은 사람이 이전까지 틀린 횟수를 계산하기 위해 HashMap을 사용했다. 문제를 아무리 많이 틀려도 해당 유저 아이디가 최종적으로 문제를 맞추지 못한다면 분모에 .. 2022. 12. 10. 이전 1 다음
