백준/1181 단어 정렬

단어 정렬

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

119208

49516

36962

40.111%

문제

알파벳 소문자로 이루어진 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

---

풀이

직접 Comparator의 compare를 구현하여  ( 람다식을 이용)

정렬 조건을 지정해주려고했다.

 

길이에 따라 정렬하는데,

길이가 같은경우는 두 단어의 맨앞부터 같은 문자인지 검사한다.

같은 문자가 아니라면 두 문자의 아스키코드 값을 이용해서 정렬한다 ( 사전순으로 정렬하기 위함)

 

수의 크기를 이용해서 정렬하는게 아닌 사전순으로 정렬하는거가 나와서 좀 고민했던 문제이다.

다른사람의 더 깔끔한 코드를 공부해봐야겠다.

 

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());
        Set<String> arraySet = new HashSet<>();

        for (int i = 0; i < n; i++) {
            arraySet.add(br.readLine());
        }
        String[] array = arraySet.toArray(new String[0]);

        Arrays.sort(array, (o1, o2) -> {
            if (o1.length() == o2.length()) {
                for (int i = 0; i < o1.length(); i++) {
                    if (o1.charAt(i) != o2.charAt(i)) {
                        return o1.charAt(i) - o2.charAt(i);
                    }
                }
                return 0;
            } else {
                return o1.length() - o2.length();
            }

        });

        for (String current : array) {
            bw.write(current + "\n");
        }

        bw.flush();
        bw.close();

    }
}

 

시간복잡도

문자열의 길이가 같은경우 두 문자의 길이만큼 반복해서 처리하는 부분이 있었는데

단어의 갯수가 최대 2만개이고, 단어의 최대길이가 50자라서 통과한것 같았다.

 

 

 

 

다른사람의 풀이

자바 Wrapper 클래스(래퍼클래스)에서 사용되는 메소드 .compareTo()를 사용했다.

compareTo를 적용해서 다시 풀어봄.

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.Map.Entry;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());
        Set<String> arraySet = new HashSet<>();

        for (int i = 0; i < n; i++) {
            arraySet.add(br.readLine());
        }
        String[] array = arraySet.toArray(new String[0]);

        Arrays.sort(array, (o1, o2) -> {
            if (o1.length() == o2.length()) {
                return o1.compareTo(o2);
            } else {
                return o1.length() - o2.length();
            }

        });

        for (String current : array) {
            bw.write(current + "\n");
        }

        bw.flush();
        bw.close();

    }
}

정답 통과

 

 

 

 

개념 정리

[Java] compareTo()

[Java] Set [미완]