반응형

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

 

19591번: 독특한 계산기

숫자, '+', '*', '-', '/'로만 이루어진 길이가 106 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −263 이상 263 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다. 

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 문자열을 입력받을 str 변수를 선언하고, 입력을 받습니다.

 

2. num을 선언하고, 기호가 아닌 문자가 나오면 num = num * 10 + str[ i ] - '0'을 통해 num을 갱신해 줍니다.

 

3. 기호가 나온다면 deque<char> symbol에 기호를 push_back 해주고, 첫 번째 문자열이 '-'라면 isFirst를 true로 바꾸고, num의 값에 -1을 곱해준 후 deque<ll> number에 num을 push_back 해줍니다.

 

4. 이후 규칙에 맞게 계산을 하고, 답을 출력합니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<deque>
#include<string>
#define ll long long
 
using namespace std;
deque<ll> number;
deque<char> symbol;
ll ans;
 
ll cal(ll num1, ll num2, char sym)
{
    if (sym == '+') {
        return num1 + num2;
    }
    else if (sym == '-') {
        return num1 - num2;
    }
    else if (sym == '*') {
        return num1 * num2;
    }
    else {
        return num1 / num2;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    string str;
 
    cin >> str;
 
    bool isFirst = false;
    ll num = 0;
 
    for (int i = 0; i < str.size(); i++) {
        if (i == 0 && str[i] == '-') {
            isFirst = true;
        }
        else if (str[i] >= '0') {
            num = num * 10 + str[i] - '0';
        }
        else {
            if (isFirst) {
                isFirst = false;
                num *= -1;
            }
            number.push_back(num);
            symbol.push_back(str[i]);
            num = 0;
        }
    }
    if (isFirst) {
        isFirst = false;
        num *= -1;
    }
    number.push_back(num);
 
    if (number.size() == 1) {
        cout << number.front();
        return 0;
    }
 
    while (1) {
        ll tmp[4= { 0 };
 
        if (number.size() == 3) {
            tmp[0= number.front();
            tmp[3= number.back();
            number.pop_back();
            number.pop_front();
            tmp[1= tmp[2= number.front();
        }
        else if (number.size() == 2) {
            tmp[0= number.front();
            tmp[1= number.back();
        }
        else {
            tmp[0= number.front();
            tmp[3= number.back();
            number.pop_back();
            number.pop_front();
            tmp[1= number.front();
            tmp[2= number.back();
        }
 
        if (symbol.size() == 1) {
            char sym = symbol.front();
            cout << cal(tmp[0], tmp[1], sym);
 
            return 0;
        }
        else {
            char sym1 = symbol.front();
            char sym2 = symbol.back();
 
            if (sym1 == '+' || sym1 == '-') {
                if (sym2 == '*' || sym2 == '/') {
                    symbol.pop_back();
                    number.pop_back();
                    number.push_back(cal(tmp[2], tmp[3], sym2));
                    number.push_front(tmp[0]);
                }
                else {
                    ll num1 = cal(tmp[0], tmp[1], sym1);
                    ll num2 = cal(tmp[2], tmp[3], sym2);
 
                    if (num1 >= num2) {
                        symbol.pop_front();
                        number.pop_front();
                        number.push_front(cal(tmp[0], tmp[1], sym1));
                        number.push_back(tmp[3]);
                    }
                    else {
                        symbol.pop_back();
                        number.pop_back();
                        number.push_back(cal(tmp[2], tmp[3], sym2));
                        number.push_front(tmp[0]);
                    }
                }
            }
            else if (sym1 == '*' || sym1 == '/') {
                if (sym2 == '+' || sym2 == '-') {
                    symbol.pop_front();
                    number.pop_front();
                    number.push_front(cal(tmp[0], tmp[1], sym1));
                    number.push_back(tmp[3]);
                }
                else {
                    ll num1 = cal(tmp[0], tmp[1], sym1);
                    ll num2 = cal(tmp[2], tmp[3], sym2);
 
                    if (num1 >= num2) {
                        symbol.pop_front();
                        number.pop_front();
                        number.push_front(cal(tmp[0], tmp[1], sym1));
                        number.push_back(tmp[3]);
                    }
                    else {
                        symbol.pop_back();
                        number.pop_back();
                        number.push_back(cal(tmp[2], tmp[3], sym2));
                        number.push_front(tmp[0]);
                    }
                }
            }
        }
    }
}
cs
반응형
반응형

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

 

20210번: 파일 탐색기

첫 줄에 문자열의 개수 N(2 ≤ N ≤ 10,000)이 주어진다. 그 다음 N줄에 정렬할 문자열이 한 줄에 하나씩 주어진다. 모든 문자열의 길이는 100 이하이며, 알파벳 대소문자와 숫자로만 이루어져 있다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 문자열을 입력받고, arr 배열에 저장합니다.

 

2. cmp 함수를 만들어 문자열을 서로 비교하면서 두 문자열이 모두 숫자가 나온다면 0이 아닌 숫자가 나온 시점부터 string에 넣어줍니다.

 

3. 두 숫자가 같을 때 사이즈가 다르면 사이즈가 더 작은 수를 앞에 두고, 사이즈가 같다면 각 자리 숫자를 비교해 주면서 더 작은 숫자를 앞에 둡니다.

 

4. cmp함수를 통해 arr 배열을 정렬해주고, arr배열을 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<string>
#include<algorithm>
 
using namespace std;
 
int N;
string arr[10000];
 
bool cmp(string left, string right)
{
    if (left == right) return false;
 
    int l = 0, r = 0;
    while (1) {
        if (l == left.size()) {
            return true;
        }
        if (r == right.size()) {
            return false;
        }
 
        if (left[l] <= '9' && right[r] <= '9') {
            int sizeL = 0, sizeR = 0;
            string L, R;
            bool zeroL = false, zeroR = false;
            while (left[l] <= '9' && l < left.size()) {
                if (left[l] != '0' && zeroL == false) {
                    zeroL = true;
                }
                
                if (zeroL) {
                    L += left[l];
                }
 
                l++;
                sizeL++;
            }
 
            while (right[r] <= '9' && r < right.size()) {
                if (right[r] != '0' && zeroR == false) {
                    zeroR = true;
                }
 
                if (zeroR) {
                    R += right[r];
                }
                r++;
                sizeR++;
            }
 
            if (R == L) {
                if (sizeL != sizeR) {
                    return sizeL < sizeR;
                }
            }
            else {
                if (L.size() == R.size()) {
                    for (int i = 0; i < L.size(); i++) {
                        if (L[i] != R[i]) {
                            return L[i] < R[i];
                        }
                    }
                }
                return L.size() < R.size();
            }
            continue;
        }
        
        if (left[l] != right[r]) {
            if (left[l] >= 'a') {
                if (right[r] >= 'a') {
                    return left[l] < right[r];
                }
                else if (right[r] >= 'A') {
                    return left[l] - 'a' < right[r] - 'A';
                }
                else {
                    return false;
                }
            }
            else if (left[l] >= 'A') {
                if (right[r] >= 'a') {
                    return left[l] - 'A' <= right[r] - 'a';
                }
                else if (right[r] >= 'A') {
                    return left[l] < right[r];
                }
                else {
                    return false;
                }
            }
            else {
                if (right[r] >= 'A') {
                    return true;
                }
            }
        }
 
        l++;
        r++;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    sort(arr, arr + N, cmp);
 
    for (int i = 0; i < N; i++) {
        cout << arr[i] << '\n';
    }
}
cs
반응형
반응형

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

 

17609번: 회문

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 문자열을 입력받아 str 변수에 저장합니다.

 

2. s = 0, e = str.size() - 1에서 시작하여 s < e 일 때까지 투포인터를 활용하여 단어가 같다면 s++, e--, 단어가 다르다면 erase flag를 통해 지운 지 지우지 않았는지를 체크하고, s++일 때와 e--일 때를 총 두 번 구해줍니다.

 

3. 만약 erase == false, ans == true라면 0을, erase == true, ans == true라면 1을, 둘 다 아니라면 2를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<string>
 
using namespace std;
 
int T;
bool erase;
 
bool check(string str, int num)
{
    int s = 0, e = str.size() - 1;
 
    while (s < e) {
        if (str[s] == str[e]) {
            s++;
            e--;
        }
        else {
            if (!erase) {
                if (num == 1) {
                    if (str[s + 1== str[e]) {
                        s++;
                        erase = true;
                    }
                }
                else {
                    if (str[s] == str[e - 1]) {
                        e--;
                        erase = true;
                    }
                }
                if (!erase) {
                    return false;
                }
            }
            else {
                return false;
            }
        }
    }
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        erase = false;
        string str;
        cin >> str;
 
        erase = false;
 
        if (check(str, 1)) {
            if (erase) {
                cout << 1;
            }
            else {
                cout << 0;
            }
            cout << '\n';
            continue;
        }
 
        erase = false;
 
        if (check(str, 2)) {
            if (erase) {
                cout << 1;
            }
            else {
                cout << 0;
            }
            cout << '\n';
            continue;
        }
 
        cout << 2;
        cout << '\n';
    }
}
cs
반응형
반응형

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

 

16934번: 게임 닉네임

첫째 줄에 가입한 유저의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 유저의 닉네임이 가입한 순서대로 한 줄에 하나씩 주어진다. 닉네임은 알파벳 소문자로만 이루어져 있고,

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/417

 

[ 자료구조 ] 트라이(Trie)

1. 트라이(Trie) 트라이(Trie)는 다양한 문자열의 집합을 하나의 트리로 표현하는 자료구조입니다. 2. 트라이(Trie) 동작 원리 먼저 그림을 통해 살펴보도록 하겠습니다. 다음 그림은 문자열 {"jade", "ja

rudalsd.tistory.com

 

1. trie를 구현하고, 단어를 입력받을 때마다 해당 문자열을 print를 통해 새로운 문자가 나오거나 문자열의 끝이 오면 해당 문자열을 출력합니다.

 

2. trie에 해당 문자열을 insert 합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
 
struct Trie {
    Trie* arr[26];
    int end;
 
    Trie() {
        for (int i = 0; i < 26; i++) {
            arr[i] = NULL;
        }
 
        end = 0;
    }
 
    ~Trie() {
        for (int i = 0; i < 26; i++) {
            if (arr[i]) delete arr[i];
        }
    }
 
    void insert(const char* ch) {
        char temp = *ch - 'a';
        if (!*ch) {
            end++;
            return;
        }
 
        if (arr[temp] == NULL) arr[temp] = new Trie;
        arr[temp]->insert(ch + 1);
    }
 
    void print(const char* ch) {
        char temp = *ch - 'a';
        if (!*ch) {
            if (end) {
                cout << end + 1;
            }
            cout << '\n';
            return;
        }
 
        cout << *ch;
 
        if (arr[temp] == NULL) {
            cout << '\n';
            return;
        }
 
        arr[temp]->print(ch + 1);
    }
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    Trie* root = new Trie;
 
    for (int i = 0; i < N; i++) {
        char ch[11];
        cin >> ch;
 
        root->print(ch);
        root->insert(ch);
    }
}
cs
반응형
반응형

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

 

7432번: 디스크 트리

갑자기 맥북이 상근이의 손에서 떨어졌고, 화면이 켜지지 않았다. AS센터에 문의해보니 수리비가 97만원이 나왔고, 상근이는 큰 혼란에 빠졌다. 돈도 중요하지만, 상근이는 그 속에 들어있는 파

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/417

 

[ 자료구조 ] 트라이(Trie)

1. 트라이(Trie) 트라이(Trie)는 다양한 문자열의 집합을 하나의 트리로 표현하는 자료구조입니다. 2. 트라이(Trie) 동작 원리 먼저 그림을 통해 살펴보도록 하겠습니다. 다음 그림은 문자열 {"jade", "ja

rudalsd.tistory.com

 

1. trie를 구현하고, 단어를 입력받을 때마다 해당 문자열을 trie에 insert 합니다.

 

2. root부터 오름차순으로 폴더이름을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<map>
#include<string>
 
using namespace std;
 
int N;
 
struct Trie {
    map<string, Trie *> m;
 
    void insert(vector<string> vect, int level) {
        if ((int)vect.size() > level) {
            if (!m.count(vect[level])) {
                m[vect[level]] = new Trie;
            }
 
            m[vect[level]]->insert(vect, level + 1);
        }
    }
 
    void print(int level) {
        if (m.empty()) return;
        for (auto& next : m) {
            for (int i = 0; i < level; i++) {
                cout << ' ';
            }
            cout << next.first << '\n';
            next.second->print(level + 1);
        }
    }
};
 
vector <string> split(string str) {
    vector <string> ret;
    
    int s = 0;
    int e = 0;
 
    while (1) {
        e = str.find('\\', s);
        if (e == -1) {
            ret.push_back(str.substr(s, str.size() - s));
            break;
        }
        else {
            ret.push_back(str.substr(s, e - s));
            s = e + 1;
        }
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    Trie* root = new Trie;
 
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        
        vector<string> vect = split(str);
 
        root->insert(vect, 0);
    }
 
    root->print(0);
}
cs
반응형
반응형

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

 

2800번: 괄호 제거

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수식을 입력받아 각 괄호에 번호를 붙입니다.

 

2. 조합을 이용하여 각 괄호들을 제거해주고, set 자료구조에 저장하여 중복을 제거해줍니다.

 

3. 저장된 답을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<string>
#include<stack>
#include<set>
 
using namespace std;
 
string str;
int arr[200];
set<string> ans;
int visited[11];
int cnt;
 
void dfs(int limit, int level, int num)
{
    if (level == limit) {
        string temp = "";
        for (int i = 0; i < str.size(); i++) {
            if (visited[arr[i]] != 1) {
                temp += str[i];
            }
        }
 
        ans.insert(temp);
        return;
    }
 
    for (int i = num; i <= cnt; i++) {
        visited[i] = 1;
        dfs(limit, level + 1, i + 1);
        visited[i] = 0;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> str;
    stack<int> s;
 
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            cnt++;
            arr[i] = cnt;
            s.push(cnt);
        }
        else if (str[i] == ')') {
            arr[i] = s.top();
            s.pop();
        }
    }
 
    for (int i = 1; i <= cnt; i++) {
        dfs(i, 01);
    }
 
    for (auto& next : ans) {
        cout << next << '\n';
    }
}
cs
반응형
반응형

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

 

5430번: AC

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 값들을 입력받고, 전처리를 통해서 배열의 값들을 deque에 넣어줍니다.

 

2. R이 입력되면 rev변수를 갱신해 줍니다.

 

3. rev변수의 값에 따라 pop_back, 혹은 pop_front를 해줍니다.

 

4. deq에 남아있는 수를 rev변수에 따라 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<deque>
#include<string>
 
using namespace std;
 
int T;
deque<int> deq;
 
void preproc(string x)
{
    int num = 0;
    for (auto next : x) {
        if (next >= '0' && next <= '9') {
            num *= 10;
            num += next - '0';
        }
        else if (next == ']' || next == ',') {
            deq.push_back(num);
            num = 0;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        bool flag = true;
        bool rev = false;
        deq.clear();
        string p, x;
        int n;
        cin >> p >> n >> x;
 
        if (n) preproc(x);
 
        for (auto com : p) {
            if (com == 'R') {
                rev = !rev;
            }
            else {
                if (!deq.empty()) {
                    if (rev) {
                        deq.pop_back();
                    }
                    else {
                        deq.pop_front();
                    }
                }
                else {
                    cout << "error\n";
                    flag = false;
                    break;
                }
            }
            
        }
 
        if (flag) {
            cout << '[';
            while (!deq.empty()) {
                if (rev) {
                    if (deq.size() == 1) {
                        cout << deq.back();
                    }
                    else {
                        cout << deq.back() << ',';
                    }
                    deq.pop_back();
                }
                else {
                    if (deq.size() == 1) {
                        cout << deq.front();
                    }
                    else {
                        cout << deq.front() << ',';
                    }
                    deq.pop_front();
                }
            }
            cout << "]\n";
        }
    }
}
cs
반응형
반응형

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

 

5052번: 전화번호 목록

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/417

 

[ 자료구조 ] 트라이(Trie)

1. 트라이(Trie) 트라이(Trie)는 다양한 문자열의 집합을 하나의 트리로 표현하는 자료구조입니다. 2. 트라이(Trie) 동작 원리 먼저 그림을 통해 살펴보도록 하겠습니다. 다음 그림은 문자열 {"jade", "ja

rudalsd.tistory.com

 

1. trie를 구현하고, 단어를 입력받을 때마다 해당 문자열이 trie에 있는지 체크하고, 있다면 NO를 출력하고, 그렇지 않다면 YES를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int n, t;
 
struct trie {
    trie* num[10];
    bool end;
 
    trie() {
        end = false;
        for (int i = 0; i < 10; i++) num[i] = NULL;
    }
    ~trie() {
        for (int i = 0; i < 10; i++) {
            if(num[i]) delete num[i];
        }
    }
 
    void insert(const char* ch) {
        if (!*ch) {
            this->end = true;
            return;
        }
 
        int now = *ch - '0';
        if (!num[now]) num[now] = new trie;
        num[now]->insert(ch + 1);
    }
 
    bool find(const char* ch) {
        if (!*ch || end) {
            return true;
        }
 
        int now = *ch - '0';
        if (!num[now]) return false;
        return num[now]->find(ch + 1);
    }
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    while (t--) {
        trie* root = new trie;
        bool flag = true;
 
        cin >> n;
 
        for (int i = 0; i < n; i++) {
            char arr[11];
            cin >> arr;
 
            if (root->find(arr)) {
                if(flag) cout << "NO\n";
                flag = false;
            }
            else {
                root->insert(arr);
            }
        }
 
        if (flag) {
            cout << "YES\n";
        }
 
        delete root;
    }
}
cs
반응형
반응형

1. 트라이(Trie)

 

트라이(Trie)는 다양한 문자열의 집합을 하나의 트리로 표현하는 자료구조입니다.

 

2. 트라이(Trie) 동작 원리

먼저 그림을 통해 살펴보도록 하겠습니다.

다음 그림은 문자열 {"jade", "japp", "an", "answer"}를 트라이(Trie)로 구현한 것입니다.

 

 

3. 트라이(Trie) 구현

트라이의 노드는 자손 노드를 가리키는 포인터 배열과, 문자열의 끝인지를 나타내는 bool 변수로 구성되어 있습니다.

보통 영어 소문자로만 이루어딘 경우가 대부분이기 때문에 배열의 크기를 26으로 선언합니다.

동적으로 메모리를 할당하기 때문에 delete로 해제해주는 것이 매우 중요합니다.

이제 문자열을 트라이에 넣어주는 함수에 대해 알아보겠습니다.

이미 트라이에 해당 문자에 해당하는 노드가 있다면 따라가고, 그렇지 않다면 새로 만들어줍니다.

문자열의 끝에 도달하면 end의 값을 true로 바꾸어줍니다.

마지막으로 트라이에서 찾고자 하는 문자열이 있는지 탐색하는 함수에 대해 알아보겠습니다.

만약 다음 문자로 가는 노드가 존재하지 않는다면 존재하지 않는 단어입니다.

또한, 문자열의 끝에 도달했을 때 end의 값이 true가 아니라면 존재하지 않는 단어입니다.

 

[ 소스코드 ]

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
struct trie {
    trie* ch[26];
    bool end;
 
    trie() {
        end = false;
        for (int i = 0; i < 10; i++) ch[i] = NULL;
    }
    ~trie() {
        for (int i = 0; i < 10; i++) {
            if(num[i]) delete ch[i];
        }
    }
 
    void insert(const char* c) {
        if (!*c) {
            this->end = true;
            return;
        }
 
        int now = *- '0';
        if (!num[now]) num[now] = new trie;
        num[now]->insert(c + 1);
    }
 
    bool find(const char* c) {
        if (!*|| end) {
            return true;
        }
 
        int now = *- '0';
        if (!num[now]) return false;
        return num[now]->find(c + 1);
    }
};
 
cs
반응형
반응형

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

 

7490번: 0 만들기

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 백트래킹을 이용해 실시간으로 계산값들을 저장하고, 각 인덱스에 저장되어 있는 부호가 무엇인지 저장합니다.

 

2. 만약 계산값이 0이라면 vector<stirng> ans에 숫자와 부호를 push합니다.

 

3. ans를 오름차순으로 정렬하고, 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
 
using namespace std;
 
int N;
int ret = 0;
char box[10];
vector<string> ans;
 
void dfs(int level, int num, int idx)
{
    if (level == N + 1) {
        if (num != 0) {
            if (box[idx] == '-') {
                ret -= num;
            }
            else {
                ret += num;
            }
        }
        if (ret == 0) {
            string temp;
            for (int i = 1; i <= N; i++) {
                temp += '0' + i;
                temp += box[i];
            }
            ans.push_back(temp);
        }
        if (num != 0) {
            if (box[idx] == '-') {
                ret += num;
            }
            else {
                ret -= num;
            }
        }
        return;
    }
 
    num = num * 10 + level;
 
    if (N != level) {
        if (box[idx] == '-') {
            ret -= num;
            box[level] = '+';
            dfs(level + 10, level);
            box[level] = '-';
            dfs(level + 10, level);
            ret += num;
            box[level] = 0;
        }
        else {
            ret += num;
            box[level] = '+';
            dfs(level + 10, level);
            box[level] = '-';
            dfs(level + 10, level);
            ret -= num;
            box[level] = 0;
        }
    }
 
    box[level] = ' ';
    dfs(level + 1, num, idx);
    box[level] = 0;
 
    return;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int T;
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        ans.clear();
        cin >> N;
 
        dfs(1,0,0);
 
        sort(ans.begin(), ans.end());
 
        for (auto& next : ans) {
            cout << next << '\n';
        }
 
        cout << '\n';
    }
}
cs

 

반응형

+ Recent posts