[013] 1181.단어 정렬

 

 

https://www.acmicpc.net/problem/1181

1181번: 단어 정렬

 

 

---

 

나같은 경우는 알고리즘 문제를 풀 때, 문제의 해답을 쭉쭉 적어나간 다음에 생략할 수 있는 부분을 제거해나가는 식으로 풀어나간다. 이 문제도 마찬가지로 진행했다.

 

우선 정렬 조건을 본다.

1. 길이가 짧은 것부터

2. 길이가 같으면 사전 순으로

3. 중복된 단어는 제거한다

 

여기에서 길이같은 경우는 sort()를 통하여 쉽게 해결이 가능하고,

길이가 같을 경우 사전 순으로 비교하여 연산하는 것을 진행한다. 

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] arr = new String[n];

        String temp = "";
        for(int i = 0; i < n; i++){
            arr[i] = sc.next();
        };

        //1. 길이가 짧은 순서대로 정렬
        Arrays.sort(arr, (String fst, String snd) -> fst.length() - snd.length());

        for(int i = 0; i < n; i++){
            // 2. 길이가 같을 경우 사전 순으로 & 중복 제거
            if(i <= n-1){
                for(int j = i+1; j < n-1; j++){
                    if(arr[i].length() == arr[j].length()){
                        if(arr[i].compareTo(arr[j]) > 0){
                            temp = arr[i];
                            arr[i] = arr[j];
                            arr[j] = temp;
                        }else if(arr[i].compareTo(arr[j]) == 0){
                            arr[j] = "";
                        }
                    }
                }
            }else{
                if(arr[i].length() == arr[i-1].length()){
                    if(arr[i].compareTo(arr[i-1]) < 0){
                        temp = arr[i];
                        arr[i] = arr[i-1];
                        arr[i-1] = temp;
                    }else if(arr[i].compareTo(arr[i-1]) == 0){
                        arr[i] = "";
                    }
                }
            }
        }
        // 비어있는 값 제거 후 출력
        for(int i = 0; i < n; i++){
            if(arr[i] != ""){
                System.out.println(arr[i]);
            }
        }
	}
}

 

이게 세가지를 전부 해서 처음 제출한 것인데

당연히 타임오버가 날 수밖에 없다 (...) for문을 티기고티기고티기기 때문에

 

여기에서 이제 코드를 하나씩 줄여나가는 과정을 거친다.

생각해봤을 때, 애초에 길이가 같을 경우 사전 순으로를 먼저 선실행을 하고 나서 길이순 정렬을 해도 결국 결과는 같다

( aa ba abc ab abcd -> aa ab abc abcd ba -> aa ab ba abc abcd )

그렇다는 건 어차피 입력을 받는 처음 for문에서 이전 것과 비교수행을 해나가면 반복문의 길이를 줄일 수 있다.

또한 (어차피 입력받는 김에) 마지막 것까지 연산을 수행해 비교하니 굳이 마지막 else의 길이도 줄일 수 있다.

 

    public void q1181(){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] arr = new String[n];

        String temp = "";
        for(int i = 0; i < n; i++){
            arr[i] = sc.next();
            if(i > 0){
                for(int j = 0; j < i; j++ ){
                    if(arr[i].length() == arr[j].length()){
                        if(arr[i].compareTo(arr[j]) < 0){
                            temp = arr[i];
                            arr[i] = arr[j];
                            arr[j] = temp;
                        }else if(arr[i].compareTo(arr[j]) == 0){
                            arr[j] = "";
                        }
                    }
                }
            }
        };

        //1. 길이가 짧은 순서대로 정렬
        Arrays.sort(arr, (String fst, String snd) -> fst.length() - snd.length());


        // 비어있는 값 제거 후 출력
        for(int i = 0; i < n; i++){
            if(arr[i] != ""){
                System.out.println(arr[i]);
            }
        }

    }

 

짜란. 사실 마지막 for문도 그저 개행입력이면 배열에 하나씩 입력될 때마다 개행문자 붙이면 되지만 그건... 그건 너무 귀찮잖아요