글이 다 날아갔다... 너무슬프다.. 다시 써야겠따..
SW Expert Academy의 문제는 무단 복제가 금지되어 있으므로 링크로 대체합니다.
이 문제는 이전에 왔던 펠린드롬과 비슷하다!
하지만 훨씬 쉽다! 왜냐하면 *은 모든 글자를 대체할 수 있기 때문이다!
따라서 뒤에서 부터 팰린드롬이 되는지(문자가 같은지)확인하다가 별표를 만나면 어떠한 단어든 팰린드롬이 가능하다는 소리다!
(단, 문자를 확인하면서 팰린드롬이 안된다면 그 문자는 무조건 팰린드롬이 안되는 것이다!)
예를들면, a*wflkjwrglakjgla 라는 단어를 생각해보자!
뒤에 a가 팰린드롬이니 제외하고
*wflkjwrglakjgl를 보면,
*에는 wflkjwrglakjgl가 거꾸로 들어가기만 하면 팰린드롬이 될 수 있다!
코드
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 | #include<cstdio> #include<cstring> char str[21]; const char rStr[2][10] = { "Not exist","Exist"}; int main() { int t; scanf("%d\n", &t); for (int i = 1; i <= t; i++) { scanf("%s\n", str); int len = strlen(str); bool res = true; for (int i = 0; i < len / 2; i++) { if (str[i] == '*' || str[len - i - 1] == '*') break; res &= str[i] == str[len - i - 1]; } printf("#%d %s\n",i, rStr[res]); } return 0; } | cs |
이 문제의 핵심은 규칙을 찾는 것이다!
이 문제는 결국 m번 섞는 것이 반복되는 구조이다!
m번 섞는 것이 처음에 비해서 어떻게 변하는지 저장했다고 가정하자!
7자리 숫자는 결국 경우의 수가 7*6*5*4*3*2*1 = 5040이다. 따라서, 5040번을 반복해서 섞는다면, 결국 처음과 같은 번호가 나올 것이다!
(비둘기집의 원리)
따라서, m번 반복한 것이 반복되는 구간을 찾고, 이를 이용해서 모듈라 연산을 하면 쉽게 반복되는 부분을 통해서 어떤 수가 나와야 하는지 쉽게 알 수 있다!
예제 2번을 통해서 알아보자!
9 123456789
1 2
2 5
3 5
4 6
6 7
1 7
4 5
2 3
4 7
m = 9 이고, k = 123456789 이다.
처음 카드셋은 0,1,2,3,4,5,6 이다.
1번과 2번을 바꾸면 1,0,2,3,4,5,6
2번과 5번을 바꾸면 1,4,2,3,0,5,6이다.
이렇게 9번을 바꾸면 결국 3,0,4,1,5,6,2가 된다!
이제 10번 부터는 이를 이용하여 바꾼다! 즉 10번은 18번을 바꾼 카드셋이 된다.
18번을 바꾸면
0번 카드 -> 3번 카드 = 1
1번 카드 -> 0번 카드 = 3
2번 카드 -> 4번 카드 = 5
3번 카드 -> 1번 카드 = 0
4번 카드 -> 5번 카드 = 6
5번 카드 -> 6번카드 = 2
가 된다!
이렇게 쭉 따라가다 보면,
20번 인덱스 즉, 12 * 9 = 108번 바꾸면 다시 처음의 카드셋 0,1,2,3,4,5,6이 나오는 것을 알 수 있다!
따라서 123456789번 바꾸게 되면, 123456789 % 108 = 45번째 카드 순서가 될 수 있다.
이는 반복문으로 충분히 구할 수 있다!
코드
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 | #pragma once #include<cstring> #include<cstdio> int m, order[21][2]; int arrOrder[6000][7]; long long k; int main() { int t; scanf("%d\n", &t); for (int tc = 1; tc <= t; tc++) { scanf("%d %lld\n", &m, &k); for (int i = 0; i < 7; i++) { arrOrder[0][i] = i; } for (int i = 1; i <= m; i++) { scanf("%d %d\n", &order[i][0], &order[i][1]); order[i][0]--; order[i][1]--; for (int j = 0; j < 7; j++) arrOrder[i][j] = arrOrder[i - 1][j]; arrOrder[i][order[i][0]] = arrOrder[i - 1][order[i][1]]; arrOrder[i][order[i][1]] = arrOrder[i - 1][order[i][0]]; } int i = m + 1; for(; i < 6000; i++) { for (int j = 0; j < 7; j++) arrOrder[i][j] = arrOrder[i - 1][arrOrder[m][j]]; bool res = true; for (int j = 0; j < 7; j++) { if (arrOrder[i][j] != j) { res = false; break; } } if(res) break; } long long cnt = (i - m + 1) * m; k %= cnt; for (int i = m + 1; i <= k; i++) { for (int j = 0; j < 7; j++) arrOrder[i][j] = arrOrder[i - 1][j]; int l = (i - 1) % m + 1; arrOrder[i][order[l][0]] = arrOrder[i - 1][order[l][1]]; arrOrder[i][order[l][1]] = arrOrder[i - 1][order[l][0]]; } printf("#%d ", tc); for (int i = 0; i < 7; i++) { printf("%d", arrOrder[(k)][i]); } printf("\n"); } return 0; } | cs |
D7치고는 왠지 도전할만 한 것 같아서 도전했지만.. 생각보다 참패를 당했다.
재귀나 동적 계획법으로 풀어보려고 했지만, 문자열의 길이가 3만이기 때문에 도전하지 못했다.
그래서 몇 가지 경우를 열심히 찾아보았다!
우선 가장 간단한 경우이다. 만약, 두 쌍이 서로 다르다면, 빠른 것을 먼저 선택한다.
하지만, 만약 두 개 중에서 선택해야 할 것을 찾지 못한다면 어떻게 해야할까?
이 때는, 어떠한 것을 넣을지 선택해야할지 모르므로 왼쪽 인덱스는 한칸 오른쪽을 검사하고, 오른쪽 인덱스는 한 칸 왼쪽을 검사한다.
이렇게 검사하다가 만약, 보고있는 문자 둘 다 맨 끝에 있는 문자들보다 사전순으로 뒤에있는 문자라면, g 두 개를 먼저 처리해야하는 것을 알 수 있다. 현재 맨 끝에서부터 지금 보고있는 포인터까지는 모두 g보다 빠른 문자열밖에 없게 만들어 줄 것이므로, z나 h가 나오기 전에 앞의 문자들이 모두 사라져야 한다. 따라서 왼쪽이나 오른쪽 아무거나 하나 집어넣어도 된다.
이는 처음 한글자만 비교할때와 비슷하다. 오른쪽 글자가 사전순으로 앞에 있으므로, 오른쪽이 먼저 사라져야한다. 따라서, 오른쪽 문자를 하나 결과에 붙이도록 한다.
대칭인 경우도 왼쪽이나 오른쪽 아무거나 하나 붙여도 결국 똑같아진다. 따라서 아무거나 하나 결과값으로 옮길 수 있다.
이렇게 하나하나 처리하는 것을 코드로 짜보자!
코드
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 | #pragma once #include<cstring> #include<cstdio> char str[30002]; char res[30002]; int main() { int t; scanf("%d\n", &t); for (int tc = 1; tc <= t; tc++) { int rLen = 0, sLen; int l, le, r, rs; scanf("%s\n", str); sLen = strlen(str); l = le = 0; r = rs = sLen - 1; while (rLen != sLen) { //대칭(홀수) if (rs == le) { res[rLen++] = str[r--]; le = l; rs = r; //1 개남음 if (r == l) { res[rLen++] = str[r]; } continue; } //대칭(짝수) else if (rs < le) { res[rLen++] = str[l++]; le = l; rs = r; continue; } //양쪽이 느림 if (str[le] > str[l] && str[rs] > str[r]) { res[rLen++] = str[l++]; rs = r; le = l; continue; } // 양쪽이 빠르거나 같음 else if (str[le] <= str[l] && str[rs] <= str[r]) { //거기다 대칭 if (str[le] == str[rs]) { le++; rs--; continue; } } // 비대칭 if(str[le] < str[rs]) { res[rLen++] = str[l++]; rs = r; le = l; } else { res[rLen++] = str[r--]; rs = r; le = l; } } res[rLen] = 0; printf("#%d %s\n",tc, res); } return 0; } | cs |
이번에는 코드 배틀에서 좋은 성적을 거두지 못했다!
생각보다 난이도가 어렵게 나왔다. 나온 난이도는 D3, D5, D6, D7이었다.
마지막 문제인 문자열 재구성 프로젝트는 결국 코드 배틀이 끝나고 나서 풀 수 있었다.
결과는 !!
다음에는 더 잘 풀어야지!
'공부 > 알고리즘 문제풀이' 카테고리의 다른 글
| [SW Expert Academy] N-Queen (0) | 2018.06.21 |
|---|---|
| [SW Expert Academy] 장훈이의 선반 (0) | 2018.06.21 |
| [알고스팟] 광학 문자 인식 (0) | 2018.06.18 |
| [알고스팟] 여행 짐 싸기 (2) | 2018.06.17 |
| [알고스팟] 두니발 박사의 탈옥 (0) | 2018.06.17 |
