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

 

안그래도 문자열에 약한데 애드혹까지 섞이니 뇌정지가 오는 문제였습니다.

우선 문자열이 섞여있는 채로 저장되어있고,  문자열이 어떤 수들로 구성되어 있는지 파악해야 합니다.

그러면 각 숫자들의 고유한 알파벳을 구해서 카운팅하는 방법을 떠올릴 수 있습니다.

 

0 2 4 6 8은 각각 고유한 알파벳이 있습니다.

0 - Z

2 - W

4 - U

6 - X

8 - G

 

그리고 이들을 제외한 숫자들 중 고유한 알파벳을 뽑으면

3 - H

5 - F

7 - S

9 - I

1 - O

순서대로 이렇게 가져올 수 있습니다.

 

먼저 입력으로 들어온 문자열의 문자들을 모두 카운팅합니다.

이후 위에서 구한 알파벳을 순서대로 가져와서 카운팅을 빼주면서 정답을 구하는 방식으로 구현했습니다.

 

 

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 <cstring>
#define MAX 10
using namespace std;
 
string str;
string alpha[MAX] = { "ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE" };
pair<int, char> ch[MAX] = { {0,'Z'}, {2,'W'}, {4, 'U'}, {6, 'X'}, {8, 'G'}, {3,'H'}, {5, 'F'}, {7, 'S'}, {9, 'I'}, {1,'O'} };
int alphaCnt[26];
int cnt[MAX];
int len;
 
void solve() {
    for (auto c : ch) {
        while (alphaCnt[c.second - 'A']) {
            cnt[c.first]++;
            for (auto a : alpha[c.first]) {
                alphaCnt[a - 'A']--;
            }
        }
    }
}
 
void func(int tc) {
    for (auto x : str) {
        alphaCnt[x - 'A']++;
    }
    solve();
 
    cout << "Case #" << tc << ": ";
    for (int i = 0; i < MAX; i++) {
        while (cnt[i]--) {
            cout << i;
        }
    }
    cout << '\n';
}
 
void input() {
    cin >> str;
    len = str.size();
}
 
void init() {
    memset(cnt, 0, sizeof(cnt));
    memset(alphaCnt, 0, sizeof(alphaCnt));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        input();
        func(t);
        init();
    }
 
    return 0;
}
 cs

'algorithm > ad-hoc' 카테고리의 다른 글

boj 16161 가장 긴 증가하는 팰린드롬 부분수열  (0) 2024.08.15
boj 24553 팰린드롬 게임  (0) 2024.08.07
boj 21316 스피카  (0) 2024.08.05
boj 10350 Banks  (0) 2024.07.31
boj 5527 전구 장식  (0) 2024.07.30

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

 

문제 키워드에 애드혹이 있던데 잘은 모르겠습니다.

제가 이 로직으로 접근하기 위해 생각한것 자체가 애드혹이 될 수는 있겠네요!

 

1. ab 는 좋은 문자열이다.
2. 만약 문자열 [S]가 좋은 문자열이라면, 오른쪽과 왼쪽 끝에 각각 a와 b를 추가한 문자열 a[S]b 또한 좋은 문자열이다.
3. 만약 문자열 [S]와 [T]가 좋은 문자열이라면 이들을 붙여 쓴 [S][T] 또한 좋은 문자열이다.

좋은 문자열의 정의가 이렇게 나옵니다.

그리고 입력으로 좋은 문자열 A, B가 주어지고, A -> B의 최소 연산 횟수를 구해야합니다.

 

우선 위 정의를 보고 알 수 있는건 "두 문자열의 구성은 같다" 입니다.

ab = S는 좋은 문자열이며, aSb도 좋은 문자열입니다. 그리고 SS도 좋은 문자열입니다.

여기서 사용된 a과 b의 갯수는 같습니다.

 

그렇다면 생각해볼 예외는 "두 문자열의 길이가 다른 경우" 입니다.

두 문자열의 길이가 다르다면 당연히 A -> B가 성립하지 않겠죠.

 

문제의 로직은

a, b의 갯수가 둘다 동일하기 때문에 b의 위치를 각각 찾습니다.

그리고 b 위치의 차이를 더합니다.

b의 갯수도 당연히 똑같기 때문에 하나라도 문자열의 길이를 벗어나면 종료할 수 있습니다.

 

 

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
#include <iostream>
using namespace std;
 
string x, y;
int len1, len2;
 
void func() {
    if (len1 != len2) {
        cout << "-1\m";
        return;
    }
 
    int ret = 0;
    int idx1 = 0;
    int idx2 = 0;
    while (1) {
        while (idx1 < len1 && x[idx1] == 'a') idx1++;
        while (idx2 < len2 && y[idx2] == 'a') idx2++;
        if (idx1 >= len1 || idx2 >= len2) break;
        ret += abs(idx1++ - idx2++);
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> x >> y;
    len1 = x.size();
    len2 = y.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
    }
 
    return 0;
}
 cs

'algorithm > String' 카테고리의 다른 글

boj 9081 단어 맞추기  (0) 2021.12.15
boj 10096 세 친구  (0) 2021.01.29

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

 

9081번: 단어 맞추기

입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알

www.acmicpc.net

문자열이지만 순열에 더 가까운 문제입니다.

주어진 단어의 사전 순으로 바로 다음 단어를 출력하는 문제로, next_permutation을 이용하였습니다.

next_permutation으로 다음 순열을 구하고, 출력하면 됩니다.

만약 마지막 단어라서 다음 순열을 구하지 못하더라도 주어진 단어를 유지하므로 그냥 출력해줍니다.

c++ 내장의 next_permutation을 사용하면 됐지만 직접 구현해보았습니다.

 

 

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
#include <iostream>
#include <string>
using namespace std;
 
string str;
int N;
 
bool nextPermutation() {
    int i = N - 1;
 
    while (i > 0 && str[i - 1] >= str[i]) {
        i--;
    }
 
    if (!i) return false;
 
    int j = N - 1;
    while (str[i - 1] >= str[j]) j--;
 
    swap(str[i - 1], str[j]);
 
    int k = N - 1;
    while (i < k) swap(str[i++], str[k--]);
 
    return true;
}
 
void func() {
    nextPermutation();
 
    cout << str << '\n';
}
 
void input() {
    cin >> str;
    N = str.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
    }
 
    return 0;
}
 cs

'algorithm > String' 카테고리의 다른 글

boj 10453 문자열 변환  (0) 2024.07.24
boj 10096 세 친구  (0) 2021.01.29

 

www.acmicpc.net/problem/1525

 

1525번: 퍼즐

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

www.acmicpc.net

3 * 3 퍼즐을 이동시켜서 위와같은 상태로 만들고, 이동의 최소 횟수를 출력하고, 불가능한 경우 -1를 출력합니다.

 

저는 3 * 3 퍼즐을 String으로 변환시켰습니다.

1 0 3
4 2 5
7 8 6

입력이 이렇게 주어지면 "103425786"을 만든 다음 bfs를 돌렸습니다. (방문체크도 Set<String>으로 하였습니다.)

그리고 각 칸에서 움직일 수 있는 공간을 ArrayList배열을 만들어서 모두 만들어줍니다.

왼쪽 위 칸 번호가 0번부터 시작해서 오른쪽 아래 칸 번호가 8번이되어 

0 -> 1, 3

1 -> 0, 2, 4

2 -> 1, 5

3 -> 0, 4, 6

4 -> 1, 3, 5, 7

5 -> 2, 4, 8

6 -> 3, 7

7 -> 4, 6, 8

8 -> 5, 7

이렇게 그래프를 연결시킬 수 있습니다.

 

이제 bfs를 돌려줍니다.

덱에 입력받은 문자열(str), 0의 위치(idx), 움직인 횟수(cnt)를 넣어줍니다.

bfs 과정에서는 현재 문자열에서 idx위치와 next위치의 문자열을 서로 바꿔줍니다.

그리고 중복체크를 하고, 덱에 넣어주는 방식으로 하였습니다.

 

덱에서 꺼낸 문자열이 ans인 "123456780"과 같으면 cnt를 출력하고 리턴합니다.

만약 ans와 같은 문자열이 나오지 않았는데 덱이 비어있게되면 "123456780"을 만들수 없으므로 -1을 출력합니다.

 

 

[C++]

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
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>
using namespace std;
 
typedef struct list {
    string now;
    int idx;
    int cnt;
}list;
 
queue<list> q;
set<string> s;
vector<int> v[9];
string ans = "123456780", str = "";
 
void init() {
    v[0].push_back(1);
    v[0].push_back(3);
 
    v[1].push_back(0);
    v[1].push_back(2);
    v[1].push_back(4);
 
    v[2].push_back(1);
    v[2].push_back(5);
 
    v[3].push_back(0);
    v[3].push_back(4);
    v[3].push_back(6);
 
    v[4].push_back(1);
    v[4].push_back(3);
    v[4].push_back(5);
    v[4].push_back(7);
 
    v[5].push_back(2);
    v[5].push_back(4);
    v[5].push_back(8);
 
    v[6].push_back(3);
    v[6].push_back(7);
 
    v[7].push_back(4);
    v[7].push_back(6);
    v[7].push_back(8);
 
    v[8].push_back(5);
    v[8].push_back(7);
}
 
void bfs() {
    while (!q.empty()) {
        string now = q.front().now;
        int idx = q.front().idx;
        int cnt = q.front().cnt;
        q.pop();
 
        if (!now.compare(ans)) {
            cout << cnt << '\n';
            return;
        }
 
        for (int i = 0; i < v[idx].size(); i++) {
            int next = v[idx][i];
            string tmp = now;
            swap(tmp[idx], tmp[next]);
 
            if (s.find(tmp) != s.end()) continue;
 
            q.push({ tmp, next, cnt + 1 });
            s.insert(tmp);
        }
    }
 
    cout << "-1\n";
}
 
void input() {
    int k = 0;
    string tmp = "";
    for (int i = 0; i < 9; i++) {
        cin >> tmp;
        str += tmp;
 
        if (tmp[0] == '0') {
            k = i;
        }
    }
 
    q.push({ str, k, 0 });
    s.insert(str);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    init();
    input();
    bfs();
 
    return 0;
}
 cs

 

 

[Java]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main {
    static class Pair {
        String now;
        int idx;
        int cnt;
 
        public Pair(String now, int idx, int cnt) {
            this.now = now;
            this.idx = idx;
            this.cnt = cnt;
        }
    }
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static String ans = "123456780";
    static ArrayList<Integer> list[] = new ArrayList[9];
    static String str = "";
 
    static void init() {
        for (int i = 0; i < 9; i++)
            list[i] = new ArrayList<>();
 
        list[0].add(1);
        list[0].add(3);
 
        list[1].add(0);
        list[1].add(2);
        list[1].add(4);
 
        list[2].add(1);
        list[2].add(5);
 
        list[3].add(0);
        list[3].add(4);
        list[3].add(6);
 
        list[4].add(1);
        list[4].add(3);
        list[4].add(5);
        list[4].add(7);
 
        list[5].add(2);
        list[5].add(4);
        list[5].add(8);
 
        list[6].add(3);
        list[6].add(7);
 
        list[7].add(4);
        list[7].add(6);
        list[7].add(8);
 
        list[8].add(5);
        list[8].add(7);
    }
 
    static void bfs() {
        Set<String> s = new HashSet<>();
        Deque<Pair> dq = new ArrayDeque<>();
        dq.add(new Pair(str, str.indexOf("0"), 0));
        s.add(new String(str));
        while (!dq.isEmpty()) {
            String now = dq.peek().now;
            int idx = dq.peek().idx;
            int cnt = dq.poll().cnt;
 
            if (now.equals(ans)) {
                System.out.println(cnt);
                return;
            }
 
            for (int i = 0; i < list[idx].size(); i++) {
                int next = list[idx].get(i);
                char newstr[] = new String(now).toCharArray();
                char tmp = newstr[idx];
                newstr[idx] = newstr[next];
                newstr[next] = tmp;
 
                String s1 = String.valueOf(newstr);
                if (s.contains(s1))
                    continue;
 
                dq.add(new Pair(s1, next, cnt + 1));
                s.add(new String(s1));
            }
        }
 
        System.out.println(-1);
    }
 
    static void input() throws Exception {
        for (int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                str += st.nextToken();
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        init();
        input();
        bfs();
    }
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 11559 Puyo Puyo  (0) 2021.02.26
boj 15653 구슬 탈출 4  (0) 2021.02.22
boj 7576 토마토  (0) 2021.02.19
boj 17135 캐슬 디펜스  (0) 2021.02.17
boj 16236 아기 상어  (0) 2021.02.14

+ Recent posts

티스토리툴바