카테고리 없음

백준 알파벳 단위로 단어 정렬 1181

벤치마킹 2019. 5. 26. 13:44

백준 1181 단어 정렬 문제

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



MergeSort 를 이용하고 struct 에 operator을 활용해서 좀 더 쉽게..문제 풀이를 하였다.

그리고 중복되는 단어는 그냥 n / n+1 두개만 비교하면 끝 

요것이 핵심 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <stdio.h>
#include <iostream>
 
using namespace std;
 
 
int N;
 
struct Word{
    int  len;
    char word[51];
 
 
    Word &operator =(const Word &org){
        len = org.len;
 
        for (int i = 0; org.word[i]; i++){
            word[i] = org.word[i];
        }
 
        word[len] = 0;
 
        return *this;
    }
 
    bool operator <(const Word &other) const {
 
        if (len != other.len)
            return len < other.len;
 
 
        int i = 0;
        for (i = 0; word[i]; i++){
            if (word[i] != other.word[i])
                return word[i] < other.word[i];
        }
 
        return word[i] < other.word[i];
    }
};
 
 
Word arr[20001];
int input[20001] = { 0, };
 
int j_strcmp(const char *src, const char * dst) {
 
    while (*src != 0 && *src == *dst) {
 
        *src++, *dst++;
    }
 
    return *src - *dst;
}
 
 
int str_len(const char str[]){
 
    int len = 0;
    while (str[len++] != 0)
    {
 
    }
 
    return len - 1;
}
 
//@ ret : 1 ==> a <b 
//         -1 ==> a >b
//          0 ==> a==b
int WordCmp(Word a, Word b){
 
    if (a.len != b.len)
        return a.len < b.len ? 1 : -1;
 
    int ret = j_strcmp(a.word, b.word);
 
    if (ret < 0){
        return 1; // 낮은 순위 알파벳 부터 a < b ;
    }
    else if (ret >0){
        return -1;
    }
    else{
        return 0;
 
    }
 
 
}
 
Word temp[100000];
 
void MergeSort(Word  arr[], int l, int r)
{
 
    int li = l; //시작점 
 
    int half = (l + r) / 2;
    int ri = half + 1; // half +1 부터 시작 
    int idx = l;
 
    if (l == r)
        return;
 
    MergeSort(arr, l, half);
    MergeSort(arr, half + 1, r);
 
 
    while (li <= half && ri <= r){
 
        if (arr[li] < arr[ri])  temp[idx++] = arr[li++];
        else temp[idx++] = arr[ri++];
 
    }
 
    while (li <= half) temp[idx++] = arr[li++];
    while (ri <= r) temp[idx++] = arr[ri++];
 
    //idx 는 l 부터 시작했으니 .결국 시작 포인트는 같게 된다. 
    for (int i = l; i <= r; i++) {
        arr[i] = temp[i];
    }
 
}
 
 
int main(void){
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    //freopen("input.txt", "r", stdin); setbuf(stdout, NULL);
 
    int N;
    cin >> N;
 
    for (int i = 0; i < N; i++){
 
        cin >> arr[i].word;
 
        arr[i].len = str_len(arr[i].word);
        input[i] = i;
 
    }
 
    MergeSort(arr, 0, N - 1);
 
    cout << arr[0].word << "\n";
 
    for (int i = 1; i < N; i++){
 
        if (j_strcmp(arr[i].word, arr[i - 1].word) == 0)
            continue;
        else
            cout << arr[i].word << "\n";
 
    }
 
    return 0;
}
cs


저작자표시 (새창열림)