[백준 1181] 단어 정렬 (C++/Java)

첫번째 풀이 : map / multipmap

두번째 풀이 : vector

방법 1. map / multimap

map은 파이썬의 딕셔너리와 비슷한데 key-value가 쌍을 이루어 저장되는 자료구조이다.

map에 관해서는 자세히 설명해놓으신 분들이 많으니 구글에서 검색하는 것을 추천하고..

해당 문제에서 map을 이용하여 푼 이유는 '같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력된다'는 제한조건 때문이다. 

따라서 입력받을 때는 key : 입력받은 문자열, value : 문자 크기로 입력받았다.

그리고 정렬을 할 때는 반대로 sort-by-value, 즉 value값으로 정렬을 해주면 되는데 여기서 주의할 점은 value 값은 중복이 가능하다는 점이다. 

more, wait처럼 value 값이 같을 수 있기 때문에 key값이 중복 허용되는 multimap을 이용하여 정렬한다.

- c++

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
map<string, int> m;
void sort(map<string, int>& M){ 
  
    // multimap 선언
    multimap<int, string> MM; 
  
    // m으로부터 key-value 하나씩 꺼내서 value-key 값으로 넣기
    for (auto& it : M) { 
        MM.insert({ it.second, it.first }); 
    } 
  
    // 프린트하기
    for (auto& it : MM) { 
        cout << it.second << "\n"; 
    } 
} 
int main(void){
    ios_base :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    string temp;
    for(int i=0; i<n; i++){
        cin >> temp;
        m.insert(make_pair(temp, temp.size()));
    }
 
    sort(m);
 
    return 0;
}

아래처럼 multimap을 전역으로 선언해도 상관없다.

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
map<string, int> m;
multimap<int, string> mm;
void sort(map<string, int>& M) { 
    for (auto& it : M) { 
        mm.insert({ it.second, it.first }); 
    } 
} 
int main(void){
    ios_base :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n; string temp;
    cin >> n;
    
    for(int i=0; i<n; i++){
        cin >> temp;
        m.insert(make_pair(temp, temp.size()));
    }
 
    sort(m);
 
    for (auto& it : mm)
        cout << it.second << "\n"; 
 
    return 0;
}

방법 2. vector

사실 map에 비해 훨씬 쉬울수도 있다.

일단 입력받은대로 벡터에 전부 저장한 다음 크기 순으로 정렬한 후에 중복값을 체크해서 출력하면 되기 때문이다.

다만 출력에서 조금 헷갈린게 i가 마지막까지 갈 때 23번째 줄에서 왜 에러가 발생안하는지 정확하게는 모르겠다.

순서 :           0       1         2      3            4        5           6               7            8            9            10              11                12

정렬된 벡터 : i   |   im   |   it   |   no   |   no   |   but   |   more   |   more   |   wait   |   wont   |   yours   |   cannot   |   hesitate

즉 i가 12인 상태에서  v[i+1].second이면 v[13].second에 접근하게 되는건데 범위를 넘어가게 되는건데 에러가 안 나서 당황;

찾아보니 []는 범위검사를 하지 않으며 예외처리를 발생시키지 않는다고 하는게 그럼 쓰레기 값도 안 걸리는건가 싶고..

(잘 아시는 분 있으면 댓글로 설명해주시면 감사하겠습니다.)

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
vector<pair<int, string>> v;
 
int main(void){
    ios_base :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n; string temp;
    cin >> n;
    
    for(int i=0; i<n; i++){
        cin >> temp;
        v.push_back(make_pair(temp.size(), temp));
    }
 
    sort(v.begin(), v.end());
 
    for(int i=0; i<v.size(); i++){
        if(v[i].second == v[i+1].second)
            continue;
        cout << v[i].second << "\n";
    }
 
    return 0;
}

그리고 여기까지 풀고 java로도 풀려고 했는데 c++의 pair가 없으니 너무 불편했다.

클래스로 직접 만들어도 되겠지만 이렇게 비효율적으로 푸는 문제는 아닌거 같아서 다른 분들은 어떻게 풀었나 하고 보니 

st_님이 너무 깔끔하게 푸셔서 그대로 제출했다. 람다식 공부해야지..

자세한 설명은 st_님 블로그 가서 참고하시길

- java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
 
 
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[] arr = new String[N];
 
        for (int i = 0; i < N; i++) 
            arr[i] = br.readLine();
        
        Arrays.sort(arr, new Comparator<String>() {
            public int compare(String s1, String s2) {
                // 단어 길이가 같을 경우 
                if (s1.length() == s2.length()) {
                    return s1.compareTo(s2);
                } 
                // 그 외의 경우 
                else {
                    return s1.length() - s2.length();
                }
            }
        });
 
        StringBuilder sb = new StringBuilder();
 
        sb.append(arr[0]).append('\n');
        
        for (int i = 1; i < N; i++) {
            // 중복되지 않는 단어만 출력
            if (!arr[i].equals(arr[i - 1])) {
                sb.append(arr[i]).append('\n');
            }
        }
        System.out.println(sb);
    }
}