복기
먼저 이 문제는 제가 풀지못한 문제입니다. 결국 다른 사람의 풀이를 보고 풀었죠...ㅜㅜ
구슬이 중간에서 터지면 위의 구슬이 떨어져서 밑이랑 색이 같으면 또 터지는 뿌요뿌요 게임처럼 삭제된 문자열 좌우 문자를 붙혀서 A 문자열이 나오면 또 삭제를 해줘야하는 점이 아마 이 문제를 까다롭게 만드는 점인 것 같은데요.
먼저, 아래는 다른 사람 풀이를 보고 작성한 코드입니다.
|
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
|
// 검열
#include <stdio.h>
#pragma warning(disable : 4996)
char A[35], T[300015], s1[300015], s2[300015], b;
int len, l, r, t1, t2;
char check(void) {
if (0 == b) {
if (t1 < len) return 0;
for (int i = 1; i <= len; i++) {
if (s1[t1 - i] != A[len - i]) {
return 0;
}
}
}
else {
if (t2 < len) return 0;
for (int i = 1; i <= len; i++) {
if (s2[t2 - i] != A[i - 1]) {
return 0;
}
}
}
return 1;
}
int main(void) {
scanf("%s %s", A, T);
for (len = 0; A[len]; len++);
for (r = 0; T[r + 1]; r++);
while (l <= r) {
if (0 == b) {
s1[t1++] = T[l++];
if (s1[t1 - 1] == A[len - 1]) {
if (check()) {
t1 -= len;
b ^= 1;
}
}
}
else {
s2[t2++] = T[r--];
if (s2[t2 - 1] == A[0]) {
if (check()) {
t2 -= len;
b ^= 1;
}
}
}
}
b = 0;
while (t2) {
s1[t1++] = s2[--t2];
if (s1[t1 - 1] == A[len - 1]) {
if (check())
t1 -= len;
}
}
s1[t1] = 0;
return !printf("%s\n", s1);
}// 1
|
cs |
위 코드가 제가 맨처음 작성했던 코드와 다른 점은 비교를 앞에서부터 하는가 뒤에서부터 하는가 입니다.
글이 좀 애매한데 어떤 의미인가 하면
| A: aac T: aaaaaaccc |
위의 입력이 주어졌을 때, T의 왼쪽에서부터 A 문자열과 일치하는 문자열을 찾는 상황에서
앞에서부터 비교한다는건 (a a c 순으로 비교) 아래와 같이 일치하는 문자열을 찾았을 때 인덱스가 4 가 되는 것이고
뒤에서부터 비교한다는건 (c a a 순으로 비교) 인덱스가 6 일 때 아래 상황이 되는 겁니다.
| aaaa (aac) cc |
별 것 아닌 차이 같지만 앞문자부터 비교하면 삭제후 다음 인덱스부터 앞방향 탐색 범위에 삭제 때문에 끊기고 뒤에 남은 문자들이 포함되지 못합니다. 추가로 뭔 짓거리를 더 해줘야 하는 셈이죠. : aaaa (c->) c
반면에 뒷문자부터 비교하면 삭제후 다음 인덱스로 옮겨도 버퍼 안의 내용과 비교하면 탐색하던 방향 그대로 뒤에 남은 문자들을 포함해서 비교할 수 있죠 : aaaa (<-c) 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
|
// 검열
#include <stdio.h>
#include <string.h>
#pragma warning(disable : 4996)
volatile char A[33], T[300015];
volatile int len, f, r;
struct Stack {
char data[300015];
int top;
} s1, s2;
void Push(Stack *ps, char in) { ps->data[ps->top++] = in; }
char Pop(Stack *ps) { return ps->data[--(ps->top)]; }
int GetCount(Stack *ps) { return ps->top; }
int main(void) {
scanf("%s %s", A, T);
for (len = 0; A[len]; len++);
for (r = 0; T[r]; r++);
char bSame;
int n;
while (r - f >= len) {
while (r - f >= len) {
bSame = 1;
for (int i = 0; i < len; i++) {
if (T[f + i] != A[i]) {
bSame = 0;
break;
}
}
if (bSame == 0)
Push(&s1, T[f++]);
else {
n = GetCount(&s1);
n = n < len - 1 ? n : len - 1;
f += len - n;
for (int i = n - 1; i >= 0; i--)
T[f + i] = Pop(&s1);
}
while (GetCount(&s2) > 0 && r - f < len) {
T[r++] = Pop(&s2);
T[r] = 0;
}
if (bSame == 1) break;
}
while (r - f >= len) {
bSame = 1;
n = r - len;
for (int i = 0; i < len; i++) {
if (T[n + i] != A[i]) {
bSame = 0;
break;
}
}
if (bSame == 0)
Push(&s2, T[--r]);
else {
n = GetCount(&s2);
n = n < len - 1 ? n : len - 1;
r -= len - n;
T[r] = 0;
for (int i = n; i > 0; i--)
T[r - i] = Pop(&s2);
}
while (GetCount(&s1) > 0 && r - f < len)
T[--f] = Pop(&s1);
if (bSame == 1) break;
}
}
while (GetCount(&s1) > 0)
T[--f] = Pop(&s1);
while (GetCount(&s2) > 0)
T[r++] = Pop(&s2);
T[r] = 0;
return !printf("%s\n", T + f);
} // 2
|
cs |
위 코드는 전자 방법으로 푼 코드이고 문자열 삭제후 뒤에 남은 문자랑 비교하려고 (A 문자열 길이 -1) 개 문자를 저장 버퍼에서 빼는... 쓰잘데기 없이 일을 만들어서 하는 방법입니다.
그리고, 사실 이 코드는 틀린 코드입니다. 이유는 잘 모르겠지만 "출력 초과"로 나오네요.. ㅠ_ㅠ
'일단 머리좀 식히고 답을 잊을 때쯤 다시와서 틀린 이유를 찾아보자' 는 의미에서 이 코드도 남깁니다.
혹여 지나가던 고수님께서 이유를 집어 주신다면 감사할 따름이고요 ㅎㅎ.
복기끝
사실 지금 든 생각이지만 이 것도 시작 문자 한 개만 버퍼랑 비교하고 나머지는 T랑 비교하면 전자나 후자나 다를게 없겠다는 생각이 드네요.............
지금까지 쓴 글이... ++'
'개발 > c' 카테고리의 다른 글
| [백준] 17825 주사위 윷놀이 (0) | 2020.04.24 |
|---|---|
| [백준] 17822 원판 돌리기 (0) | 2020.04.22 |
| [백준] 4179 불! (0) | 2018.12.13 |
| winpcap pcap_pkthdr 구조체에서 caplen과 len의 차이 (0) | 2018.12.01 |
| ffmpeg 라이브러리 사용법 (2) | 2018.11.16 |
