기록방

👉 문제링크🔸 문제 분석 🔸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가 없다면, 생성해준다.마지막 노드..

👉 문제링크 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 🔸 문제 분석 🔸 기본 문자열과 폭발 문자열이 입력된다. 기본 문자열에서 폭발 문자열 부분이 폭발하며 지워지고, 남은 문자열은 다시 이어 붙는다. 더 폭발할 문자열이 남지 않았을 상태의 문자열을 출력한다. 남은 문자가 없으면 "FRULA"를 출력한다. 🔸 문제 풀이 🔸 문자열의 길이가 100만이기 때문에 O(n^2) 미만의 알고리즘을 사용해야 한다. 반복문 한 번에 계산할 수 있도록 한다. 새로운 문자열이 생기면 메모리 문제가 생길 수..

👉 문제링크 1235번: 학생 번호 첫째 줄에는 학생의 수 N(2≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 학생의 학생 번호가 순서대로 주어진다. 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같으며, 0부 www.acmicpc.net 🔸 문제 분석 🔸 학생번호를 중복되지 않도록 가장 짧게 만들 수 있는 길이를 출력한다. 번호를 줄일때는 왼쪽수 부터 버린다. 🔸 문제 풀이 🔸 학생 번호 문자열의 끝 부분에서 하나씩 길이를 늘려가며 중복되는 문자열이 있는지 확인해야한다. 끝 부분에 있으면 접근이 어려울 것 같아 문자열을 뒤집어서 저장 후 중복을 확인했다. 중복확인을 위해 문자열을 1부터 N-1까지 잘라가며 Set에 넣고 확인했다. 🔸 코드 🔸 import java.io.Bu..

👉 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔸 문제 분석 🔸 문자열 s의 각 자리 문자들을 index만큼 뒤 알파벳으로 바꾼다. z가 넘으면 다시 a부터 미룬다. skip에 포함 된 문자는 세지 않는다. 결과를 출력한다 🔸 코드 🔸 class Solution { public String solution(String s, String skip, int index) { String answer = ""; for(int i = 0; i < s.length(); i++) { int now = s.charAt(i) - 'a'; for(int j =..