본문 바로가기
728x90

백준브실골/Tree4

백준 14725, 개미굴 개요 문제 링크 골드 3, Tree, Trie 루트노드부터 리프노드까지의 탐색 결과를 바탕으로 트리 복원 접근 트라이를 알고만 있으면 크게 어렵지 않은 문제, 다만 한 노드에 하나의 알파벳을 저장하는 전형적인 트라이와 달리 한 노드에 string을 저장하고 있어야 한다. 트라이를 안다는 가정하에 설명하자면, 만약 현재 노드의 자식 노드에 문자열이 있으면 자식노드로, 없다면 새로운 노드로 업데이트를 해줘야 하고, 출력은 재귀를 이용해 하는데, 깊이를 입력으로 넣어줘야 한다. 왜냐하면 --의 출력횟수 = 깊이 이기 때문이다. N = 1000이고 k = depth = 15인데, 출력을 하면서 바로 정렬을 해버리면 된다. 이게 왜 먹히냐? 정렬 횟수가 생각보다 적거나, 정렬해야 하는 문자열의 개수가 생각보다 적.. 2023. 2. 15.
백준 16934, 게임 닉네임 개요 문제 링크 골드 2, Tree, Trie 최소한의 길이로 겹치지 않는 고유 아이디 출력 접근 어렵게 풀려면 어렵고, 쉽게 풀려면 쉽다. 우선 N이 100,000이므로 cin을 쓰면 안된다. 처음에 이것 때문에 TLE가 여러번 났다. 같은 이름이 들어올 때만 숫자를 출력해주므로 그냥 map을 써주면 된다. map에 들어있는 값이 1이상이라면 +1한 값을 출력하면 된다. 왜냐하면 이미 들어온 값이 또 들어온 것이기 때문. 나머지는 전형적인 트라이인데, 출력할 문자열에 포함할 원소를 결정하는 것이 살짝 까다롭다. 만약 트리에 추가되지 않은 원소를 만나면 그 뒤로는 출력해주면 안된다. 그럼 거기서 break를 거냐? 아니다. 나머지도 트리에 추가는 해줘야 같은 원소가 들어올 때 또 체크를 해줄 수 있다. .. 2023. 2. 15.
백준 12578, File Fix-it (Large) 개요 문제 링크 골드 4, Tree, Trie 이미 생성된 경로에 새로 경로를 추가할 때 추가해야 하는 폴더의 수 접근 조금 전형적이지 않은 트라이 문제, C언어에서는 malloc과 free를 통해 동적할당을 했는데, C++에서는 생성자와 소멸자를 사용해서 많이 절었다. 다음 노드에 대한 정보는 map을 쓸 수도 있고 vector를 쓸 수도 있는데 vector를 썼다. /를 이용해 문자열을 분해해주면서 leaf node인 경우 count를 추가해주고, count의 총합을 출력하면 되는 문제. C++에는 split 함수가 없다. split을 사용하는 가장 편한 방법은 뭘까? 보통 sstream을 많이 사용하는데, 이 문제에서는 find와 substr만 잘 이용해도 split을 구현할 수 있다. split(.. 2023. 2. 15.
백준 25601, 자바의 형변환 개요 문제 링크 실버 1, Tree 부모-자식 관계 연결 여부 출력 접근 트리 문제라기보다 일반적인 구현 문제에 가까운 문제이다. C++의 미친 장점, map을 사용하면 쉽게 풀린다. 각 문자열의 부모를 저장한 map을 생성한다. 그리고 A에서 B로, B에서 A로 탐색할 때, 둘이 같아지는 순간이 오면 부모-자식 관계로 연결된 것이다. 만약 map이 없다면? 정수 array를 통해 각 문자열의 인덱스를 저장하면 될 것이다. Pseudo code parent[A] = B find(A, B) { while (true) if (A == B) return 1 A = parent[A] } answer = find(A,B) || find(B,A) Source code #include #include using na.. 2023. 2. 15.
728x90

티스토리툴바