(글 수정 시작 : 3일 pm 11시 경)
설명하기 전에,
앞으로 등장하게 될 트리는 문제의 입력 예시 3번째에 있는
(3 (2 (4 () ()) (8 () ())) (1 (6 () ()) (4 () ()))) 으로 하겠습니다
먼저 구조체 card를 살펴보면
숫자(여기선 특히 int형)를 저장하는 nPart와
문자(여기선 특히 닫는 괄호)를 저장하는 cPart,
그리고 그 상태를 나타내주는 status로 구성되어있습니다
이 때 status를 보면 storeType형으로 되어있는데,
열거형으로 된 이것은 NONE(아무것도 없음), NUMBER(숫자가 저장되어있음), LETTER(문자가 저장되어있음), BRANCH(가지), LEAF(잎)으로 구성되어있습니다
'가지'와 '잎'의 역할은 나중에 언급하기로 하고-
처음의 for문(37라인 ~ 42라인)은
세 개의 card형 배열의 초기화를 담당합니다
nPart와 cPart에 무엇이 저장되어있건, 그게 쓰레기값이라 해도
status를 NONE으로 설정하면 아무것도 없는 상태로 간주하는 것이죠
그리고 첫 while문(47라인 ~ 57라인)은 정수 하나와 트리를 입력받는 부분입니다
walker와 i, j, 그리고 50~54라인의 for문의 역할은
gets로 입력시 엔터키를 치더라도 다음 줄에 계속해서 입력을 받도록 된 부분입니다
while문 탈출 조건은 입력받은 트리의 여는 괄호와 닫는 괄호의 개수가 일치할 때만 입니다
두번째 while문(60라인 ~ 98라인)은
첫 while문에서 입력받은 트리를 card형 배열 adjusted에 옮기는 부분입니다
inputStr에 입력받은 내용을 하나씩 확인하면서 숫자면 type을 1, 문자면 0으로 설정하면서
문자 뒤에 숫자나 문자가 오면 그냥 card형으로 바꿔서 저장하고,
숫자 뒤에 숫자가 오면 음수와 양수를 구분하여 저장합니다
이 때, else if 안의 내용이 위의 두 경우와 다른 이유는
inputStr : …[1][2]… 를
adjusted : …[12][ ]… 로 만들기 때문입니다
세번째 while문(101라인 ~ 120라인)은
adjusted의 내용에서 숫자와 닫는 괄호만을 골라내어 card형 배열 stack에 저장합니다
그러면 stack 안의 내용은
3, 2, 4, ), ), ), 8, ), ), ), ), 1, 6, ), ), ), 4, ), ), ), ), ) 이 되겠지요
네번째 while문(123라인 ~ 130라인)에서는
일부 괄호의 속성을 LETTER에서 LEAF로 바꾸는 과정입니다
트리의 형태를 보면 가지의 끝부분에서는 n () () 의 형태를 띄는데,
stack엔 닫는 괄호만 저장되어있으므로
숫자 뒤에 연속으로 닫는 괄호가 나오면 그 중 두번째를 LEAF로 바꿉니다
즉,
3, 2, 4, ), ), ), 8, ), ), ), ), 1, 6, ), ), ), 4, ), ), ), ), ) 입니다 (붉은 괄호의 status가 LEAF)
마지막 while문(133라인 ~ 178라인)에서는
card형 배열 temp에 stack의 내용을 하나하나 저장하면서
숫자 뒤에 괄호가 두 개 연속해서 붙으면 숫자를 떼어내는 방식으로 연산합니다
이 때, compare라는 변수에 stack 안의 숫자값을 다 더하다가
LEAF를 만나는 순간 그 값을 searchKey의 값과 비교하고, 일치하면 judge를 1로 바꾸고 브레이크,
일치하지 않으면 괄호 두 개와 숫자 하나를 없애고(status를 NONE으로) 없앤 숫자만큼을 compare에서 뺍니다
그렇게 연산을 계속 하다가, LEAF이 아닌데 숫자 뒤에 괄호 두 개가 연속으로 붙으면
두번째 괄호의 속성을 BRANCH로 바꾸고 index를 하나씩 줄여서 다시 괄호의 속성을 검사하게 만듭니다
BRANCH는 compare값을 비교하지 않고 괄호 두 개와 숫자 하나를 없앱니다
그렇게 했는데 찾는 값이 없다면 연산이 끝난 후 temp에는 닫는 괄호 하나만이 남게 되는데
그건 그냥 연산이 끝났다고 보고 while문을 탈출합니다
그리고 마지막에 judge 값에 따라 yes나 no를 출력해주면 끝입니다
(글 수정 완료 : 4일 am 0시 40분 경)
----------------------------------------
한가지 확실히 해둘 것은
고의로 복잡하게 짠 것은 아니라는 것;
프로그램이 VC++ 6.0이니 컴파일러도 아마 VC 6.0일듯?
UVa에서는 서버불안정(?)으로 제출 불가,
PKU에서는 CE판정 받았습니다, 어찌보면 당연한 일, (문법이 완전하지 않은듯)
소스 붙여넣고 VC++에서 돌리면 문제에서 원하는 결과는 나옵니다
VC++에서 돌리면 결과는 잘 나옵니다 (.. 아마 마이너스기호랑 숫자를 떨어뜨려서 쓰는 짓만 하지 않으면?)
EOF 입력 받는거 처리했는데도 이 모양이니 그냥 AC는 포기해야할듯 -_-
'Solutions > Mr.K's Solution' 카테고리의 다른 글
| PKU 1145, UVa 112. Tree Summing. [판정:AC & TLE] (1) | 2008.09.20 |
|---|---|
| PKU 3685. Matrix. [판정:WA] (5) | 2008.09.18 |
| PKU 2017. Speed Limit. [판정:AC] (2) | 2008.09.12 |
| PKU 2027. No Brainer. [판정:AC] - 104B (0) | 2008.09.11 |
| PKU 2027. No Brainer. [판정:AC] (0) | 2008.09.10 |
