Algorithms/Data Structure

https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 1. Preview 시간 복잡도 1) Trie 자료구조 : O(N * L) - N : 전화번호 개수 - L : 전화번호 길이 2) 문자열 비교 : O(N) 공간 복잡도 : O(N) 2. 초기 접근 방법 https://wch-0625.tistory.com/102 자바 Trie 자료구조 구현 3. 생각 자바로 문제를 풀고, 주로 사용하는 파이썬으로도 Trie 자료구조를 구현 연..

[초기 접근 방법] 검사 문자열 inspect에 대해 집합 S 문자의 접두사가 맞는지 체크 → 시간복잡도가 O(MN * len(inspect[i])) = O(1억 * a) 으로 시간초과가 된다. [생각] 문제 유형을 보니 "Trie"라는 처음 보는 자료구조여서 블로그를 참조해 먼저 공부했다. Trie : 문자열을 저장하고 효율적으로 탐색하기 위한 '트리' 형태의 자료구조 → 자동완성, 사전 검색 등 문자열 탐색 기능 - insert() // 생성 시간 복잡도 : O(N*L) void insert(String word) { TrieNode node = this.rootNode; // 문자열의 각 단어의 자식노드를 찾아 return 하거나, 자식노드 새로 생성 // Map에서 현재 문자를 key로 Value..

[초기 접근 방법] - 맨 처음에 제시한 사람은 무조건 "진실"만을 들어야 한다. - 각 사람마다 일관되게 "과장된 이야기 or 진실"을 들어야 한다. - 해당 파티에서는 무조건 "과장된 이야기 or 진실"을 이야기해야 한다. 1. 제시한 사람이 있는 파티는 일단 전부 진실을 말한다. 2. 위 파티에 있는 사람들 모두 "진실파티" 에 넣는다. 3. 각 파티를 탐색하면서 파티 참석 인원 중 "진실파티"에 있는 사람이 있다면 참가한 사람들을 "진실파티"에 추가를 하고, 파티를 처음부터 다시 탐색해야 한다. "진실파티"에 있는 사람이 없다면 해당 루프에서 종료한다. [생각] 1. input.split() 내에서의 슬라이싱 set(map(int, input().split()[1:])) 2. set.union()..

[초기 접근 방법] 1) 개미굴 입구를 중심으로, 자식 노드들을 top [] 에 저장한다. 2) 자식노드들의 각 행에 중복되지 않는 노드들을 result[] 에 저장하도록 한다. [생각] 각 행에 중복되지 않는 노드들을 result[]에 저장하도록 구현했는데, 부모 노드가 다를 때에는 각각 저장해주어야 한다. 아래와 같은 test case 를 적어보았다. Input Output Answer 2 3 APPLE APPLE ORANGE 3 APPLE BANANA ORANGE APPLE --APPLE ----ORANGE --BANANA APPLE --APPLE ----ORANGE --BANANA ----ORANGE 올바른 접근 풀이는 다음과 같다. 1. 동굴 깊이 간선 정보를 정렬을 한다. → 사전 순서가 앞..