기록방

👉 문제링크🔸 문제 분석 🔸t 번의 테스트 동안 n 개의 전화번호가 주어진다. 각 전화번호가 서로 접두어가 되는 경우가 없는지 판단한다.접두어 관계가 있으면 NO, 없으면 YES를 출력한다.🔸 문제 풀이 🔸n개의 문자열들을 서로 비교해야하는데, n이 1만이므로 O(n^2)으로 비교하면 테스트케이스까지 합쳐서 1초를 초과하게 된다.방법은 2가지가 있는데 정렬 혹은 트라이 자료구조를 이용하는 것이다.정렬 : 현재 문자열보다 긴 문자열 하고만 비교해서 접두어인 경우가 있는지 파악한다.트라이 : 현재 문자열을 접두어로 하거나, 다른 문자열이 현재 문자열에게 접두어인지 확인한다.🔸 정렬 풀이 코드 🔸import java.io.*;import java.util.Arrays;import java.util..

💡 트라이(Trie)는 트리형태로 문자열을 저장해 빠르게 탐색하는 자료구조이다. 일반적인 이진트리의 시간 복잡도는 O(logN) 이지만, 길이가 M인 문자열을 저장하면 O(M*logN)의 시간 복잡도를 갖는 문제가 생긴다.이러한 문제를 해결하기 위해서 Trie는 문자열의 문자 하나씩 노드에 저장한다.문자열 하나를 검색할 때 O(N)의 시간 복잡도를 갖는다.Java에서는 Map 자료구조를 이용해 구현한다.저장된 문자열 : cap, code, kakao, kai 🚀 트라이 자료구조 생성 및 사용검색하고자 하는 문자열을 트라이 클래스에 모두 저장한다.하나의 문자열을 저장할 때, 각 문자를 key로 자식 노드를 value로 트리 형태를 띄는지 확인한다.만약 현재 문자 key가 없다면, 생성해준다.마지막 노드..

👉 문제링크 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 🔸 문제 분석 🔸 중위 표기식을 후위 표기식으로 변환해 출력한다. 입력되는 피 연산자는 알파벳 대문자, 연산자는 "+-*/()"의 6가지가 사용된다. 스택 자료구조를 사용해서 후위 표기식으로 변환할 수 있다. 🔸 코드 🔸 import java.io.*; public class Main { private static class MyStack { private int pointer; private char[] stack; public MyStack(..

👉 문제링크 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 🔸 문제 분석 🔸 문제 내용 N명의 사람과 M개의 파티가 있다. 진실을 아는 사람이 참여한 파티에서는 진실만 말해야 한다. 진실을 말한 파티에 있던 사람들도 진실을 아는 사람이 된다. 거짓을 말할 수 있는 파티의 수를 출력한다. 풀이 전략 같은 파티 참가자를 연결해야 한다. 각 파티별 참가자 List와 개인 별 참가 파티 List를 만든다. BFS로 진실을 말한 파티와 진실을 알게된 사람들을 추가해 나간다. 진실을 말하지 않은 파티의 수를 출력한다. 2024...

👉 문제링크 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 🔸 문제 분석 🔸 int 범위의 값을 넣는 'I' 연산과 최대값 혹은 최소값을 빼는 'D'연산이 k번 수행된다. 최종 연산 후 결과를 출력한다. k의 최대값이 1,000,000 이므로 값을 저장할 자료구조를 힙 형태로 구현해야 한다. 힙정렬이 적용된, 우선순위 큐(Priority Queue) 혹은 TreeMap을 사용한다. 🔸 Priority Queue 🔸 import java.io.BufferedReader; import java.io.IOEx..