Tackle to Mr.K's Solution.(PKU 1145)

#include <stdio.h> #include <ctype.h> #define SIZE 300 typedef enum storeType { NONE, NUMBER, LETTER, BRANCH, LEAF } storeType; typedef struct { int nPart; char cPart; storeType status; } card; /* status의 내용을 바꿔주는 것만으로 int형과 char형을 자유자재로 다룰 수 있어서 앞·뒤 뒤집는게 쉬운 card에 비유, 디버깅이 불편하다는 것이 단점 */ void main() { int searchKey; char inputStr[ SIZE ]; card adjusted[ SIZE ]; card stack[ SIZE ]; card temp[ SIZE ]; int compare = 0; int type = 0; /* 1 : digit, 0 : etc */ int i = 0; int j = 0; int judge = 0; char *walker; int count = 0; for( i = 0; i < SIZE; i++ ) /* card형 initialize */ { adjusted[i].status = NONE; stack[i].status = NONE; temp[i].status = NONE; } i = 0, j = 0; while( i == 0 || (i > 0 && count > 0) ) { walker = &inputStr[i]; if( i == 0 ) scanf( "%d ", &searchKey ); gets( walker ); for( j = i; inputStr[j] != '\0'; j++ ) { if( inputStr[j] == '(' ) count++; if( inputStr[j] == ')' ) count--; } i = j; } i = 0, j = 0; while( inputStr[i] != '\0' ) { if( isdigit( inputStr[i] ) && type == 0 ) { type = 1; if( inputStr[i-1] == '-' ) { adjusted[j].nPart = '0' - inputStr[i]; } else { adjusted[j].nPart = inputStr[i] - '0'; } adjusted[j].status = NUMBER; j++; } else if( isdigit( inputStr[i] ) && type == 1 ) { type = 1; if( adjusted[j-1].nPart < 0 ) { adjusted[j-1].nPart = adjusted[j-1].nPart * 10 - ( inputStr[i] - '0' ); } else { adjusted[j-1].nPart = adjusted[j-1].nPart * 10 + ( inputStr[i] - '0' ); } adjusted[j-1].status = NUMBER; inputStr[i-1] = ' '; } else { type = 0; adjusted[j].cPart = inputStr[i]; adjusted[j].status = LETTER; j++; } i++; } i = 0, j = 0; while( adjusted[i].status != NONE ) { if( adjusted[i].status == NUMBER ) { stack[j].nPart = adjusted[i].nPart; stack[j].status = adjusted[i].status; j++; } else if( adjusted[i].cPart == ')' ) { stack[j].cPart = adjusted[i].cPart; stack[j].status = adjusted[i].status; j++; } else { ; } i++; } i = 0; while( stack[i].status != NONE ) { if( stack[i].status == LETTER && stack[i-1].status == LETTER && stack[i-2].status == NUMBER ) { stack[i].status = LEAF; } i++; } i = 0, j = 0; while(1) { if( stack[0].status == LETTER ) break; /* no tree */ if( temp[0].status == LETTER || judge == 1 ) break; while( stack[i].status != NONE ) { if( stack[i].status != LEAF && stack[i].status != BRANCH ) { if( stack[i].status == NUMBER ) { temp[j].nPart = stack[i].nPart; temp[j].status = stack[i].status; compare += temp[j].nPart; } else { temp[j].cPart = stack[i].cPart; temp[j].status = stack[i].status; if( temp[j].status == LETTER && temp[j-1].status == LETTER && temp[j-2].status == NUMBER ) { stack[i].status = BRANCH; i--; j--; } } j++; } else { if( stack[i].status == LEAF && compare == searchKey ) { judge = 1; break; } else { compare -= temp[j-2].nPart; temp[j].status = NONE; temp[j-1].status = NONE; temp[j-2].status = NONE; j -= 2; } } i++; } } if( judge ) printf("yes\n"); else printf("no\n"); }

Mr.K의 솔루션입니다.

위 부분에서 첫번째 문제...

문제에는 "EOF까지 입력받아라~"라고 되어있습니다.

근데 이 처리가 없지요 -_-a;;

이 처리는 생각보다 단순합니다.

int main() { //선언부 while(scanf(입력부) != EOF) { //처리부 } return 0; }

위와 같습니다.

scanf는 EOF를 만나면 데이터를 변수에 넣지 않고, EOF를 리턴합지요.

이 외의 경우 scanf는 읽어들이는데 성공한 변수의 갯수를 리턴합니다.

while문의 조건에 scanf가 EOF를 만나느냐 아니느냐를 가지고 처리하게 해 버리고

내부 처리 루틴을 이 안에 쑤셔넣음으로써 해결되지요.

UVa나 PKU에서 EOF를 만날때까지 입력받을때 항상 쓰이는 방법입니다.

일반적으로 UVa나 PKU는 입력이 남았는데도 프로그램이 종료될 경우

TLE(Time Limit Exceed)나 WA(Wrong Answer)중 자기 마음대로 나오는 경향이 있습니다.

UVa의 경우는 WA만 나오더군요.

-_-;

이후 45~ 53줄.

gets를 이용해 입력을 받고 있습니다.

이 경우 문제점이.....

자. 아래 입력 예시를 보세요.

3 (3()
())
4 (2(2()())
())

.....

첫 문장만 처리해야 하는데...

4 (2(2()()) 까지 gets가 먹어버립니다.

-_-;

로직상 문제 없지 않냐구요?

.....

문제 있어요 -_-;;

gets는 버퍼에 글을 쓴 후, 버퍼 내용을 지우지 않고 변수에 데이터를 넣고 끝냅니다.

고로.... 입력 버퍼와 변수에 저장할 버퍼 사이에서 gets 한번 더 호출시

'\0'의 위치가 엉킨다거나, 하는 문제가 발생합니다.

-_-;

한두번의 입력은 버텨내겠지만, 이후에는 RE(Runtime Error)나 WA(Wrong Answer)를

유도할 수 있습니다.

이 떄문에 제가 getchar로 하나하나 받아다 처리했다지요 -_-;;

제 경우는 scanf의 특성을 활용했습니다.

EOF를 만날 경우 EOF나 -1을 리턴하는것 외에도,

scanf("%d", &a);시 입력받은 부분이 숫자로 시작하지 않는다면 scanf는 1개중 1개를 읽는데 실패했으니

1 - 1 = 0, 즉, 0을 리턴합니다.

이리하여 제 경우는 처음 비교대상은 scanf로 받고, 이후 getchar로 (를 받을떄까지 달린 후, 바로 scanf

를 이용해 빈 노드인지 아닌지를 판별하고 넘어가는 방식을 썼습니다.

빈 노드가 아니라면 scanf가 1을 리턴함으로써 참이 될 테고, 이 경우 내부 노드를 추가 확인하는 작업,

빈 노드라면 scanf가 0을 리턴함으로써 거짓이 되니, 다시 한번 (를 찾아 getchar의 여행을 떠나는거지요.

-_-;;

이후 곽군 코드의 문제점.

스택에다가 아예 우르르 쌓아버린후 연산하는데...

TL 걸리기 딱 좋답니다.

WA 풀린다면 아마 TL이 또 한번 가로막을꺼에요.

-_-!;;;;

용호군은 현재 솔루션이 있으나, 다시 생각해 풀어 올린다 합니다.

용호군의 솔루션도 저와 비슷한데.... 전북대 ALPS의 솔루션과 매우 흡사합니다.

용호군이나 저나 getchar를 이용해 한글자씩 받으며 입력받음과 동시에 연산을 했습니다.

이리하여 만약 yes가 된다면, 이후에는 종료될때까지 입력만 받도록 처리되었지요.

특히 Mr.K의 솔루션에서는 구조체를 이용해 처리를 했는데,

구조체의 배열 크기를 300으로 잡았답지요.

gets를 썼다는 부분과 문자열로 처리했다는 부분, 노드 갯수를 300이라는 적은 숫자로 잡은 부분에서

큰 문제가 발생합니다.

문자열로 처리함으로써 만약 한 줄에 256자가 넘게 입력되거나, 한 입력문이 256자가 넘으면

바로 RE입죠.

-_-;

동시에, 노드 갯수(Mr.K는 카드)가 300개를 넘는 경우에도 RE가 발생합니다.

물론 저런 극악의 경우는 드물겠지만 말입니다. -_-;

이 부분에 대한 처리를 하고 나면 코드가 상당히 짧아짐과 동시에 안정성을 가질겁니다.