목록알고리즘 (41)
시간이 NullNull
이 문제는 무려 5초를 주었다는 점과 N의 수가 작아 N*N을 하더라도 10000인 점 미생물의 수가 1000개 이하라는 점이 무조건 시뮬레이션이라는 생각이 들어 쉽게 풀게 되었다. 내가 사용한 변수들은 int[][] maxMap, int[][] dirMap, int[][] sumMap 이다 이름만 봐도 어떤 용도인지 알겠으나 나중에 더 자세히 설명하겠다. 1. m일 동안 진행하기 때문에 0~m-1까지 for문 돌기 2. 미생물이 합쳐지기도 죽기도 하기때문에 list가 아닌 Queue 사용 하였는데 하루동안 한칸만 움직여야 하기때문에 Q의 사이즈를 이용하여 그만큼만 for문을 돌아주었다. 3. 문제에 나와있듯이 한칸 움직인 후 배열의 가장 바깥쪽 칸들에 가면 크기를 반으로 줄이고 방향을 반대로 바꿔주었다..
주요 포인트! 1. 09:00 부터 n회 t분 간격으로 역에 도착한다. 나의 경우 09:00 부터라는 것을 제대로 못봐 문제가 이해가 되지 않아 한참동안 고민을 하였다. 2. m명을 태우면 더이상 태울 수 없다 ( 단, 기다리고 있는 줄은 유지된다. ) 이를 기준으로 나는 그냥 단순히 09:00 부터 각 셔틀버스마다 태울 수 있는 만큼 태우자 그리고 끝난 뒤에 1. 마지막 버스에 m명이 가득 차 있다면 마지막에 탄사람보다 1분 일찍오자! 2. 마지막 버스에 자리가 빈다면 마지막 버스가 도착할 시점에 오도록 하자! 이를 구현하기 위해서 우선 크루들이 도착하는 시간을 오름차순으로 정렬해야한다. 그래야 시간 순으로 버스에 태울 수 있기 때문이다. 그리고 시간 계산과 대소관계 비교를 원활하게 하기 위해서 시간 ..
문제를 쉽게 설명하면 1. go, gone, guild 라는 String 배열이 주어지면 이를 학습시킨다. 2. g를 입력하였을때 go와 gone가 나오므로 한번에 자동완성이 안된다. 3. 하지만 go 까지 하면 문자가 다 ( 자동 ) 완성이 되었다. 4. gon까지 입력시 gon으로 시작하는 문자는 gone 뿐이므로 gone을 완성시켜준다. 5. gu까지 입력시 gu로 시작하는 문자는 guild 이기때문에 guild를 완성시켜준다. 따라서 g + o + g + o + n + g + u 가 되어 7번 입력시 문자가 전부 자동완성 된다. 이를 풀기 위해서 지난번에 소개했던 Trie 알고리즘을 썼으며 1. 문자가 주어지면 Trie 트리를 만들고 2. 다음번에 문자 하나씩 읽으면서 ( 자동 ) 완성이 될때까지..
Trie로 검색 혹은 이 글을 보러 오신 분은 전화번호 목록에 대해서 알 것이라고 생각하고 문제 설명은 넘어가겠습니다. 그리고 sort의 경우 본인이 구현하셔도 상관없지만 이 글에서 Point의 경우 Trie 이기에 라이브러리를 활용하였습니다. ( 그리고 sort의 경우 해주지 않으면 9112 다음에 911이 들어오면 문제가 발생하여 sort 해주었습니다. ) Trie의 개념의 경우 제가 이전에 써두었던 글을 참고하시면 더 이해가 잘 가실 것 같습니다. 글 링크 따윈 저는 상남자니까 걸어두지 않을께요 이 문제는 저번 문제와 다르게 번호가 들어왔을때 ( 예를 들어, 911 이 입력되었고 다음줄에 9112가 들어오면 ) 911 때문에 isTerminal이 true 인 상황에서 현재 자식노드의 2번 이 nul..
java 트라이 알고리즘, Trie 알고리즘 등등으로 검색해서 오신 분들은 귀찮더라도 개념 자체는 다른 분들이 친절하게 그림까지 다 그려가면서 설명을 잘 해놓았기 때문에 다른 분들 글과 그림을 보면서 설명을 듣고 오시길 바랍니다! 사실 저도 엄청 검색을 해보고 많은 글을 보고 했었는데 먼가 진짜 쉽게 짜놓은 트라이 알고리즘은 없어서 이 새벽에 미친 듯이 고민해가며 트라이를 짜왔습니다. 문제는 SW Expert에 문자열 교집합이라는 문제를 참고로 하였고 사실 이 문제는 트라이로 풀면 메모리가 오버되어 절대로 풀 수가 없습니다. ㅎ.... 이거 때문에 왜 런타임 에러일까 하면서 한참을 고민했네요 B형을 준비하시는 분들은 LinkedList를 구현하는 것을 먼저 보고 오시길 추천드리며 LinkedList를 아..