문제주어진 문자열 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 = ..
문제https://www.acmicpc.net/problem/19951 풀이해당 문제는 누적합 알고리즘의 imos를 사용하는 문제이다. 1. 입력 수열을 0을 패딩주고 1 - N에 값을 저장2. imos 알고리즘을 활용하여 구현3. 쿼리에 따라서 값을 sumArr에 마킹해줌 예를들어 a - b 구간에 3을 더해준다면, sumArr[a] += 3, sumArr[b+1] -= 3 a - b 구간에는 3을 더해주고, 그 다음 값인 b+1 부터는 -3을 하여 다시 원래대로 돌리는 작업을 하는 것4. 쿼리를 마치고 1 - N 순회하면서5. imos 배열 값(sumArr)을 바탕으로 누적합 구하고 + 수열의 값(arr[i])를 더해주어 출력 코드import java.io.*;import java.util..
문제https://www.acmicpc.net/problem/13911 풀이 코드121,788 KB / 940 msimport java.io.*;import java.util.*;public class Main { static final int INF = 1 [] list; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nex..
문제https://www.acmicpc.net/problem/16194 풀이 코드15044 KB / 180 msimport java.io.*;import java.util.*;public class Main { static int N; static int[] arr, dp; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; N = Integer.parseInt(br.readLine()); arr = new int[N+1..
문제https://www.acmicpc.net/problem/12015 풀이해당 문제는 LIS 풀이로 접근했습니다.하지만, 가장 긴 증가하는 부분 수열 시리즈 1번보다 입력 값이 큰 점에서 차이가 있습니다.(N 최대 1,000,000)이 부분을 이분탐색을 적용하여 시간 복잡도를 줄였습니다.풀이 방법은 다음과 같습니다.1. 가장 긴 증가하는 부분수열이 담길 list를 선언 및 초기화합니다.(초기 값으로 list에 0을 add 해줍니다. list size를 체크할 때 에러방지) 2. 입력값을 하나씩 받으며 로직을 진행합니다.(로직은 list 값을 변경하거나 추가하기 위해 진행합니다.) 2-1. tgt(입력받은 값)이 list의 마지막 인덱스에 위치한 값보다 클 경우, (마지막에 추가해도 증가 수열이 유지되기..
