👨🏻‍💻 PS/바킹독

[JAVA] 백준 1715번 【G4.카드 정렬하기】

문제 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 1️⃣ PriorityQueue 를 활용한 풀이 💡 떠오른 Idea 약간, 그리디 처럼 생각을 해보았다. 누적으로 묶음의 수만큼 합쳐지므로, 가장 작은 묶음의 수만 중복으로 값에 더해져야한다. 결론은, 카드 묶음을 합치는데 남은 카드 묶음 중에서 가장 작은 두 묶음을 골라서 합쳐야 한다. 카드 묶음을 합치게 되면, 다른 후보 묶음들 보다 커지게 될 수도 있고 여전히 작을 수도 있다. 따라서, 일단은 이 카드 묶음을 다시 후보로 올려두고,..

[JAVA] 백준 23326번 【G3.홍익 투어리스트】

문제 23326번: 홍익 투어리스트 도현이는 홍익 투어리스트가 되어 홍익대학교를 견학하려고 한다. 홍익대학교는 $N$개의 구역이 원형으로 배치된 모습이다. $1$번 구역에서 시계 방향으로 각각 $2$번, ... , $N$번 구역이 존재하고, www.acmicpc.net 풀이 1️⃣ treeSet을 이용한 풀이 💡 떠오른 Idea 구역의 개수가 500000 이고 쿼리의 개수가 100000 이므로 선형탐색을 하게되면 시간복잡도가 최대 500000*100000 으로 절대 통과 못하는 수치가 나온다. 따라서, treeSet을 이용한 풀이가 필요하다. treeSet의 대부분의 메서드는 log(N) 의 성능으로 동작하기 때문이다. treeSet에 명소 번호를 갱신하고, 쿼리문을 수행하면서 도현이의 위치도 갱신한다...

[JAVA] 백준 22939번 【G4.문제 추천 시스템 Version 1】

문제 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 풀이 1️⃣ TreeMap 과 TreeSet을 이용한 풀이 💡 떠오른 Idea 1. 요구사항에 가장 난이도가 낮은 것에서 가장 문제번호가 작은 것과 가장 난이도가 높은 것에서 가장 문제번호가 큰 것을 출력하라고 했다. 따라서, 난이도를 key로 정렬해주는 TreeMap안에 value로 문제 번호의 크기순으로 정렬해주는 TreeSet을 사용하면 되겠다고 판단했다. 2. 또한, solved 요청 시 문제 번호를 입력받아 지워야 하는..

[JAVA] 백준 20166번 【G4.문자열 지옥에 빠진 호석】

문제 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net 풀이 1️⃣ 백트래킹과 map을 이용한 풀이 이 문제는 백트래킹과 해시를 통해 문제를 해결하였다. 백트래킹을 통해서 만들 수 있는 문자열의 조합별 개수를 기록하였는데, 경로가 다르면 다른 경우의 수로 치기 때문이다. 백트래킹을 map의 각 포인트에서 시작하도록 설정하였고 탈출 조건을 설정한 길이에 도달했을 때 기록하는 방식을 사용했다. 왜냐하면, 예를 들어 (1,1) 에서 시작해서 길이가 2를 만족할때의 경우의 수는 다른 포인트에서 시작한 길이가 2인 경우와 절대 중복이 발생하지 않을 것이라 판단했기 때문이다. import java.io.*;..

[JAVA] 백준 13414번 【S3.수강신청】

문제 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net 풀이 먼저 이 문제는, 수강 신청을 한 학생들을 순서대로 자료구조에 넣어야 하는데, 이미 그 자료구조에 들어가 있는 학생인 경우, 제일 뒷 순서로 다시 집어넣어야 한다. 이 아이디어는, 이 문제를 푸는 누구나 떠올렸을텐데 생각보다 간단하게 풀릴 줄 알았는데 아니었다. 1️⃣ map과 priority queue 사용 set을 이용해서 중복여부를 확인할 수 있지만, 수강 신청 순서를 확인할 순 없다. HashMap map = new HashMap()..

[JAVA] 백준 20366번 【G3.같이 눈사람 만들래?】

문제 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 풀이 1️⃣ 조합을 이용한 풀이 주어진 눈덩이 중 2개로 만들 수 있는 눈사람의 높이를 모두 구한다. 단, 두 사람이 같은 눈덩이를 사용할 수 없다. 서로 다른 눈덩이 4개가 사용되어야 한다. 따라서, 그냥 합의 조합만 구하면 이러한 부분을 체크할 수 없기 때문에 어떤 인덱스의 눈덩이로 눈사람을 만든건지 정보가 필요하다. 따라서, 클래스를 새롭게 하나 정의해야한다. static class SnowMan{ int idx1; int..