좋은 단어 




예제 입력 

3
ABAB
AABB
ABBA



같은 글자 두 개씩 쌍을 짓는데, 글자 위로만 선을 그어서 쌍을 지어야 한다.


이 선이 겹치지 않을 때 좋은 단어로 친다.


예제의 경우에 ABAB는 좋은 단어가 아니다.



퍼뜩 떠오른 생각은 스택에 넣으면서 최상위 글자랑 지금 넣는 글자랑 다르면 좋은 단어가 아니다.


따라서 첫 글자는 무조건 스택에 넣어야 한다.


두번째 글자부터 이를 확인해 주면된다.


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
#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
 
int n, ans, len;
char buf[100001];
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", buf);
        len = strlen(buf);
        stack<char> st;
        st.push(buf[0]);
 
        for (int j = 1; j < len; ++j) {
            if (st.empty())
                st.push(buf[j]);
 
            else if (st.top() == buf[j])
                st.pop();
            else
                st.push(buf[j]);
        }
 
        if (st.empty())
            ans++;
    }
    printf("%d", ans);
}
cs


'알고리즘 > 미분류' 카테고리의 다른 글

백준) 2257 화학식량  (0) 2018.01.31
백준) 2841 외계인의 기타 연주  (0) 2018.01.22
백준) 9935 문자열 폭발 (스택)  (0) 2018.01.22
백준) 11559 Puyo Puyo  (0) 2018.01.14
백준) 5397 키로거 (스택)  (0) 2018.01.13

문자열 폭발 



상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

  • 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
  • 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
  • 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이 때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.



문자열을 순회할때 폭발 문자열과 같은지 확인하고, 같다면 현재 보고 있는 인덱스를 다시 당겨서 정답을 채워나가자.


비슷한 문자가 나와서 같은지 확인할 때, 너무 앞에서 걸려서 처음 인덱스를 벗어나버리는 경우를 생각하지 못해 오래걸렸다.


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 <stdio.h>
#include <string.h>
using namespace std;
 
char buf[1000001];
char ans[1000001];
char ex[37];
 
int buf_len, ex_len;
 
int main() {
    scanf("%s %s", buf, ex);
 
    buf_len = strlen(buf);
    ex_len = strlen(ex);
 
    int p = 0;
    for (int i = 0; i < buf_len; ++i) {
        ans[p++] = buf[i];
 
        if (ans[p - 1] == ex[ex_len - 1]) {
            if (p - ex_len >= 0) {
                bool chk = false;
                for (int i = 0; i < ex_len; ++i) {
                    if (ans[p - 1 - i] != ex[ex_len - 1 - i]) {
                        chk = true;
                        break;
                    }
                }
 
                if (!chk) {
                    p -= ex_len;
                }
            }
        }
    }
    if (p == 0)
        printf("FRULA");
    else {
        ans[p] = '\0';
        printf("%s", ans);
    }
}
cs


'알고리즘 > 미분류' 카테고리의 다른 글

백준) 2841 외계인의 기타 연주  (0) 2018.01.22
백준) 3986 좋은 단어  (0) 2018.01.22
백준) 11559 Puyo Puyo  (0) 2018.01.14
백준) 5397 키로거 (스택)  (0) 2018.01.13
백준) 2110 공유기 설치  (0) 2018.01.09

Puyo Puyo




복잡한 구현의 문제.

우리가 아는 바로 그 게임을 구현하면 된다.

주의할 점은 현재 상태에서 4개이상 붙어버린 뿌요들은 한 번에 터지고(콤보 1),

한 번에 바닥으로 내려가고, 새로운 상태에서 새롭게 붙어버린 뿌요들도 한 번에 터진다는 것이다.



구현은 다음과 같이 하였다.


1. 맵을 DFS로 돌면서 현재 붙어버린 뿌요들을 파악한다.


2. 이 중 4개 이상되는 뿌요들만 한꺼번에 터진다.


3. 나머지 뿌요들이 바닥으로 내려오게 맵을 갱신해준다.


4. 1~3과정을 반복하면서 콤보 수를 센다.



과정 1을 수행하면서, 맵을 다른 곳에 기록해야 한다. DFS는 2개만 되어도 수행될 것이므로,


다른 곳에 좌표정보를 기록해두고, 과정 2에서 이를 써먹으면서 맵을 갱신해야 한다.



과정 3은 12*1의 배열이 6개 있다고 생각하고, 6개의 배열을 각각 갱신해주었다.


배열에서 뿌요들만 빼내서 다른 곳에 기록해두고, 배열을 갱신하는 방법을 사용했다.(스택 OR 큐)



코드로 옮기면 다음과 같다.


모든 과정을 수행하면서 맵 전체를 살피는게 불편하다면, 과정마다 뿌요들 중 최고 높이를 갱신하는 과정을 추가한다면


최적화가 가능해지지 않을까 생각한다.


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 <stdio.h>
#include <stack>
using namespace std;
 
typedef struct col {
    int x, y;
}col;
stack<col> st;
stack<int> st2;
 
int map[12][6];
int visit[12][6];
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
char buf[8];
 
int dfs(int x, int y, int c) {
    int cnt = 1;
    visit[x][y] = c;
    st.push({ x,y });
 
    for (int i = 0; i < 4; ++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
 
        if (xx < 0 || yy < 0 || xx >= 12 || yy >= 6)
            continue;
 
        if (map[xx][yy] == c && visit[xx][yy] == 0)
            cnt += dfs(xx, yy, c);
    }
    return cnt;
}
 
void arange() {
    for (int i = 0; i < 12; ++i)
        for (int j = 0; j < 6; ++j)
            visit[i][j] = 0;
 
    for (int i = 0; i < 6; ++i) {
        for (int j = 11; j >= 0; --j) {
            if (map[j][i] > 0) {
                st2.push({ map[j][i] });
                map[j][i] = 0;
            }
 
        }
        int cnt = 0;
        while (!st2.empty()) {
            map[cnt++][i] = st2.top();
            st2.pop();
        }
    }
}
 
int main() {
    for (int i = 11; i >= 0; --i) {
        scanf("%s", buf);
        for (int j = 0; j < 6; ++j) {
            if (buf[j] == 'R')
                map[i][j] = 1;
            else if (buf[j] == 'G')
                map[i][j] = 2;
            else if (buf[j] == 'B')
                map[i][j] = 3;
            else if (buf[j] == 'P')
                map[i][j] = 4;
            else if (buf[j] == 'Y')
                map[i][j] = 5;
        }
    }
 
    int combo = 0;
 
    while (1) {
        int del = 0;
        for (int i = 0; i < 12; ++i) {
            for (int j = 0; j < 6; ++j) {
                if (map[i][j] > 0 && visit[i][j] == 0) {
                    int cnt = dfs(i, j, map[i][j]);
 
                    if (cnt >= 4) {
                        del += cnt;
 
                        while (!st.empty()) {
                            map[st.top().x][st.top().y] = 0;
                            st.pop();
                        }
                    }
                    else {
                        while (!st.empty())
                            st.pop();
                    }
 
                }
            }
        }
        if (del == 0)
            break;
 
        arange();
        combo++;
    }
    printf("%d", combo);
 
    return 0;
}
cs



'알고리즘 > 미분류' 카테고리의 다른 글

백준) 3986 좋은 단어  (0) 2018.01.22
백준) 9935 문자열 폭발 (스택)  (0) 2018.01.22
백준) 5397 키로거 (스택)  (0) 2018.01.13
백준) 2110 공유기 설치  (0) 2018.01.09
백준) 1695 팰린드롬 만들기  (0) 2017.09.06

키로거




입력 케이스는 캐릭터와 좌우 화살표, 백스페이스로 분류된다.


캐릭터를 제외한 추가 키 들에 대한 기능을 정의해야 하는데,


좌우 화살표의 입력은 문자열 자체를 변경하진 않고 캐릭터가 입력될 위치(커서)를 바꾼다.


백스페이스는 현재 커서 바로 앞의 캐릭터를 지워야 한다.



위와 같은 기능을 구현하기 위해,


커서의 앞뒤를 구분하면서, 부가 키의 입력 시에 빠른 결과를 리턴해줄 구조를 짜야 하는데,


이를 스택으로 구현한다면 선형시간에 모든 기능이 수행된다.



커서의 앞과 뒤를 두 개의 스택으로 생각한다면


캐릭터의 입력은 앞의 스택에 push,


왼쪽 화살표는 앞 스택에서 pop -> 뒤 스택에 push,


반대로 오른쪽 화살표는 뒤 스택에서 pop -> 앞 스택에 push,


백스페이스는 앞 스택에서 pop


으로 구현할 수 있다.



기타 예외처리를 추가한 코드는 다음과 같다.


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
#include <stdio.h>
 
int T;
char buf[1000001];
int len;
int strlen(char buf[]) {
    int cnt = 0;
    while (buf[cnt] != '\0')
        cnt++;
    return cnt;
}
 
char stack1[1000001];
char stack2[1000001];
int stack1_size;
int stack2_size;
 
void stack_push(char stack[], char c, int& size) {
    stack[size++] = c;
}
char stack_pop(char stack[], int& size) {
    return stack[--size];
}
 
int main() {
    scanf("%d", &T);
 
    while (T--) {
        scanf("%s", buf);
        len = strlen(buf);
 
        for (int i = 0; i < len; ++i) {
            if (buf[i] == '<') {
                if (stack1_size == 0)
                    continue;
 
                stack_push(stack2, stack_pop(stack1, stack1_size), stack2_size);
            }
            else if (buf[i] == '>') {
                if (stack2_size == 0)
                    continue;
 
                stack_push(stack1, stack_pop(stack2, stack2_size), stack1_size);
            }
            else if (buf[i] == '-') {
                if (stack1_size == 0)
                    continue;
 
                stack_pop(stack1, stack1_size);
            }
            else
                stack_push(stack1, buf[i], stack1_size);
        }
 
        for (int i = 0; i < stack1_size; ++i)
            printf("%c", stack1[i]);
        for (int i = stack2_size-1; i >= 0; --i)
            printf("%c", stack2[i]);
        putchar('\n');
 
        stack1_size = 0;
        stack2_size = 0;
    }
 
    return 0;
}
cs


'알고리즘 > 미분류' 카테고리의 다른 글

백준) 3986 좋은 단어  (0) 2018.01.22
백준) 9935 문자열 폭발 (스택)  (0) 2018.01.22
백준) 11559 Puyo Puyo  (0) 2018.01.14
백준) 2110 공유기 설치  (0) 2018.01.09
백준) 1695 팰린드롬 만들기  (0) 2017.09.06

공유기 설치




N개 집의 위치가 일직선 상에 주어지고, 공유기의 갯수 C가 주어진다.

공유기는 집에만 설치 할 수 있을 때, C개를 적절하게 모두 설치하고자 한다.

이 때 설치 가능한 경우들 가운데, 가장 인접한 공유기 쌍의 거리는 최대 몇 까지 가능할까?


C가 2개라고 생각해본다면, 최인접 공유기 쌍간 거리는 시작집과 끝집 사이의 거리다.

C가 3개일 때 부터 고민을 해봐야 하는데, 모든 설치 가능한 경우를 시뮬레이션할 수 도 있다.

하지만 시간이 부족하므로 어떠한 최적화가 필요하다.


만약 최대거리가 x가 되게 시도해보고 성공한다면, x보다 작은 거리는 시도 해볼 필요가 없다.

따라서 이분탐색을 생각해 볼 수 있고, 집의 좌표는 최소 1, 최대 10억 이므로 log로 따지면 30번 안에 찾을 수 있다.


시도하는 과정은 어떻게 구현해야 할까?

그리디적으로 생각해보면 간략히 구현할 수 있다.

만약 중간 집들을 이용했을 때 현재 시도하는 거리가 유효하다면,

당연히 중간 집들의 맨 처음 집 대신 처음 집에 공유기를 심어도 유효하다는 사실은 변하지 않는다. 


만약 중간 집들 중 처음 집이 가장 인접한 공유기 쌍 중에 하나 였다면, 오히려 최대 길이는 늘어날 가능성이 있다.

아니었다면 최대 길이는 그대로 있다.

유효한 시뮬레이션임은 변하지 않는다.


따라서 우리는 처음 집에 공유기를 설치하고 나머지 과정을 시뮬레이션 하면 된다.

다음 집들을 살펴보면서 현재 시도하고 있는 최대길이를 유효하게만 해준다면 공유기를 심어도 되는 것이다.


코드로 옮기면 다음과 같다.



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
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, c;
int home[200000];
 
bool chk(int mid) {
    int cnt = 1;
    int cur = 0;
    int next = 1;
    
    while (next <= n - 1) {
        if (home[next] - home[cur] < mid)
            next++;
        else {
            cnt++;
 
            if (cnt == c)
                return true;
 
            cur = next;
            next = cur + 1;
        }
    }
    
    return false;
}
 
int main() {
    scanf("%d %d", &n, &c);
 
    for (int i = 0; i < n; ++i)
        scanf("%d", &home[i]);
        
    sort(home, home + n);
 
    int left = 1, right = home[n - 1] - home[0];
    int ans = 0;
 
    while (left <= right) {
        int mid = (left + right) / 2;
 
        if (chk(mid)) {
            if (ans < mid)
                ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
 
    printf("%d", ans);
 
    return 0;
}
cs


'알고리즘 > 미분류' 카테고리의 다른 글

백준) 3986 좋은 단어  (0) 2018.01.22
백준) 9935 문자열 폭발 (스택)  (0) 2018.01.22
백준) 11559 Puyo Puyo  (0) 2018.01.14
백준) 5397 키로거 (스택)  (0) 2018.01.13
백준) 1695 팰린드롬 만들기  (0) 2017.09.06

1695. 팰린드롬 만들기



문제

앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다.

한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 길이 N(1≤N≤5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다.

출력

첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다.

예제 입력 

5
1 2 3 4 2

예제 출력 

2



1. 접근


앞으로 보나 뒤로 보나 같은 수열을 팰린드롬 수열이라 한단다.


한 수열이 주어지고, 이 수열 양 끝과 사이사이에 숫자들을 끼워넣어서 팰린드롬으로 만들려고 한다.


이렇게 만드는 경우 중에 가장 숫자를 적게 쓰는 횟수는 몇번일까?



뭔가 획기적으로 수열을 분석하는 방법이 없으니까, (있을 수도 있지만 내가 모른당!)


무적의 다이나믹 프로그래밍으로 뚫어보자.



2. 풀이


가장 무식하게 팰린드롬으로 만드는 방법은 있다.


수열을 뒤집어서 뒤에 추가해 버리면 무조건 팰린드롬이다.


하지만 우리는 조각조각들을 끼워넣을 수 있으므로 저 방법보단 숫자들을 적게 쓴다.



그러면 무슨 패턴으로 숫자들을 추가해야 할까?


예시의 1, 2, 3, 4, 2 를 보자. 앞에서 보면 1의 짝꿍이 없으니까 뒤에 1을 추가해야 할 것 같긴 하다.


반대로 뒤에서 보면 2의 짝꿍이 없으니까 앞에 2를 추가해야 할 것 같기도 하다!



뒤에 추가하는 경우라면, 1은 짝이 생겼으니까 생각하지 않고, 남은건 2, 3, 4, 2로 팰린드롬을 만드는 문제다.


앞에 추가하는 경우라면, 2는 짝이 생겼으니까 생각하지 않고, 남은건 1, 2, 3, 4로 팰린드롬을 만드는 문제다.



아하! 그러면 앞에 추가하든지 뒤에 추가하든지 남은 수열의 문제 답이 작은 경우를 써야하겠다.


배열은 다음처럼 정의하자


DP[왼쪽 시작점][오른쪽 시작점] = DP[X][Y] = 남은 수열이 X~Y까지 수열일 때, 문제에서 원하는 정답을 저장



그러면 우리 답은 DP[0][N-1]에 있을 것이고,

기저사례들은 X>Y 가 되버려 수열을 다쓴 경우들이다.


X==Y인 경우도 당연히 더이상 뭘 해줄 필요는 사실 없지만, 원소가 두 개 남은 상태에서, 두 원소가 서로 다른 경우를 다시 생각해야 하는 번거로움이 있다. 그래서 기저사례는 저 경우만 생각하기로 하자.(푸는 사람 마음이다)


함수는 func(x, y)로 정의하고, DP[X][Y]를 계산해줘야 한다.


배열의 X번째 원소와 Y번째 원소가 같다면 둘다 무시하면 되고, 다르다면 뒤나 앞에 추가 해야 한다.



배열 크기에 시간 복잡도가 비례하니까, N*N = 25,000,000 으로 1초안엔 들어오겠다.



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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int n, i;
int arr[5000];
int dp[5000][5000];
 
int func(int x, int y) {
    if (x > y)
        return 0;
 
    int& ref = dp[x][y];
    if (ref != -1)
        return ref;
 
    if (arr[x] == arr[y])
        return ref = func(x + 1, y - 1);
    else
        return ref = min(func(x + 1, y) + 1, func(x, y - 1) + 1);
}
 
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", func(0, n - 1));
 
    return 0;
}
cs


'알고리즘 > 미분류' 카테고리의 다른 글

백준) 3986 좋은 단어  (0) 2018.01.22
백준) 9935 문자열 폭발 (스택)  (0) 2018.01.22
백준) 11559 Puyo Puyo  (0) 2018.01.14
백준) 5397 키로거 (스택)  (0) 2018.01.13
백준) 2110 공유기 설치  (0) 2018.01.09

+ Recent posts

티스토리툴바