백준 1181번 단어 정렬

1. 문제

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

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

단, 중복된 단어는 하나만 남기고 제거해야 한다.

입력

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

출력

조건에 따라 정렬하여 단어들을 출력한다.

예제 입력 1 복사

13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

예제 출력 1 복사

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

 

 

2.나의 풀이

comparable을 통해서 풀려고 했다.

strSort라는 클래스를 따로 만들었다. (알고보니 매우 불필요한 행동)

 

사실 나는 String에 compareTo가 있는지 몰랐다. 알고보니 내가 짠 코드는 String compareTo를 직접 구현한거 같다.

 

1. 중복값 미리 제거하기

Set에 String을 담아서 중복 제거한다음 List컬렉션에 옮긴다.

2. 정렬하기

compareTo를 구현해서 정렬한다.

 

import java.util.*;

class strSort implements Comparable<strSort> {
    String str;

    strSort(String str) {
        this.str = str;
    }
    @Override
    public int compareTo(strSort tmp) {
    	//문자열의 길이가 다르다면 문자열 길이 기준으로 오름차순 정렬
        if(this.str.length() != tmp.str.length()) return this.str.length() - tmp.str.length();
        else{ //문자열의 길이가 같다면 문자열의 문자 하나하나씩 비교
            int num = this.str.length();
            for (int i = 0; i < num; i++) {//문자열의 i번째 문자끼리 비교
                int a = this.str.charAt(i); 
                int b = tmp.str.charAt(i);
                if(a!=b) return a - b; 
            }
        }
        return 0;
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<String> set = new HashSet<>();
        for (int i = 0; i < n; i++){
            set.add(new String(sc.next()));
        } //Set에 입력값 저장

        List<strSort> AL = new ArrayList<>();
        Iterator<String> it = set.iterator();
        while (it.hasNext()) {
            AL.add(new strSort(it.next()));
        } //Set에 저장된 값 List에 옮기기
        
        Collections.sort(AL); //정렬

        for (strSort s : AL) {
            System.out.println(s.str);
        }
    }
}

 

 

3.다른 풀이

1. Stream을 이용한 중복 제거 ㅡ> 이것도 String 배열인지 int 배열인지에 따라 다르다

2. String에서 구현한 compareTo를 사용하면 wait와 wont같은 단어도 정렬이 가능하다. 단, 문자열의 길이가 다른 것 끼리는 정렬해주지 못하니 내가 따로 추가해야한다.(Comparator, Comparable)

3. 여기서는 익명객체를 사용했는데 Sort안에서 내가 익명객체를 지정할 수 있음

 

(1) Stream을 이용한 중복제거 String 배열

str = Arrays.stream(str).distinct().toArray(String[]::new);
//toArray를 하면 Object 반환이라서 String[]::new를 해줘야한다.

(2) Stream을 이용한 중복제거 int 배열

arr = Arrays.stream(arr).distinct().toArray(); // [1, 2, 3, 4, 5]

 

코드

import java.util.*;

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

        String[] str = new String[n];
        for (int i = 0; i < n; i++) str[i] = sc.next();

        str = Arrays.stream(str).distinct().toArray(String[]::new);

        Arrays.sort(str, new Comparator<String>() { 
        //익명객체 new Comparator<String>을 (o1, o2) -> 로 바꿔도 된다.(람다식)
            @Override
            public int compare(String o1, String o2) {
                if(o1.length() == o2.length()) return o1.compareTo(o2);
                else return o1.length() - o2.length();
            }
        }
        );
        
        //출력
        for (String s : str) {
            System.out.println(s);
        }
    }
}

 

 

4.얻어갈 점

1. Stream을 이용한 중복 제거 방법

2. String의 compareTo 메서드는 문자열 길이가 같을 때 정렬 해준다.

3. 익명객체 sort메서드 안에서 지정 가능