문자열2 [BOJ] 5052번: 전화번호 목록 (C++) Problem Solution 접두사를 통해 해결할 수 있는 문제이므로 트라이를 이용한다. 트라이를 통해 일관성 없는 전화번호 목록을 어떻게 찾을 수 있을까? 트라이에서 두 문자열이 같은 접두사를 공유하고 있으면 같은 노드를 공유하고 있다. 예를 들어 두 문자열 913, 9134가 트라이에 입력되었을 때, 두 문자열은 9, 91, 913 노드를 공유하고 있다. 이때 공유하는 노드 중에 문자열의 끝을 나타내는 노드가 있으면 일관성이 없는 전화번호 목록이라고 볼 수 있다. 이 예제에서는 913 노드가 문자열의 끝을 나타내는 노드이므로 913, 9134는 일관성이 없는 전화번호 목록이다. 1. 모든 전화번호를 트라이에 넣는다. 2. 각각의 전화번호를 트라이에서 탐색하면서 일관성 여부를 확인한다. 3. 마지막 .. 2021. 12. 16. [BOJ] 9935번: 문자열 폭발(C++) Problem Solution ❌ erase함수의 시간 복잡도는 O(N)이므로 erase함수를 사용하면 문제를 시간 내에 해결할 수 없다 1. 루프 문을 통해 문자열을 탐색하며 스택에 문자를 push 한다. 2. 만약 탐색한 문자가 폭발 문자열의 마지막 문자와 같으면 폭발 문자열의 길이만큼 스택에서 pop을 하여 폭발 문자열과 같은지 비교한다. 3. 스택에서 꺼낸 문자열과 폭발 문자열이 다르다면 꺼낸 문자들을 다시 스택에 넣는다. 4. 루프를 마치고 스택에 남아있는 문자열이 정답!! #include #include #include #include using namespace std; int main() { ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.. 2021. 12. 12. 이전 1 다음
