[BaekJoon] #1181 - 단어 정렬 [Java][C++]

문제 링크

---

1. 아이디어

길이가 짧은 것부터, 길이가 같으면 사전 순으로 정렬해서 출력하는 문제로 중복된 단어는 하나만 남기고 제거해야 한다. 조건에 맞춰 정렬을 먼저 하고 출력 과정에서 이전 단어와 현재 단어가 동일하면 출력하지 않고 넘어가고 다르면 출력하고 이전 단어를 현재 단어로 갱신하면 된다. 집합을 활용해서 먼저 중복을 제거해도 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \times L \log N)$	$O(N \times L)$

($N$ = 입력값 n, $L$ = 단어 길이의 최댓값)

---

3. 코드

풀이 [Java][C++]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        String[] arr = new String[n];
        for (int i = 0; i < n; i++) {
            arr[i] = br.readLine();
        }
        Arrays.sort(arr, (o1, o2) -> {
            if (o1.length() != o2.length()) return Integer.compare(o1.length(), o2.length());
            return o1.compareTo(o2);
        });

        String prv = "";
        for (String s : arr) {
            if (s.equals(prv)) continue;

            bw.write(s);
            bw.newLine();
            prv = s;
        }

        bw.flush();
    }
}

compareTo 메서드가 사전순 정렬인 점을 활용해서 람다식을 구성했다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<string> v(n);
    for (string& x : v) cin >> x;
    sort(v.begin(), v.end(), [](auto& a, auto& b) {
        if (a.size() != b.size()) return a.size() < b.size();
        return a < b;
    });

    string prv;
    for (string& s : v) {
        if (s == prv) continue;

        cout << s << '\n';
        prv = s;
    }
}

a < b가 사전순 정렬인 점을 활용해서 람다식을 구성했다.

---