ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Baekjoon - 6137] 문자열 생성
    문제 풀이/Baekjoon Online Judge 2023. 2. 13. 22:07

    난이도: Gold IV

     

    태그

    더보기
    • Greedy
    • Two Pointer

     

    풀이

    1. 맨 앞 글자와 맨 뒷 글자가 다르다면, 무슨 글자를 선택해야 할까?

    더보기

    사전순의 정의에 따라, 둘 중 더 빠른 글자를 선택해야 합니다.

     

    2. 맨 앞 글자와 맨 뒷 글자가 똑같은데... 앞에서부터 2번째 글자와 뒤에서부터 2번째 글자가 다르다면?

    더보기

    2번째 글자를 비교한 뒤, 더 빠른 쪽을 선택하면 됩니다.

    이유는, 다음에 보여지게 되는 글자를 생각해보면 됩니다.

    [2]에 대한 증명

    더보기

    길이 N의 문자열 S에 대해, 일반성을 잃지 않고 S1=SN,S2<SN1이라고 해봅시다.

     

    그럼, 아래 경우로 나눠볼 수 있습니다.

    • S1<S2: 어느 쪽을 선택하든 상관없습니다.
      공개되는 글자가 원래 글자보다 뒤쪽이므로 다음 선택은 항상 반대쪽이 되고,
      이는 그냥 S1,SN을 연속으로 선택한다는 것이니, S1=SN를 감안하면 순서는 별 의미 없죠.
    • S1S2: S1,S2를 선택하는 게 최적입니다.
      S1을 선택하면 공개되는 글자가 S2가 되는데, 이는 S2<SN이거나 S2=SN이므로 이미 위에서 커버되었습니다.
      유일한 걱정으로는 SN의 선택인데, SN을 선택한 뒤에 할 수 있는 선택은 S1,SN1이고,
      S1을 선택하면 S1,SN 순서로 선택한 거와 다를 게 없어지고
      SN1을 선택하면 S1,S2보다 더 느린 문자열이 오게 됩니다.

     

    3. 맨 앞 글자와 맨 뒤 글자가 같고, 그 다음도 같고, ..., 그러다가 Sk,SNk+1가 다르다면?

    더보기

    귀납법을 잘 써보면, Sk,SNk+1 중 더 작은 쪽을 선택해주면 됩니다.

     

    4. 문자열이 회문이라서 비교가 불가능하다면?

    더보기

    어느 쪽을 선택하든 만들 수 있는 문자열의 집합은 동일합니다. (문자열을 뒤집어도 동일하니까요.)

    그러니 아무데나 선택해주면 됩니다.

     

    5. 코드

    더보기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    char 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++]; }
            elsecout << 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
Designed by Tistory.