글 읽기 - 1181번 시간초과

qpoas 6년 전 0

String 배열이 51이 되서 시간초과인가요 아니면

sort하는 부분이 시간초과인가요..?

왜 시간초과가 나는지 모르겠습니다ㅠㅠ

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.io.*;

public class Main {
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//Scanner sc = new Scanner(System.in);

		int N = Integer.parseInt(br.readLine());
		String[] array = new String[N];
		String[] countarray = new String[51];
		
		for(int i = 0; i < countarray.length; i++) {
			countarray[i] = "";
		}
		
		int max = 0;
		
		for(int i = 0; i < N; i++) {
			array[i] = br.readLine();
			countarray[array[i].length()] += array[i] + " ";
			
			if(max < array[i].length())
				max = array[i].length();
		}

		for(int i = 1; i <= max; i++) {
			if(!countarray[i].equals("")) {
				String[] result = countarray[i].split(" ");
					
				Arrays.sort(result);
				
				for(int j = 0; j < result.length; j++) {
					int k = j + 1;
					
					if(k != result.length && result[j].equals(result[k]))
						continue;
					else
						System.out.println(result[j]);
				}
			}
		}
		br.close();
	}
}

djm03178 6년 전 2

String 객체는 immutable 하기 때문에, String을 += 하는 연산은 기존의 문자열과 덧붙일 문자열의 내용을 전부 복사하는 과정을 거쳐 새 객체를 만들어야 됩니다. 따라서, 길이가 같은 문자열이 N개 들어온다면 O(N^2) 시간이 소요되고 각 문자열의 길이만큼의 상수배가 곱해지면 매우 긴 시간이 됩니다.

qpoas 6년 전 0

감사합니다ㅎㅎ몰랐던 사실이네요!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1181번 시간초과

qpoas 6년 전 0

djm03178 6년 전 2

qpoas 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말