밤이 블로그

BOJ#5670 휴대폰 자판 * 문제https://www.acmicpc.net/problem/5670 * 풀이카카오 블라인드 채용 - 3차 코딩테스트 5번 문제와 유사합니다. Trie를 사용하여 풀어보았습니다. 1. 모든 문자열을 Trie에 저장한 후2. child의 개수가 2 이상인 경우, terminal 노드인데 child가 존재하는 경우를 카운트하였습니다. 부족한 점이 있으면 댓글로 알려주세요. 감사합니다. * 나의 코드https://github.com/stack07142/BOJ/blob/a3f55a12084c8b798e96dd86eedbdc8661595777/BOJ%235670/src/Main.java import java.io.BufferedReader; import java.io.IOExcep..

BOJ#5052 전화번호 목록 * 문제https://www.acmicpc.net/problem/5052 * 풀이저는 이 문제를 Trie를 이용해서 풀어보았습니다. Trie를 처음 공부하고 풀어보는 것이라서 부족한점이 있을 것 같습니다. 댓글로 알려주시면 감사하겠습니다. , 1. 일단 전화번호 목록을 배열에 저장한 후 정렬을 진행합니다.2. Trie 자료구조에 Insert합니다.3. 이 과정에서 terminal 노드인데 children이 추가되는 경우 '일관성 있지 않은' 목록으로 판단합니다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%235052/src/Main.java import java.io.BufferedReader; import java..

BOJ#1152 단어의 개수 * 문제https://www.acmicpc.net/problem/1152 * 풀이1. 문자열을 입력받습니다. 앞, 뒤 공백이 있을 수 있으므로 trim 함수를 이용하여 공백을 제거합니다.2. 문자열을 정규표현식을 이용하여 분리합니다. (정규표현식 : \\{Blank}+ : 공백이 하나 이상)3. 분리한 문자열의 개수를 출력합니다. * 나의 코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * BOJ#1152 단어의 개수 * https://www.acmicpc.net/problem/1152 */ public class Main { public stati..

BOJ#1254 팰린드롬 만들기 * 문제https://www.acmicpc.net/problem/1254 * 풀이 1. 입력받은 문자열 S를 뒤집은 문자열 R을 생성합니다.2. S의 접미사이면서 R의 접두사인 문자열을 찾습니다.3. 문자열을 찾고 나면, 이 때 R의 남은 부분을 S뒤에 붙이면 팰린드롬이 됩니다.4. 이런 경우가 여러개가 있다면, 그 중 팰린드롬의 길이가 최소가 되는 경우를 찾으면 됩니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%231254_Palindrome/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputS..

BOJ#10942 팰린드롬? * 문제https://www.acmicpc.net/problem/10942 * 풀이 문자열 중에서 팰린드롬에 대하여 지금 공부할지 아니면 나중에 공부할지 고민했습니다만..(알고리즘 대회가 아니면 별로 쓸 일이 없기 때문에) 간단히 O(N^2) 풀이와 O(N)풀이에 대해 공부해 보았습니다. 완벽히 이해한 상태가 아니기 때문에 설명은 나중에 추가하도록 하겠습니다.팰린드롬은 너무 어렵습니다.. 팰린드롬 공부 링크 : http://stack07142.tistory.com/128 * 나의 코드 O(N), Manacher's Algorithm - 어느 한 원소를 기준으로 좌/우로 넓혀가면서 검사 -> N이 홀수인 경우에는 문제없지만, N이 짝수인 경우에는 문제가 생김 -> 일괄적으로 2..