시간복잡도...

Question

https://www.acmicpc.net/problem/2179 이문제입니다.. 제한시간이2초인데 시간초과 떠야할거같은데 100점이네요.. 찜찜해서 왜 이런지 이유가 궁금합니다.n제곱 곱하기 문자열길이 이면 4*10의 8승 에 문자열길이 100 을 곱하는거 아닌가요? 그럼 10의 10승 이되는데 왜 안터지는지....궁금합니다 ㅠㅠ import java.io.*;import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br &#61; new BufferedReader(new InputStreamReader(System.in)); String str &#61; br.readLine(); StringBuilder sb&#61;new StringBuilder(); int n&#61;Integer.parseInt(str); String []str2 &#61; new String[n]; int max&#61;-1; for(int i&#61;0;i<n;i&#43;&#43;){ str2[i] &#61; br.readLine(); } // System.out.println(str2.length); String s&#61;&#34;&#34;; String t&#61;&#34;&#34;; for(int i&#61;0;i<n;i&#43;&#43;){ String tmp&#61;str2[i]; for(int j&#61;i&#43;1;j<n;j&#43;&#43;){ String tmp2&#61;str2[j]; int cnt&#61;0; // System.out.println(tmp); int size&#61;Math.min(tmp.length(),tmp2.length()); for(int k&#61;0;k<size;k&#43;&#43;){ if(tmp.charAt(k)&#61;&#61;tmp2.charAt(k) ){ cnt&#43;&#43;; } else break; } if(max<cnt){ max&#61;cnt; s&#61;tmp; t&#61;tmp2; } } } sb.append(s).append('
').append(t); System.out.println(sb.toString()); } }

kenu,전독시 · Answer

죄송합니다만당신이 더 복잡한데요.다른 길도 많습니다? 다른 길도 있습니다.

kenu,전독시 · Answer

문제 2179는 두 개의 문자열 중에서 가장 긴 공통 접두사를 찾는 문제입니다. 주어진 코드를 보면, 각 문자열 쌍에 대해 공통 접두사를 찾아 최대 길이를 추적하고 있습니다. 그러나, 이 방법은 효율적이지 않으며, 특히 입력 크기가 큰 경우에는 시간 초과 문제가 발생할 수 있습니다.문제의 핵심은 문자열의 길이가 매우 클 때, 모든 가능한 쌍을 검사하는 것이 아니라 더 효율적인 방법을 사용해야 한다는 것입니다. 현재 코드에서는 O(n^2 * min_len)의 시간 복잡도를 가집니다. 여기서 n은 문자열의 개수이고, min_len은 두 문자열 중 하나의 길이입니다. 이는 매우 비효율적이며, 특히 n과 min_len이 크면 시간 초과 문제가 발생할 수 있습니다.해결 방안문자열의 길이가 매우 클 때, 모든 가능한 쌍을 검사하는 대신, 더 효율적인 알고리즘을 사용할 수 있습니다. 예를 들어, 문자열을 사전 순으로 정렬한 후, 첫 번째 문자열부터 시작하여 나머지 문자열들과 비교하면서 공통 접두사의 길이를 갱신하는 방법이 있습니다. 이 방법은 O(n log n + n^2)의 시간 복잡도를 가지며, 대부분의 경우에 충분히 빠릅니다.다음은 수정된 코드 예시입니다:import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] strs = new String[n]; // 문자열들을 사전 순으로 정렬 Arrays.sort(strs); String ansStr = ""; int maxLen = -1; // 첫 번째 문자열부터 시작하여 나머지 문자열들과 비교 for (int i = 0; i < n; i++) { if (i > 0 && strs[i].startsWith(strs[i - 1])) { continue; // 이미 이전 문자열보다 짧은 접두사가 있으면 건너뜀 } int len = 0; while (len < strs[i].length() && len < strs[0].length()) { if (strs[i].charAt(len) == strs[0].charAt(len)) { len++; } else { break; } } if (len > maxLen) { maxLen = len; ansStr = strs[i]; } } System.out.println(ansStr); } } 이 코드는 먼저 문자열들을 사전 순으로 정렬합니다. 그런 다음 첫 번째 문자열부터 시작하여 나머지 문자열들과 비교하면서 공통 접두사의 길이를 갱신합니다. 만약 현재 문자열의 접두사가 이전 문자열보다 길다면, 이를 새로운 최대 접두사로 업데이트합니다. 이렇게 하면 모든 가능한 쌍을 검사하지 않고도 최종 결과를 얻을 수 있으며, 시간 복잡도가 크게 줄어들게 됩니다.from: https://www.phind.com/search?cache=joxr1s5bji49ri8gnizt82kk

시간복잡도...

2개의 답변

Q&A 목록