J

문제 바로 가기 > 문제 링크 💡 1. 기존 Trie 알고리즘과 달리 층별로 삽입되는 String들을 하나의 변수에 넣어서 넘기지 않음. 그러므로 삽입 시, parent를 넘겨주어야 함. 2. 출력 시, map을 list로 변환하여 정렬해준다. 또한 백트래킹처럼 연결된 모든 것을 출력한 뒤 다음 child를 출력해야 하므로 재귀를 사용한다. import java.util.*; import java.io.*; public class boj_14725 { static class Node{ Map childNode = new HashMap(); boolean end; } static class MakeAntHole{ Node rootNode = new Node(); Node insert(Node root, S..

https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net Trie 자료구조를 사용해 문제를 해결하였다. 💡 computeIfAbsent() Map에서 특정 키에 해당하는 값이 존재하는지 확인한 후, 없으면 새로 만들어서 넣어주는 형태의 코드이다. Key값에 해당하는 value가 존재하면 가져와서 사용하고 없으면 새로 만들어주는 패턴의 코드를 위해 computeIfAbsent()라는 메소드를 이용할 수 있다. 전 Value valu..

풀이 방법 Queue를 이용하여 각각의 상위 parent의 node 값을 저장해준다. convert 함수를 통해 num을 이진수로 변환한다. 이때 예시의 63을 생각해보면 원래의 이진수는 1부터 시작해야 한다. 그러므로 완전 이진트리를 생각했을 때 이진수의 길이에 값을 맞추기위해 앞에 0을 추가해야 함을 생각하자. 가능한 이진수의 길이는 nums 배열에 저장해두었다. 가능한 이진수의 길이가 되게 하기 위해 그만큼 앞에 0을 추가해주자 check 함수를 통해 이진트리가 되는지 확인한다. 짝수의 경우 미리 저장해둔 roots배열을 확인한다. 홀수의 경우 4로 나눈 나머지가 1인 친구들과 2인 친구들에 따라 parent가 다르다. 가능한 이진트리가 되려면 자식이 존재하는 경우 부모가 존재해야 한다. impor..

풀이 방법 PriorityQueue를 사용하여 String이 사전 순으로 계속 정렬되게 한다. 가지치기를 하면서 poll 값을 조사할지 말지 결정한다. 도착 위치와 현재 위치 거리가 남은 거리보다 크면 절대 도착할 수 없다. (현재 위치와 도착 위치 사이 거리)와 남은 거리의 홀짝은 같아야 한다. import java.io.*; import java.util.*; class Solution { static class load{ int x; int y; int time; String route; load(int x, int y, int time, String route){ this.x = x; this.y = y; this.time = time; this.route = route; } public Stri..

💡 주의할 점 1. 셀에 값이 없더라도 병합이 가능하다. 2. 셀의 값은 서로 같을 수 있다. 풀이 방법 cell을 저장할 class를 정의한다. 이때 생성 시 값의 초기값은 “”가 아니라 null로 주었다.(상관 없을 것 같다!) 병합할 때 같은 cell을 가리키고 있는 것들도 같이 수정해준다. (merge 함수에서 table[r1][r2] = table[r3][r4]만 하면 절대 안됨) merge할 때 하나의 값이 null이라고 그 cell에 연결된 표가 1칸이라는 뜻은 아님!!! 값이 없어도 merge가 가능하기 때문에 같은 곳을 가리키는 표가 있는 지 확인해주어야 한다. import java.io.*; import java.util.*; class Solution { static class cel..

https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 💡 부분집합과 BFS를 활용하여 문제를 해결하였다. 1. 부분 집합을 통해 5X5 좌표에서 7개를 골라준다. 2. 이때 'Y'의 개수가 3개이상이면 return 해준다. 3. 7개를 골라주면 BFS를 통해 서로 연결되어 있는지 확인해준다. 전체 코드 import java.util.*; import java.io.*; public class Main { static char[][] classroom; ..