[JAVA]BOJ 1181, 단어 정렬

문제 자체는 쉽지만 시간복잡도와 arrays.sort, 람다식을 모르면 풀기 어려운 문제이다.

단순히 이중 for문으로 길이와 알파벳순으로 정렬할 수 있지만 시간초과가 난다. 컴퓨터는 1초에 1억번 정도의 연산만 수행할 수 있는데 이중 for문을 사용하면 최대 20,000제곱만큼 계산해야 하기 때문이다.O(n^2)

그래서 고민하다가.. arrays.sort를 할때 조건을 주면 되지않나 싶어서 찾아봤고 문제가 풀렸다.

 

1. 조건에 맞춰 정렬하기

 조건은 길이가 짧은 순으로 정렬하고, 길이가 같으면 알파벳순으로 정렬하는 것이다.

// 길이로 정렬, 길이 같으면 알파벳으로 정렬, 람다식 사용
Arrays.sort(strArr, (s1, s2) -> {  int lengthComparison = Integer.compare(s1.length(), s2.length());
    return lengthComparison != 0 ? lengthComparison : s1.compareTo(s2);
});

 strArr을 정렬할때, 람다식으로 조건을 주었다. 람다식 내용은.. 길이로 정렬을 한다. 길이가 같을때 조건을 삼항연산자로 return에 준다. 

 

 Integer.compare(int x, int y)는 두 정수를 비교하여 x가 y보다 작으면 음수, 같으면 0, 크면 양수를 반환한다. 반환값을 lengthComparison에 저장하고, return에 있는 삼항연산자 조건식으로 길이가 같은지 아닌지 확인한다. 

 

 참이면 lengthComparison을 반환하고, 거짓이면 s1.compareTo(s2)를 반환한다.

s1.compareTo(s2)는 두 문자열을 사전 순서(알파벳순)로 비교하고 두 문자열이 동일하면 0, s1이 s2보다 앞서면 음수, 뒤면 양수를 반환한다.

 

2. 중복없이 출력하기

 정렬할때 삼항연산자를 중복으로 써서 어떻게 중복을 지울 수 있을 것 같긴 했는데... 잘 모르겠어서 쉬운 방법으로 출력했다.

// 중복 없이 출력
System.out.println(strArr[0]);
for(i=1;i<N;i++){
    if(!strArr[i - 1].equals(strArr[i]))
        System.out.println(strArr[i]);
}

단순하다. 그냥 첫번째 String은 출력해주고(당연히 중복이 없으니까), 그 뒤에서부터 중복확인을 한다. 정렬이 되어있기때문에 바로 앞에 항이랑 같으면 출력 안하고, 다른 경우에만 출력한다.

---

아래는 전체 코드이다.

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

public class BOJ1181 {
        public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, i;

        N = Integer.parseInt(br.readLine());
        String[] strArr = new String[N];

        for(i=0;i<N;i++){
            strArr[i] = br.readLine();
        }

        // 길이로 정렬, 길이 같으면 알파벳으로 정렬, 람다식 사용
        Arrays.sort(strArr, (s1, s2) -> {  int lengthComparison = Integer.compare(s1.length(), s2.length());
            return lengthComparison != 0 ? lengthComparison : s1.compareTo(s2);
        });

        // 중복 없이 출력
        System.out.println(strArr[0]);
        for(i=1;i<N;i++){
            if(!strArr[i - 1].equals(strArr[i]))
                System.out.println(strArr[i]);
        }
    }
}