[programmers/kakao] [3차] 압축 (Java/Trie)
문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 알파벳 'A' - 'Z'로 이루어진 사전과 문자열 msg가 주어진다. 이 msg의 문자중 사전과 최장 일치하는 문자를 찾고, 문자열이 일치하지않는다면, 사전에 추가하며, 일치하는 문자열의 Index(색인 번호)를 출력하는 문제다. 풀이 우선 이 문제에서 msg의 길이는 최대 1,000이다. 완전탐색으로 구현할 경우, 최악의 경우는 (아마)다음과 같을것 이다. msg : ..
[programmers/kakao] [3차] 자동완성 (Java)
문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/17685?language=java 코딩테스트 연습 - [3차] 자동완성 자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g programmers.co.kr 검색어 자동완성 기능을 만들고, 모든 문자를 찾기위해서 최소 몇번 타이핑해야하는지 찾는 문제다. 풀이 전형적인 Trie 문제였다 모든 단어의 길이를 합쳤을때 최대 1,000,000길이가 나오니 Trie 구조를 만드는데, 1,000,000번 반복하며, 모든 단어의 길이의 합이 최대 1,000,000 이므로 ..
[백준 / BOJ] 9202 Boggle
문제 출처 : www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net 각칸에 알파벳 대문자가 적혀있는 보드가 주어졌을때 단어를 찾는 게임을 하려고한다. w개의 찾을 단어가 주어지고, 각 칸마다 알파벳 대문자가 적혀있는 b개의 4*4 보드가 주어졌을때, 가장 많이 얻는 점수 , 가장 긴 문자열, 가장 많이 찾을수있는 단어의 수 를 구하는 문제다. (이동은 현재위치에서 8방향(가로, 세로, 대각선)으로 갈수있다.) 풀이 일반적인 완탐만 사용할경우, 최..
