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/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

matches 메소드와 정규식을 이용하여 해당 문자열이 정수인지 확인할 수 있습니다.

 

str.matches("-?\\d+")

=> 참이면 true, 거짓이면 false를 리턴합니다.

1
2
3
if(price != null && !price.matches("-?\\d+")) {
    System.out.println("price 정수 아님");
}
 cs

 

'Etc' 카테고리의 다른 글

TypeScript 설치  (0) 2021.08.30
Windows 10 에서 WSL을 이용한 우분투 설치  (0) 2021.08.29
C++ cout 소수점 고정  (0) 2021.08.05
localStorage를 이용한 데이터 저장  (0) 2021.05.11
Java 소수점 자리출력  (0) 2021.03.03

www.acmicpc.net/problem/10096

 

10096번: 세 친구

준규, 해빈, 진욱이는 다음과 같은 게임을 한다. 먼저, 준규가 문자열 S를 고른다. 그 다음, 해빈이는 S의 뒤에 S를 붙인 새로운 문자열 T를 만든다. 마지막으로 진욱이는 문자열 T의 어딘가(시작이

www.acmicpc.net

문자열 S가 2번 반복되어있는 문자열에 문자 하나를 무작위로 넣었습니다.

 

이렇게 완성된 문자열에서 문자열 S를 찾는 문제입니다.

 

일단 같은 문자열이 2번 반복되어있기때문에 주어지는 입력은 홀수개의 문자로 이루어져 있습니다. (2n+1개)

저는 이 문자열은 앞에서부터

n, n+1개로 끊은 문자열 2개

n+1, n개로 끊은 문자열 2개

이렇게 그룹을 나누었습니다.

 

나눈 문자열을 순차적으로 비교를 하였고,

다른부분이 1개면 S는 n개로 끊었던 문자열이 되고, 2개 이상이면 S를 구할 수 없는 것입니다.

 

두 개의 그룹이

모두 true면 답이 2개이므로 2개가 같으면 문자열 출력, 다르면 NOT UNIQUE

모두 false면 답이 없으므로 NOT POSSIBLE

아니면 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
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static char ch[];
    static int N;
 
    static boolean solve(char s1[], char s2[]) {
        int cnt = 0;
        for (int i = 0, j = 0; i < s1.length; i++, j++) {
            if (s1[i] != s2[j]) {
                if (cnt > 0)
                    return false;
                cnt++;
                i--;
            }
        }
 
        return true;
    }
 
    static void func() {
        if (N % 2 == 0) {
            System.out.println("NOT POSSIBLE");
            return;
        }
        char s1[] = new char[N / 2];
        char s2[] = new char[N / 2 + 1];
        char s3[] = new char[N / 2];
        char s4[] = new char[N / 2 + 1];
 
        System.arraycopy(ch, 0, s1, 0, N / 2);
        System.arraycopy(ch, N / 2, s2, 0, N / 2 + 1);
 
        System.arraycopy(ch, 0, s4, 0, N / 2 + 1);
        System.arraycopy(ch, N / 2 + 1, s3, 0, N / 2);
 
        boolean result2 = solve(s3, s4);
        boolean result1 = solve(s1, s2);
 
        if (result1 && result2) {
            String str1 = String.valueOf(s1);
            String str2 = String.valueOf(s3);
            if (str1.contains(str2))
                System.out.println(String.valueOf(s1));
            else
                System.out.println("NOT UNIQUE");
        } else if (!result1 && !result2)
            System.out.println("NOT POSSIBLE");
        else if (result1)
            System.out.println(String.valueOf(s1));
        else
            System.out.println(String.valueOf(s3));
 
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        ch = st.nextToken().toCharArray();
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

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

boj 10453 문자열 변환  (0) 2024.07.24
boj 9081 단어 맞추기  (0) 2021.12.15

+ Recent posts

티스토리툴바