글 읽기 - 단어 정렬 테스트 케이스를 구합니다 ..

lumyjuwon 6년 전 0

코드를 다 작성하고 난 후에 HashMap을 이용해서 풀어도 된다는 걸 깨달았습니다 ..

그런데 이미 작성한 코드는 아까워서 제출해봤는데 자꾸 틀렸다고 나오네요

어떤 테스트 케이스가 더 있을까요 ?

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class problem1181 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int input = sc.nextInt();
		
		String[] Array = new String[input];
		int[] Array_element = new int[input];
		
		// 단어 배열 및 길이 배열 선언
		for(int i = 0; i<input; i++)
		{
			Array[i] = sc.next();
			Array_element[i] = Array[i].length();
		}
		
		
		// 배열 몇 개를 복사
		String[] Arraycopy = Arrays.copyOf(Array, input);
		// 배열 길이 정렬
		Arrays.sort(Array_element);
		// 길이가 정렬된 배열을 복사
		int[] Array_elementcopy = Arrays.copyOf(Array_element, input);
		
		// 1. 배열의 Element 길이가 짧은 순서대로 배열
		for(int i = 0 ; i<Array.length; i++)
		{
			
			for (int k = 0; k<Array.length; k++)
			{
				if (Array[i].length() == Array_element[k] ) 
				{
					Array_element[k] = 0;
					Arraycopy[k] = Array[i];
					break;
				}
			}
			
		}
				
		
		// 밑의 구문에서는 index 범위를 설정하여 sort를 한다. 
		
		int i = 0;
		int start = 0;
		int end = 0;
		while(i<Array_elementcopy.length-1) {
			
			if(Array_elementcopy[i] == Array_elementcopy[i+1])
			{
				start = i;
				end = i;
				for(int k = i; k<Array_elementcopy.length-1; k++) {
					if(Array_elementcopy[k] == Array_elementcopy[k+1]) {
						end++;
					}
					else {
						break;
					}
				}
				
				i = i + end;
				
			}
			else {
				i = i + 1;
			}
			Arrays.sort(Arraycopy, start, end+1);
			// System.out.println(i + " " + start + " " + end);
			
		}
		
		
		// 배열을 ArrayList로 만들어 remove 할 수 있도록 변경
		ArrayList<String> List = new ArrayList<String>();
		
		
		// 배열을 ArrayList로
		for(int k = 0; k<Arraycopy.length; k++) {
			
			List.add(Arraycopy[k]);
		}
		
		
		// ArrayList 중복 요소 제거
		
		int n = -1;
		while(n <List.size())
		{
			n++;
			
			for(int m = n+1; m<List.size(); m++)
			{
				if(List.get(n).equals(List.get(m)))
				{
					List.remove(m);
					n = -1;
					break;
				}
			}
			
		}
		
		
		// ArrayList 출력
		for(int k = 0; k<List.size(); k++)
		{
			System.out.println(List.get(k));
		}
		
		
		sc.close();

	}

}

djm03178 6년 전 0

6
a
b
ab
aa
aab
aaa

66번째 줄이 이상합니다. i는 최소 2배가 되어버립니다.

그와는 별개로 코드 자체가 매우 비효율적이라 시간 내에 통과할 수 있을지 조금 의문입니다. 이 문제는 O(N*logN)에 풀기가 의도된 문제인데, 30~43번째 줄이나 92~106번째 줄이 모두 O(N^2)입니다.

lumyjuwon 6년 전 0

아, i = i + end 를 i = end로 바꾸니 해결이 됐네요 ㅎㅎ.. 그런데 djm님 말씀대로 시간초과가 ㅠ HashMap으로 다시 풀어봐야 겠네요 답변 해주셔서 감사합니다 ^^

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

문제

문제

출처

ICPC

단어 정렬 테스트 케이스를 구합니다 ..

lumyjuwon 6년 전 0

djm03178 6년 전 0

lumyjuwon 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말