카카오11 [2020 카카오 기출] 가사 검색(JAVA) 문제: https://programmers.co.kr/learn/courses/30/lessons/60060 참고 링크: https://shjz.tistory.com/99 shjz님의 블로그 글을 참고해서 해결했습니다. 중요한 점은 3가지 입니다. 1. 트라이 사용 문제 2. 정방향 트라이와 역방향 트라이를 사용 3. 문자열 길이만큼 트라이배열을 만들어서 사용 1. 트라이 사용 문제 각 문자열에 대한 판단을 O(M) (M: 문자열의 길이)에 끝내기 위해 트라이를 사용합니다. 2. 정방향 트라이와 역방향 트라이를 사용 '?'(와일드 카드 식별자)가 중간에 나오지 않는다는 뜻은 '?'가 나온 시점에는 나머지 탐색에 대한 처리가 상수 시간에 끝나야 합니다. 그렇게 처리하지 않고 26(알파벳 크기)^(남은 문자.. 2021. 5. 24. [2018 카카오 기출] 파일명 정렬(JAVA) programmers.co.kr/learn/courses/30/lessons/17686 시뮬레이션 문제입니다. 저는 File이라고 하는 별도의 클래스를 선언했고 아래와 같이 네 부분으로 나눠습니다. 첫 문자 부분(String HEAD) 숫자 부분(int NUMBER) 배열 안에 들어있던 순서(int isbn) 원래 파일명(String origin) 파싱하는 게 번거로운 편이고 파싱 후에 문제 조건대로 정렬해주면 됩니다. 코드: github.com/cotchan/algorithm/blob/main/java/PROGRAMMERS/PG17686.java 2021. 4. 28. [2020 카카오 기출] 블록 이동하기 문제: https://programmers.co.kr/learn/courses/30/lessons/60063 시뮬레이션 문제입니다. 따져줄 게 참 많아보이는 문제입니다만 아래 두 가지에 대해서만 잘 정하고 풀면 됩니다. 1. 상태를 어떻게 저장할 지 2. 다음 좌표 탐색을 어떻게 할 지 우선 편의를 위해 블록의 2칸 중 한 칸을 HEAD, 다른 한 칸을 TAIL이라고 하겠습니다. 우리는 (HEAD_Y, HEAD_X, TAIl_Y, TAIL_X)로 4개의 정보가 필요하지만 이는 (HEAD_Y, HEAD_X, HEAD가 TAIL과 연결되어 있는 방향) 3개 정보로 똑같이 표현할 수 있습니다. 그래서 상태를 어떻게 저장하느냐에 대해서는 (HEAD_Y, HEAD_X, Direction)으로 표현하겠습니다. (b.. 2020. 8. 11. [2018 카카오 기출] 자동완성 트라이 자료 구조로 해결할 수 있는 문제입니다. 탐색을 O(L)에 할 수 있습니다. 먼저 입력받은 문자열에 대해 트라이를 만들고, 다시 한 번 더 순회하면서 정답을 구하면 됩니다. 트라이는 상태정보로 child를 가지고 있습니다. 특정 노드에 있는 알파벳이 insert 메서드에 호출될 때 마다 child += 1을 해줍니다. 즉, 자신이 완성된 뒤에도 누군가 자신을 호출했다면 그 단어는 자신과 자식관계가 되는 셈입니다. 자동완성 기능을 통해 더 이상 탐색을 안해도 되는 경우는 현재 탐색하는 알파벳에서 남은 문자열이 하나밖에 없는 경우이고, 그 때 child 값은 1입니다. 그래서 그 높이까지 탐색하도록 find 함수를 작성하면 됩니다. 2020. 5. 8. 이전 1 2 3 다음
