UVa 200. Rare Order AC get =_=

#include <stdio.h> #include <stdlib.h> #include <string.h> #define FUCKYOUSPARKING 100 int graph[FUCKYOUSPARKING][FUCKYOUSPARKING]; int out_degree[FUCKYOUSPARKING]; int degree[FUCKYOUSPARKING]; char prev[255]; char curr[255]; // 문자 비교 파트에요. -_- void fuckingJAVA(char *a, char *b, int graph[FUCKYOUSPARKING][FUCKYOUSPARKING], int degree[FUCKYOUSPARKING], int out_degree[FUCKYOUSPARKING]) { int firstChar = *a - 'A', secondChar = *b - 'A'; while (*a && *b && *a == *b) { a++; b++; } if (*a && *b) { // 유향그래프 처리 파트. a < b 꼴로 됩니다. firstChar = *a - 'A'; secondChar = *b - 'A'; if(graph[secondChar][firstChar] == 0) { graph[secondChar][firstChar] = 1; degree[firstChar]++; degree[secondChar]++; out_degree[secondChar]++; } } } // 출력이에요 -_- void CppIsBest(int graph[FUCKYOUSPARKING][FUCKYOUSPARKING], int degree[FUCKYOUSPARKING], int out_degree[FUCKYOUSPARKING]) { int chars[FUCKYOUSPARKING]; int maximum = 0, i, j; int character, nowchar; for (i = 0; i < FUCKYOUSPARKING; i++) { if (degree[i]) { chars[maximum] = i; maximum++; } } // 고(?)문자 순으로 찍습니다. for (i = 0; i < maximum; i++) { character = -1; for (j = 0; j < maximum; j++) { nowchar = chars[j]; if (out_degree[nowchar] == 0) { character = nowchar; out_degree[nowchar] = -1; putchar(character + 'A'); break; } } // 진출차수 정리... for (j = 0; j < maximum; j++) { nowchar = chars[j]; if (graph[nowchar][character] > 0) { out_degree[nowchar]--; graph[nowchar][character] = 0; } } } } int main() { int n = 1; char temp[256]; scanf("%s", prev); while (1) { scanf("%s", curr); if (!strcmp(curr, "#")) { break; } fuckingJAVA(prev, curr, graph, degree, out_degree); // ..... 이전문자열을 새로 받은 녀석으로 체인지. memcpy(temp, prev, sizeof(prev)); memcpy(prev, curr, sizeof(curr)); memcpy(curr, temp, sizeof(temp)); n++; } if(n == 1) { putchar(prev[0]); } else { CppIsBest(graph, degree, out_degree); } putchar('\n'); return 0; }

스'뽜'킹님아

살살해염

나 손가락 아파 ㄱ-

----------------------------------------------------------------------------------------------

모니터가 죱내 넓어진 탓에

#define으로 잡은 FUCKYOUSPARKING처럼 긴 이름을 마음놓고 쓰게 됐습니다 -_-

문제 번역 부분에 댓글 단 것 처럼, 유향그래프를 이용해 탐색합니다.

그 부분이 이디냐 하면...

바로 fuckingJAVA 함수입니다.

-_-...

죄송해요.

자바로 UVa 문제 풀다 보니 승질 뻗치더라구요;;;

여서 제가 메인함수에서 n = 1로 두고, 아래서 n이 1이냐 아니느냐로 CppIsBest 함수를 호출했는데요.

CppIsBest 함수는 고문자 순으로 출력하게 하는 함수입니다.

만약 n이 1이라면, 한줄 딸랑 받은거니 정리 하고 자시고 없어서

그냥 prev를 고대로 찍어버림 되니까요.

초기화가 귀찮아서 그냥 prev, curr를 전역변수로(이 경우 NULL 혹은 0으로 자동 초기화 됩니다.)

선언해 버렸습니다.

degree는 해당 노드에서의 전체 차수를 의미하고, out_degree는 해당 노드에서의 진출 차수를 의미합니다.

CppIsBest 함수의 초반부에 i가 0부터 FUCKYOUSPARKING까지 돌 때는

다름아니라... 차수를 가지고 가장 큰 문자열이 뭔지를 판별합니다.

이후 maximum까지 돌때 고(?)문자 순으로 찍지요.

두개의 내부 루프중 첫번째는 0부터 maximum까지 돌면서

j번째 문자의 진출차수가 0이라면 그걸 출력해주는걸 반복합니다.

두번째 내부 루프는 해당 글자들의 차수를 원상복구 시켜주는 역할을 하지요.

.... 너무 횡설수설로 써놨네.

여튼, 유향그래프로 만들어놓고 진출차수를 이용해 체크해 순서를 "예상"하는 방법입니다.

-ㅁ-;;;;;;

외의 방법으로는 2차원 배열에 입력을 다 쑤셔넣고는

큐에 또 우르르.... 넣고

큐에서 새로운 문자를 만날때까지 꺼내서 얹어놓고...

다시 우겨넣고...

이리 반복하다가 큐에 남은 녀석들을 그냥 차례로 출력하는 방법도 있습니다만,

그건 구현하기 귀찮았으므로 -_-

------------------------------------------------------------------------------------

스'뽜'킹군.

하드해 하드해 -ㅁ- 어려웠다구