-
[Baekjoon - 6137] 문자열 생성문제 풀이/Baekjoon Online Judge 2023. 2. 13. 22:07
난이도: Gold IV
태그
더보기- Greedy
- Two Pointer
풀이
1. 맨 앞 글자와 맨 뒷 글자가 다르다면, 무슨 글자를 선택해야 할까?
더보기사전순의 정의에 따라, 둘 중 더 빠른 글자를 선택해야 합니다.
2. 맨 앞 글자와 맨 뒷 글자가 똑같은데... 앞에서부터 2번째 글자와 뒤에서부터 2번째 글자가 다르다면?
더보기2번째 글자를 비교한 뒤, 더 빠른 쪽을 선택하면 됩니다.
이유는, 다음에 보여지게 되는 글자를 생각해보면 됩니다.
[2]에 대한 증명
더보기길이
의 문자열 에 대해, 일반성을 잃지 않고 이라고 해봅시다.그럼, 아래 경우로 나눠볼 수 있습니다.
: 어느 쪽을 선택하든 상관없습니다.
공개되는 글자가 원래 글자보다 뒤쪽이므로 다음 선택은 항상 반대쪽이 되고,
이는 그냥 을 연속으로 선택한다는 것이니, 를 감안하면 순서는 별 의미 없죠. : 를 선택하는 게 최적입니다. 을 선택하면 공개되는 글자가 가 되는데, 이는 이거나 이므로 이미 위에서 커버되었습니다.
유일한 걱정으로는 의 선택인데, 을 선택한 뒤에 할 수 있는 선택은 이고, 을 선택하면 순서로 선택한 거와 다를 게 없어지고 을 선택하면 보다 더 느린 문자열이 오게 됩니다.
3. 맨 앞 글자와 맨 뒤 글자가 같고, 그 다음도 같고, ..., 그러다가
가 다르다면?더보기귀납법을 잘 써보면,
중 더 작은 쪽을 선택해주면 됩니다.4. 문자열이 회문이라서 비교가 불가능하다면?
더보기어느 쪽을 선택하든 만들 수 있는 문자열의 집합은 동일합니다. (문자열을 뒤집어도 동일하니까요.)
그러니 아무데나 선택해주면 됩니다.
5. 코드
더보기1234567891011121314151617char arr[2020];void Main(){int n; cin >> n;for (int i = 1; i <= n; i++){ cin >> arr[i]; }int st = 1, ed = n;for (int i = 1; i <= n; i++){int p1 = st, p2 = ed;while (p1 <= p2){if (arr[p1] != arr[p2]){ break; }p1++; p2--;}if (p1 > p2 || arr[p1] < arr[p2]){ cout << arr[st++]; }else{ cout << arr[ed--]; }if (i%80 == 0){ cout << endl; }}}cs '문제 풀이 > Baekjoon Online Judge' 카테고리의 다른 글
[Baekjoon - 22443] Minus One (0) 2023.02.13 [Baekjoon - 3973] Time To Live (0) 2023.02.13 [Baekjoon - 2115] 갤러리 (0) 2023.02.13 [Baekjoon - 24759] Slide Count (0) 2023.02.13 [Baekjoon - 18392] SHOP (0) 2023.02.13