문제주어진 문자열 T, P에서 T 문자열 내에 P가 몇 번 나타내는지 출력하는 문제입니다.https://www.acmicpc.net/problem/1786 풀이접두사 기준으로 일치하는 부분 문자열 찾는 알고리즘인 KMP를 활용해서 해결했습니다.이때 문자열 P(pattern)를 이용해서 테이블을 형성하고만들어진 테이블과 문자열 T와 P를 이용해서 비교를 진행합니다.1) T.charAt(i) == P.charAt(idx)가 true일 때idx == pLen - 1가 true라면 T 문자열 내에 P가 존재한다는 뜻이므로카운트를 증가시켜줍니다.(P값이 T의 몇번째 인덱스에서 만들어졌는지 알기위해 list에 i-idx+1 값을 추가해줍니다.)2) 1)의 케이스에 해당하지 않는다면 idx를 ++ 합니다.비교를 마친..
문제- 주어진 문자열에서 두 번 이상 나오는 부분 문자열 중, 가장 길이가 긴 것을 구하는 문제입니다.https://www.acmicpc.net/problem/1701 풀이접두사 기준으로 일치하는 부분 문자열 찾는 알고리즘인 KMP를 활용해서 해결했습니다.이때 N번 반복하면서 접두사를 변경해주며 정답(부분 문자열 중 가장 긴 길이)을 도출했습니다. 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..
'+' 연산자를 이용한 문자열 + 문자열을 연산은막연하게 시간복잡도가 O(1)로 생각하고 있었다. 이런 생각을 갖고 문제를 푸는 과정에서 터질게 터지게 되었고해당 연산을 100만 ~ 1000만번 하면서 시간초과가 발생하게 되었다. string + string 연산은 + 연산자를 통해뒷 string의 문자를 하나씩 따와서 앞의 string에 연결하는 방식으로 동작하기 때문에시간 복잡도가 뒷 string의 길이가 된다.따라서 문제의 상황에서의 시간 복잡도는O(1)이 아닌 O(뒷 string의 길이)이다.
문제https://www.acmicpc.net/problem/1302 풀이해당 문제는 문자열과 관련된 문제로, map 자료구조를 활용해 해결했습니다. - string 값들의 수를 관리하기 위해서 Map 자료구조를 사용했으며- 입력을 받으면서 map에 저장한다음 max 값을 갱신해줍니다.- for문을 순회하면서, max값과 동일한 key에 대해서 List에 저장해두고- 오름차순 정렬 후 0번째 인덱스를 출력합니다. 코드14,212 KB / 100 msimport java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = ..
