BOJ : https://www.acmicpc.net/problem/10942

github : https://github.com/junho0956/Algorithm/blob/master/10942/10942/%EC%86%8C%EC%8A%A4.cpp

 

manacher 알고리즘을 공부하고, 문제를 해결하였다.

사실 2차원의 dp로도 해결할 수 있는데 좀더 빠르며, 팰린드롬 관련해서 많이 쓰이는 알고리즘 이기에

연습도 할 겸 사용하였다.

 

단, manacher 알고리즘은 홀수 기준의 문자열만 판단가능하기 때문에

이 문제에서 짝수가 나올 수 있다는 것을 감안하여

숫자 중간중간에 임의의 값을 삽입하여 홀수로 만들고 문제를 해결하였다.

 

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
// manacher's algorithm
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int dp[4010];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    string str;
    int N; cin >> N;
    int len = N * 2 - 1;
    for (int i = 0; i < N; i++) {
        int num; cin >> num;
        str += num + '0';
        str += '#';
    }
 
    int r, p;
    r = p = 0;
    for (int i = 0; i < len; i++) {
        if (i <= r) dp[i] = min(r - i, dp[p * 2 - i]);
        else dp[i] = 0;
 
        while (i + dp[i] + 1 < len && i - dp[i] - 1 >= 0 && str[i + dp[i] + 1] == str[i - dp[i] - 1]) dp[i]++;
        if (i+dp[i] > r) {
            r = i + dp[i];
            p = i;
        }
    }
 
    int T; cin >> T;
    while (T--) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        a *= 2;
        b *= 2;
        int mid = (a + b) / 2;
        if (mid + dp[mid] >= b) cout << "1\n";
        else cout << "0\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 11046번 팰린드롬??  (0) 2020.02.16
BOJ 13275번 가장 긴 팰린드롬 부분 문자열  (0) 2020.02.16
BOJ 1695번 팰린드롬 만들기  (0) 2020.02.16
BOJ 1213번 팰린드롬 만들기  (0) 2020.02.16
1254번 팰린드롬 만들기  (0) 2020.02.16

BOJ : https://www.acmicpc.net/problem/1695

github : https://github.com/junho0956/Algorithm/blob/master/1695/1695/%EC%86%8C%EC%8A%A4.cpp

 

문자열을 앞 뒤 중간 어디든 넣을 수 있다면, LCS를 통하여 간단히 해결할 수 있다.

 

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
#include <iostream>
#include <algorithm>
using namespace std;
 
#define MAX 5001
 
int dp[MAX][MAX];
int arr[MAX];
int reverse_arr[MAX];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N; cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i], reverse_arr[N - i-1] = arr[i];
 
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {
            if (arr[i] == reverse_arr[k]) dp[i + 1][k + 1] = dp[i][k] + 1;
            else dp[i + 1][k + 1] = max(dp[i + 1][k], dp[i][k + 1]);
        }
    }
 
    cout << N - dp[N][N];
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 13275번 가장 긴 팰린드롬 부분 문자열  (0) 2020.02.16
BOJ 10942번 팰린드롬?  (0) 2020.02.16
BOJ 1213번 팰린드롬 만들기  (0) 2020.02.16
1254번 팰린드롬 만들기  (0) 2020.02.16
BOJ 1720번 타일 코드  (0) 2020.02.13

BOJ : https://www.acmicpc.net/problem/1213

github : https://github.com/junho0956/Algorithm/tree/master/1213

 

알파벳이 A-Z 까지 주어진다.

이 때 string 의 각 문자열을 [26] 배열을 통해 그 갯수를 저장해놓을 수 있다.

문제의 조건에서는 정렬을 통한 앞선 팰린드롬을 출력하라고 했으니, [26]배열을 통해 순서대로 만들면 된다.

 

주어진 문자열이 홀수일수도 있고, 짝수일수도 있다.

결국 팰린드롬을 만들지 못하는 경우는 홀수이건, 짝수이건 간에 그 경우가 2번이상 나타날때이다.

이때를 제외하고는 무조건 팰린드롬을 만들 수 있다.

 

팰린드롬을 만들것이므로, 미리 앞의 반만 만들어 놓으면 그 뒤의 반은 앞의 것을 반대로 출력해주기만 하면된다.

결국 AA.. 에서 A는 2번 나왔으므로 반만 만들어놓는 스트링에는 A가 1번 입력될 것이다.

AAA..이면 당연히 1번만 입력된다.

그러므로 [26] 배열의 값을 통째로 가지고 있다가 /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
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int use[26];
 
int main() {
    vector<pair<char, int> > v;
    string str;
    int mid = -1;
    bool flag = false;
 
    cin >> str;
    for (int i = 0; i < str.size(); i++) use[str[i] - 'A']++;
 
    for (int i = 0; i < 26; i++) {
        if (use[i] % 2 && flag) {
            cout << "I'm Sorry Hansoo";
            return 0;
        }
        else if (use[i] % 2) {
            flag = true;
            mid = i;
            v.push_back({ i + 'A', use[i] });
        }
        else v.push_back({ i + 'A', use[i] });
    }
 
    string ans = "";
    for (int i = 0; i < v.size(); i++)
        for (int k = 0; k < v[i].second / 2; k++)
            ans += v[i].first, cout << v[i].first;
 
    if (mid != -1) ans += mid + 'A';
    for (int i = ans.size() - 1; i >= 0; i--)
        cout << ans[i];
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

 

 

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

BOJ 10942번 팰린드롬?  (0) 2020.02.16
BOJ 1695번 팰린드롬 만들기  (0) 2020.02.16
1254번 팰린드롬 만들기  (0) 2020.02.16
BOJ 1720번 타일 코드  (0) 2020.02.13
BOJ 11060번 점프 점프  (0) 2020.02.13

BOJ : https://www.acmicpc.net/problem/1254

github : https://github.com/junho0956/Algorithm/blob/master/1254/1254/%EC%86%8C%EC%8A%A4.cpp

 

 

팰린드롬이 만들기 위해서 뒤에서부터 최소 0개이상의 문자를 붙여야된다는 조건이였습니다.

길이는 최대 1000이기 때문에 충분히 브루트포스로 해결할 수 있었습니다.

앞자리에 붙이고자 하는 갯수만큼 뒤에 붙였다고 생각하면

이미 앞자리 부분과 뒷자리 부분은 팰린드롬을 이루기 때문에, 전체탐색을 할 필요없이 

팰린드롬이 되는 부분을 제외한 부분만 탐색해주시면 됩니다.

 

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
#include <iostream>
#include <string>
using namespace std;
 
string str;
 
bool palin(int idx) {
 
    int len = str.size() - 1;
    for (int i = idx; i <= len; i++, len--) {
        if (str[i] != str[len]) return false;
    }
    return true;
}
 
int main() {
    cin >> str;
 
    for (int i = 0; i < str.size(); i++) {
        if (palin(i)) {
            cout << str.size() + i;
            break;
        }
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 1695번 팰린드롬 만들기  (0) 2020.02.16
BOJ 1213번 팰린드롬 만들기  (0) 2020.02.16
BOJ 1720번 타일 코드  (0) 2020.02.13
BOJ 11060번 점프 점프  (0) 2020.02.13
BOJ 1890번 점프  (0) 2020.02.13

+ Recent posts

티스토리툴바