백준 1181 단어 정렬

 

이 문제를 해결하는 방식은 기본적으로 다음과 같다.

 

1. set을 사용하여 중복을 제거한다.

2. set 사용으로 인해 list형식으로 변환된 값을 다시 배열로 바꾼다.

3. 단어 수에 따라 정렬하고 만약 같다면  알패벳 순으로 정렬한다.

 

시간을 고려하지 않고 코드를 작성한 모습이다.

 

이해에 도움이 될 것이다.

 

import java.util.Arrays;
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        // 입력 받는 개수

        sc.nextLine();
        // 개행

        String arr[] = new String[N];
        // 입력받는 배열

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextLine();
        }
        // N개 입력받음

        Set<String> list = new HashSet<>(Arrays.asList(arr));
        // Set로 바꿈으로서 중복된 값을 제거한다.

        String result[] = list.toArray(new String[0]);
        // Set는 배열이 List이므로 다시 배열로 바꿔준다.

        for (int i = 0; i < result.length - 1; i++) {
            for (int j = 0; j < result.length - 1; j++) {
                if (result[j].length() > result[j + 1].length()) {
                    String tmp = result[j];
                    result[j] = result[j + 1];
                    result[j + 1] = tmp;
                    // 길이별로 배열을 정렬한다.
                    
                } else if (result[j].length() == result[j + 1].length()) {
                    if (result[j].compareTo(result[j + 1]) > 0) {
                    	//compareTo는 현재 객체가 더 작으면 음수, 같으면 0, 크면 양수를 반환한다.
                        // 즉 위 코드는 result[j] result[j]보다 작으면 음수 같으면 0, 크면 양수를 반환한다. 
                        
                        String tmp = result[j];
                        result[j] = result[j + 1];
                        result[j + 1] = tmp;
                        // 0보다 큰 경우에는 result[j]가 더 크다는 의미이므로 자리를 바꾼다.
                    }
                }
            }
        }

       

        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + " ");
        }

        sc.close();
    }

}

 

 

하지만 이 코드는 버블 정렬 방식을 사용하기 때문에 시간초과가 뜬다.

 

따라서 효율적인 Arrays.sort()를 람다식으로 변경하여 같은 결과를 내도록 해보자.

 

import java.util.Arrays;
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        // 입력 받는 개수

        sc.nextLine();
        // 개행

        String arr[] = new String[N];
        // 입력받는 배열

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextLine();
        }
        // N개 입력받음

        Set<String> list = new HashSet<>(Arrays.asList(arr));
        // Set로 바꿈으로서 중복된 값을 제거한다.

        String result[] = list.toArray(new String[0]);
        // Set는 배열이 List이므로 다시 배열로 바꿔준다.

       Arrays.sort(result, (s1, s2) -> {
       		// result배열의 n과 n +1 번째 값을 배교하겠다는 의미.
           
           if (s1.length() != s2.length()) {
               return Integer.compare(s1.length(), s2.length());
               // 두 값의 길이가 다르다면, 두 값을 비교하여
               // s1이 s2와 비교하여 작으면 음수 같으면 0 크면 양수를 반환한다.
               // 양수 0, 음수인지에 따라 Arrays.sort에 의해 정렬될 것이다.
        }
        else{
        	
            return s1.compareTo(s2);
            // 길이가 다르지 않은 경우 즉 같은 경우에는
            // s1, s2를 비교하여 음수, 0, 양수를 반환한다.
        }
       });


        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + " ");
        }

        sc.close();
    }

}

 

 

Arrays.sort()는 효율적인 방법으로 정렬하기에, 위와 같은 람다식으로 정렬한다면 효율적으로 정렬할 수 있다.