글 읽기 - 소스에 대한 반례를 찾지 못했습니다 부탁드려요

jwjpop 5년 전 0

단어들을 주고

길이에 대해 정렬하고

길이가 같다면 사전식으로 정렬한 후

중복은 제거하여 출력해야하는 문제입니다.

질문 게시판에 있는 반례들을 적용해보았지만

정답 출력으로 나와 적절한 반례를 찾지 못했습니다...

소스가 좋지 않지만 반례를 찾아주시면 감사합니다 ㅠㅠ

------------------------------------------------------------------

일단 ArrayList<MyString> arrayMs 통해 데이터들을 받은 후

leng 을 통해 길이별로 처음 정렬하였구요

그 정렬된 것들을

새로운 ArrayList<String> str 에 중복을 제거하여 넣습니다.

그 후 사전식으로 재정렬하기 위해 길이가 같은 친구들만 묶어서 A에 넣어주고

A를 sort하여 사전식으로 정렬한 후

정답 리스트인 ans에 넣어주었습니다.

---------------------------------------------------------------

댓글들 중에서 문제의 의도가 O(nlogn) 으로 해결하라는 댓글을 봐서

52~74 줄이 비효율적인 것은 확인하였습니다.

import java.util.*;

class MyString implements Comparable<MyString>{
	String word;
	int leng;
	
	public int compareTo(MyString ms)
	{
		if(this.leng>ms.leng)
			return 1;
		if(this.leng==ms.leng)
			return 0;
		else
			return -1;
	}
}

public class Main {
	public static void main(String args[]) {
		Scanner scn = new Scanner(System.in);
		int N = scn.nextInt();
		
		scn.nextLine();
		
		ArrayList<MyString> arrayMs = new ArrayList<MyString>();
		ArrayList<String> str = new ArrayList<String>();
		ArrayList<String> ans = new ArrayList<String>();
		ArrayList<String> A = new ArrayList<String>();
		
		for(int i=0;i<N;i++)
		{
			String input = scn.nextLine();
			MyString ms = new MyString();
			ms.word = input;
			ms.leng = input.length();
			arrayMs.add(ms);
		}
		
		//길이로 정렬
		Collections.sort(arrayMs);
		
		//중복 단어 제거
		for(int i=0;i<N;i++)
		{
			if(i==0)
				str.add(arrayMs.get(i).word);
			if(i!=0 && !arrayMs.get(i).word.equals(arrayMs.get(i-1).word))
				str.add(arrayMs.get(i).word);
		}
		
		//같은 길이일 때 사전순 정렬
		for(int i=1;i<=str.get(str.size()-1).length();i++)
		{
			
			int len = i;
			
			//길이가 같은 것들 찾기
			for(int j=0;j<str.size();j++)
			{
				if(str.get(j).length()==len)
				{
				A.add(str.get(j));
				}
			}
			//찾은 것을 사전식으로 정렬
			Collections.sort(A);
			
			//정렬한 것 정답 리스트에 추가
			for(int k=0;k<A.size();k++)
			{
				ans.add(A.get(k));
			}
			A.clear();
		}
		
		//정답 출력
		for(int i=0;i<ans.size();i++)
		{
			System.out.println(ans.get(i));
		}
		
	}
}

seico75 5년 전 1

10
a
b
c
a
b
c
a
b
c
a

jwjpop 5년 전 0

seico75 님 정말 감사합니다 ㅠㅠ

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