[백준 알고리즘, 정렬] 알고리즘 문제 :: 1181번 단어정렬

안녕하세요 호호만두에요

오늘은 정렬 마지막 문제...

이 문제도 낮은 정답률 37% 답게

푸는데 오래걸렸어요 ㅠㅠㅠ

 

 

제가 알고리즘을 직접 코드를 짜서 풀었는데

답은 맞는것 같은데

계속 되는 시간초과 ㅠㅠㅠㅠ

시간초과 너무 싫어....

그래도 2번만에 풀었어요

 

<백준 알고리즘 1181번 단어정렬>

 

문제

---

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

 

입력

---

첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

---

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

 

**코드는 자바를 이용했습니다**

<시간초과 에러난 코드>

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

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		// 입력할 문자의 개수
		int str_num = scan.nextInt();
		
		// 입력한 문자열
		String [] str_arr = new String[str_num];
		
		//문자 입력받기
		for(int i=0; i<str_num; i++) {
			str_arr[i] = scan.next();
			
		}
		
		ArrayList list = new ArrayList();
		ArrayList length_list = new ArrayList();
		
		//중복되는 문자 제거
		for(int i=0; i<str_num; i++) {
			if(!list.contains(str_arr[i])) {
				length_list.add(str_arr[i].length());
				list.add(str_arr[i]);
			}
			
		}
		
		str_num = length_list.size();
		//입력한 문자들의 길이
		int [] str_length = new int[str_num];
		
		/* arraylist to array */
		for(int i=0; i<str_num; i++) {
			str_length[i] = Integer.parseInt(length_list.get(i).toString());
		}
		
		for(int i=0; i<str_num; i++) {
			str_arr[i] = list.get(i).toString();
		}
		
		
		/* Sorting */
		// 길이 순으로 정렬
		for(int i=0; i<str_num; i++) {
			for(int j=i+1; j<str_num; j++) {
				if(str_length[i] > str_length[j]) {
					int temp = str_length[i];
					str_length[i] = str_length[j];
					str_length[j] = temp;
					
					String str_temp = str_arr[i];
					str_arr[i] = str_arr[j];
					str_arr[j] = str_temp;
				}
				// 길이가 똑같은 문자가 있는 경우
                // 알파벳 하나씩 비교하며 정렬
				else if(str_length[i] == str_length[j]) {
					for(int k=0; k<str_length[i];) {
						if(str_arr[i].charAt(k) > str_arr[j].charAt(k)) {
							String temp = str_arr[i];
							str_arr[i] = str_arr[j];
							str_arr[j] = temp;
							break;
						}
						else if( str_arr[i].charAt(k) == str_arr[j].charAt(k) ) {
							 k++;
						}
						else
							break;
					}
				}
			}
		}
		
        // 결과 출력
		for(int i=0; i<str_num; i++)
			System.out.println(str_arr[i]);
			
		
		scan.close();
	}
}

간단히 설명하면

우선 문자들을 입력받고 중복된 문자를 먼저 제거합니다

그리고 문자들의 길이를 각각 계산해서 다른 배열에 저장하고

그 배열을 이용해서 소팅합니다

이 중에 길이가 같은 문자들은 문자(char) 하나씩 비교하며 정렬해요

이렇게 해서 제출했는데 시간초과 ㅠㅠㅠ

 

그래서 다른 사람들의 코드를 찾아보다가

대박인것을 발견했어요

바로 TreeSet 자료구조!!

 

이를 이용해서 코드의 길이도 절반으로 줄어들고

바로 해결했어요 ㅠㅠㅠ

다음에는 이에 대해 따로 다뤄보려고해요

 

<정답 코드>

import java.util.ArrayList;
import java.util.Collection;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
	
		int str_num = scan.nextInt();
		
		Set<String> str_set = new TreeSet<String>();
		Set<Integer> length_set = new TreeSet<Integer>();
		
		//문자 입력받기
		for(int i=0; i<str_num; i++) {
			String temp = scan.next();
			str_set.add(temp);
			length_set.add(temp.length());
		}
		
		ArrayList<String> str_arr = new ArrayList<String>();
		ArrayList<Integer> length_arr = new ArrayList<Integer>();
		
		str_arr.addAll(str_set);
		length_arr.addAll(length_set);
		
		for(int i = 0; i< length_arr.size(); i++) {
			for(int j=0; j<str_arr.size(); j++) {
				if(length_arr.get(i) == str_arr.get(j).length()) {
					System.out.println(str_arr.get(j));
				}
			}
		}
		
		scan.close();
	}

}

TreeSet 자료구조가 자동으로 중복 제거.

담길때마다 자동으로 정렬(오름차순)되서 담기기 때문에 따로 정렬할 필요도 없어요

짱이죠...

앞으로 유용하게 쓰일 것 같네요

 

잘 보셨으면 댓글과 공감 부탁드려요!!