[JAVA_백준 1181] 단어 정렬

📌 문제 탐색하기

주어진 단어를 정렬하는 문제입니다.

첫째, 단어의 길이가 짧은 순서대로 정렬한다.

둘째, 길이가 동일한 경우 사전 순서대로 정렬한다.

셋째, 중복된 단어는 제거

 

📌 가능한 시간복잡도

정렬 - Array.sort( ) 함수 사용하면 시간 복잡도 O(n logn)이고, 중복제거 - 모든 단어를 체크해서 중복된 단어가 있는지 찾아야하므로 O(n)의 시간 복잡도를 갖는다. 따라서 최종 전체 알고리즘의 시간 복잡도는 O(n logn)이라고 생각합니다.

 

📌 코드 설계하기

1. 배열으로 단어들을 입력받는다.

2. 정렬한다. 

    2-1. 단어 길이 기준 정렬

    2-2. 사전 순서 정렬 ( 단어 길이 동일한 경우 )

3. 중복된 단어 제거해야함..... => for문 사용해서 한바퀴 돌면서 단어 체크하고 if문으로 제거시키면 된다. equals() 사용해서!! 

 

📌 정답 코드

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
 
 
public class Main {
	public static void main(String[] args) {
    
		Scanner in = new Scanner(System.in);
 
		int N = in.nextInt();
		String[] arr = new String[N];
 
		in.nextLine(); // \n 제거하기 위해서 반드시 필요함..!! 이거때문에 틀림
 
		for (int i = 0; i < N; i++) {
			arr[i] = in.nextLine();
		}
		
		Arrays.sort(arr, new Comparator<String>() {
			public int compare(String s1, String s2) {
				// 단어 길이가 같을 경우 
				if (s1.length() == s2.length()) {
					return s1.compareTo(s2);
				} 
				else {
					return s1.length() - s2.length();
				}
			}
		});
 
 
		System.out.println(arr[0]);
		
		for (int i = 1; i < N; i++) {
			if (!arr[i].equals(arr[i - 1])) {
				System.out.println(arr[i]);
			}
		}
	}
 
}

 

📌 실수 정리

1회차 : in.nextLine(); 띄어쓰기 제거하기 않아서 틀린거 같음 \n 제거하는 과정이 입력 처리 과정에서 필요함..!!