염라대왕의 이름 정렬[SWEA 7701][Java][TreeSet]

[광고 누르면 오늘의 행운 상승!!]

 

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?contestProbId=AWqU0zh6rssDFARG&solveclubId=AW--k1o64VwDFAVg&problemBoxTitle=20200312&problemBoxCnt=1&probBoxId=AXDJArbqfckDFAVX+

 

SW Expert Academy

문제의 저작권은 SW Expert Academy에 있습니다.

여러가지 방법을 사용하여 구현해 보았다.

## 1~ 5 올라갈 수록 수행속도 빠름 ## 

1. 선택정렬 (시간초과) 

package Study0307;

import java.io.*;
import java.util.*;

public class 염라대왕의이름정렬 {

	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("test.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();// 1~50
		
		for (int tc = 0; tc < T; tc++) {
			int N = sc.nextInt(); //이름의 개수 1~20,000
			
			String[] name = new String[N];
			
			for (int i = 0; i < N; i++) {
				name[i] = sc.next();
			}
			// 선택정렬 - 우선순위
			// 0 ~ 끝 : name[0] <-> name[minIndex];
			// 1 ~ 끝 : name[1] <-> name[minIndex];
			// 끝 ~ 끝 : name[끝] <-> name[minIndex];
			for (int i = 0; i < name.length; i++) { //범위의 시작 값
				int minIndex = i; //최소값의 방번호
				for (int j = i; j < name.length; j++) {// 범위 i~끝
					if(compare(name[minIndex], name[j]) > 0) {//최소값이라면
						minIndex = j;//최소값 인덱스 기억
					}
				}
				//swap name[i] <-> name[minIndex]
				String temp = name[i];
				name[i] = name[minIndex];
				name[minIndex] = temp;
				
			}
			//중복제거
			//System.out.println("#" + tc + " " + );
			
			String temp = null;
			for (int i = 0; i < name.length; i++) {
				if(!name[i].equals(temp)) {
					System.out.println(name[i]);
				}
				temp = name[i];
			}
		}
	}
	//바꿔야된다면,(next 앞으로 가야한다면) 양수를 리턴
	private static int compare(String pre, String next) {
		 if(pre.length() != next.length()) {//글자의 길이 짧은 순
			 return pre.length() - next.length();
		 }else { // 길이가 같으면, 사전순
			 return pre.compareTo(next);
		 }
	}
}

2. Arrays.sort (3100ms)
기본형-> 퀵소트
객체형-> 32개 이하 :  머지소트
             32개 이상 :  팀소트(머지 + 선택)

package Study0307;

import java.io.*;
import java.util.*;

public class 염라대왕의이름정렬2 {

	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("test.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();// 1~50
		
		for (int tc = 1; tc <= T; tc++) {
			int N = sc.nextInt(); //이름의 개수 1~20,000
			
			String[] name = new String[N];
			
			for (int i = 0; i < N; i++) {
				name[i] = sc.next();
			}
			Arrays.sort(name, new Comparator<String>() {
				public int compare(String pre, String next) {
					if(pre.length() != next.length()) {//글자의 길이 짧은 순
						 return pre.length() - next.length();
					 }else { // 길이가 같으면, 사전순
						 return pre.compareTo(next);
					 }
				}
			});
			//중복제거
			System.out.println("#" + tc);
			
			String temp = null;
			for (int i = 0; i < name.length; i++) {
				if(!name[i].equals(temp)) {
					System.out.println(name[i]);
				}
				temp = name[i];
			}
		}
	}
}

3. TreeSet (1200ms)

package Study0307;

import java.io.*;
import java.util.*;

public class 염라대왕의이름정렬3 {

	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("test.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();// 1~50
		
		for (int tc = 1; tc <= T; tc++) {
			int N = sc.nextInt(); //이름의 개수 1~20,000
			
			TreeSet<String> name = new TreeSet<String>(new Comparator<String>() {
				public int compare(String pre, String next) {
					if(pre.length() != next.length()) {//글자의 길이 짧은 순
						 return pre.length() - next.length();
					 }else { // 길이가 같으면, 사전순
						 return pre.compareTo(next);
					 }
				}
			});
			
			for (int i = 0; i < N; i++) {
				name.add(sc.next());
			}
			
			System.out.println("#" + tc);
			
			for (String string : name) {
				System.out.println(string);
			}
		}
	}
}

4. TreeSet + StringBuilder (600ms)

package Study0307;

import java.io.*;
import java.util.*;

public class 염라대왕의이름정렬4 {
	//시간터짐
	//3100
	//2900
	//500~600
	//아이디어 : 글자 개수에 해당하는 배열에
		//        글자길이가 동일한 이름들을 TreeSet으로 사전순 정렬 해보자
		//        글자 개수가 작은 TreeSet 부터 출력하면 됨
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());// 1~50
		
		for (int tc = 1; tc <= T; tc++) {
			int N = Integer.parseInt(br.readLine()); //이름의 개수 1~20,000
			
			TreeSet<String> name = new TreeSet<String>(new Comparator<String>() {
				public int compare(String pre, String next) {
					if(pre.length() != next.length()) {//글자의 길이 짧은 순
						 return pre.length() - next.length();
					 }else { // 길이가 같으면, 사전순
						 return pre.compareTo(next);
					 }
				}
			});
			
			for (int i = 0; i < N; i++) {
				name.add(br.readLine());
			}
			
			sb.append("#").append(tc).append('\n');
			
			for (String string : name) {
				sb.append(string).append('\n');
			}
			System.out.println(sb);
		}
	}
}

5. TreeSet2개를 이용하여 글자길이가 동일한 이름들을 TreeSet으로 정렬 (600ms)

-> 글자의 개수가 골고루 포진되어 있을 때 시간을 많이 절약한다.

package Study0307;

import java.io.*;
import java.util.*;

public class 염라대왕의이름정렬5 {
	//아이디어 : 글자 개수에 해당하는 배열에
	//        글자길이가 동일한 이름들을 TreeSet으로 사전순 정렬 해보자
	//        글자 개수가 작은 TreeSet 부터 출력하면 됨
	//        글자의 개수가 골고루 포진되어 있을 떄 시간을 많이 줄일 수 있다.
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());// 1~50
		
		for (int tc = 1; tc <= T; tc++) {
			int N = Integer.parseInt(br.readLine()); //이름의 개수 1~20,000
			
			TreeSet<String>[] tsrr = new TreeSet[51];
			for (int i = 0; i < tsrr.length; i++) {
				tsrr[i] = new TreeSet<String>(); // 배열 각 칸에 생성해서 넣기
			}

			for (int i = 0; i < N; i++) {
				String str = br.readLine();
				tsrr[str.length()].add(str);
			}
			
			sb.append("#").append(tc).append('\n');
			
			for (int i = 1; i < tsrr.length; i++) {
				for (String string : tsrr[i]) {
					sb.append(string).append('\n');
				}
			}
		}
		System.out.print(sb);
	}
}