[백준] 1181 : 단어 정렬 (Comparator, compareTo) - JAVA

백준 단계별 문제풀이 13단계 (정렬)

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

1181번: 단어 정렬

 

 

 

# 문제

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

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

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

 

# 예제

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

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

 

출력

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

 

# 필요개념

 

저번 게시글과 마찬가지로 Comparator를 사용해야한다. Comparator에 대한 설명은 아래 게시글에 자세히 나와있다.

https://wanna-developer02.tistory.com/79

[백준] 11650 : 좌표 정렬하기 (Comparator<int[]> 이차원배열 정렬) - JAVA

 

해당 문제는 문자열을 정렬하는 문제인데, 왜 리턴값이 int형으로 되어있는지 궁금해서 추가로 정리하고자 한다. compare 메소드의 리턴값은 3가지라고 한다.

• 양의 정수
• 0
• 음의 정수

양의 정수라면 위치를 바꾸고, 나머지의 경우에는 위치를 바꾸지 않는다고 한다. a1 - a2 라고 한다면 a1 > a2일 때 양의 정수가 되어 위치를 바꿔준다.  

문자열을 넣을 경우에는 아스키코드로 바꾸어 같은 계산을 한다고 생각하면 된다. A와 B 문자의 경우 A - B는 아스키코드값으로 생각하면 -1이 되므로 자리가 바뀌지 않지만, B - A의 경우엔 바뀌게 된다.

 

문자열 사전순 정렬을 할 땐 그냥 compareTo를 사용해주면 된다.

 

추가로 중복제거의 경우에는 정렬을 마치고 앞뒤 문자를 비교해 다르면 StringBuilder에 넣는 방식으로 구현했다. 처음에 이 방법을 생각 못해서 stream의 distinct메소드를 사용했는데 이 방법을 쓰니 시간이 비교적 오래 걸리는 것을 확인할 수 있었다.

 

# Code

stream의 distinct 메소드 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] str = new String[n];

        for (int i = 0 ; i < n ; i++) {
            str[i] = br.readLine();
        }
        String[] str2 = Arrays.stream(str).distinct().toArray(String[]::new);
        Arrays.sort(str2, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                if (s1.length() != s2.length()) {
                    return s1.length() - s2.length();
                }
                else return s1.compareTo(s2);
            }
        });
        for (int k = 0 ; k < str2.length ; k++) System.out.println(str2[k]);
    }
}

 

for문으로 비교 + StringBuilder 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        String[] str = new String[n];

        for (int i = 0 ; i < n ; i++) {
            str[i] = br.readLine();
        }
        Arrays.sort(str, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                if (s1.length() != s2.length()) {
                    return s1.length() - s2.length();
                }
                else return s1.compareTo(s2);
            }
        });
        sb.append(str[0]).append("\n");
        for (int j = 1 ; j < str.length ; j++) {
            if (!str[j].equals(str[j - 1])) sb.append(str[j]).append("\n");
        }
        System.out.println(sb);
    }
}

 

# 결과

위 : for문 + StringBuilder / 아래 : stream의 distinct