[백준 1181] 단어 정렬

문제 출처

사용 언어: Java

1. 구상

• 단어는 일차원 배열에 저장.
• 짧은 길이의 단어순으로 정렬 → 문자열의 길이 비교
• 길이가 같으면 사전순으로 배열 → compareTo() 메소드를 이용하여 사전순으로 배열
  
  

2. 1번째 구현 (시간초과)

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

public class Main {
	
	public static String[] arr; //단어를 저장하는 배열
	public static int num; //배열의 크기
	
    //원소 이동 메소드
	public static void swap(String[] arr, int i, int j) {
		String temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;		
	}
	
    //버블 정렬을 이용
	public static void bubbleSort(String[] arr) {	
		for (int i = arr.length - 1 ; i >= 0; --i) {
			for (int j = 0; j < i; j++) {
            	//단어 길이가 다를 경우
				if (arr[j].length() > arr[j+1].length())
					swap(arr, j, j+1);
                    
				//단어 길이가 같을 경우
				else if(arr[j].length() == arr[j+1].length()) {
               		//사전순으로 정렬하기
					if(arr[j].compareTo(arr[j+1]) > 0)
						swap(arr, j, j+1);
                        
					//동일한 단어일 경우, 배열에서 삭제
					else if (arr[j].compareTo(arr[j+1]) == 0) {
						for (int k = 0; k < num-1; k++)
							arr[k] = arr[k+1];
						num--;
					}
				}
					
					
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
		Scanner s = new Scanner(System.in);	
	
		num = s.nextInt();
		
		arr = new String[num];
		
		for (int i = 0; i < num ; i++)
			arr[i] = s.next();
		
		bubbleSort(arr);
		
		for(int i = 0; i < num; i++)
			System.out.println(arr[i]);
		
		
		
	}
	 

} 

처음에는 bubble-sort를 이용하여 구현함.
그러나 bubble-sort 메소드 내에서 배열 삭제와 길이 동일 조건을 부여하면서 시간이 많이 걸리는 문제가 발생한다고 예상.

3. 2번째 구현

코드 참고 링크

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

public class Main {
	
	public static String[] arr;
	public static int num;
	
	
	public static void main(String[] args) throws Exception {
		Scanner s = new Scanner(System.in);	
	
		num = s.nextInt();
		
		arr = new String[num];
		
		for (int i = 0; i < num ; i++)
			arr[i] = s.next();
		
        //배열 기본 정렬 메소드 이용
		Arrays.sort(arr, new Comparator<String>() {
			//조건을 만족하기 위해 Comparator를 재정의 
            @Override
			public int compare(String a1, String a2) {
				if (a1.length() == a2.length()) {
					return a1.compareTo(a2);
				}
				
				else
					return a1.length() - a2.length();  
			}
		});
		
		System.out.println(arr[0]);
		
        //동일한 단어라면 한 번만 출력하도록 조건 설정
		for(int i = 1; i < num; i++) {
			if(!arr[i].equals(arr[i-1]))
				System.out.println(arr[i]);
		}
			
		
		
		
	}
	 

} 

기본적인 정렬 방법은 시간이 오래걸리는 문제가 있어 타인의 코드를 참고함.
객체를 비교하는 Comparator의 compare 메소드를 조건에 맞추어 재정의함.
단어의 길이가 동일할 경우, compareTo 메소드를 이용하여 사전순으로 정렬.
중복되는 단어는 한 번만 출력할 수 있도록 출력에서 조건을 설정함.