p.62 Best Cow Line (POJ 3617) - Greedy Algorithm

p.62 Best Cow Line (POJ 3617) - Greedy Algorithm

http://poj.org/problem?id=3617

이 문제는 노란책에서 기초적이면서도 처음 접하면 어려운 문제라고 생각한다.

문제는 다음과 같다.

어떤 문자열이 주어지면 앞이나 뒤에서 문자 하나를 빼서 새로운 문자열을 구성하는데,

이 때 새롭게 만들어지는 문자열이 사전순으로 가장 앞에 있도록 만들려고 한다.

그냥 앞뒤 두 문자 보고 사전순으로 앞에 있는 문자를 가져다 쓰면 될 것 같지만,

앞뒤 두 문자가 같을 때에는 문제가 생긴다.

맨 앞에 있는 문자를 s[b], 맨 뒤에 있는 문자를 s[e]라고 하면,

s[b], s[b+1], s[e]

s[e], s[e-1], s[b]

순서로 만들거나

s[b], s[e], s[b+1]

s[b], s[e], s[e-1]

s[e], s[b], s[b+1]

s[e], s[b], s[e-1]

순서로 만들 수 있을 것이다.

그런데, 여기서 s[b]==s[e]인 경우만 s[b+1]과 s[e-1]에 대해서 조사하므로

s[b]를 C라 하면,

C, s[b+1], C

C, s[e-1], C

C, C, s[b+1]

C, C, s[e-1]

중에 하나가 될 것이다.

그럼 C하나는 반드시 써야한다는 결론이 나오고

그 다음의 오는 문자가 s[b+1], s[e-1], C중 하나여야 한다.

여기서 세 문자를 모두 비교하지 않아도 되는데, s[b+1], s[e-1] 두 문자만 비교하고 C는 고려하지 않아도 된다.

왜냐하면 s[b+1]<s[e-1]인 경우 s[b]를 써야하므로 s[b++]을 화면에 출력한다.

그 다음 반복문을 보면 s[b]와 s[e]를 자연스럽게 비교하게 된다. (여기서 b는 1 증가된 상태)

이는 b를 증가시켜주기 전의 s[b+1]값과 C를 비교하는 것과 같다.

또한, s[b+1]<s[e-1]이라면 s[b+1]이 무조건 먼저 나와야 한다.

그러니까 이탤릭체로 쓴 부분에서 s[e-1]을 고려하지 않아도 된다.

사실 이렇게 이해하는게 맞나 싶긴한데 ㅠ 쉽게 생각할 수 있는 방법은 잘 모르겠다.

아무튼 논리는 맞으니까...

조금 다시 정리를 해보자면,

결국 s[b]==s[e]이면 s[b+1]과 s[e-1]을 비교하면 되고, 이 마저도 같으면 s[b+2]와 s[e-2]를 비교하면 된다.

중간에 s[b+i]와 s[e-i]중 b+i쪽이 사전순으로 앞선다면, 현재 턴에서 s[b]를 먼저 써야 한다는 결론이 나온다.

N제한이 2000이므로 에 충분히 돌아간다. ^^

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
string s, rs;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> s;
    int b=0, e=s.size()-1;
    while(b<=e) {
        bool left = false;
        for(int i=0; b+i<=e; i++) {
            if(s[b+i]<s[e-i]) {
                left=true;
                break;
            } else if(s[b+i]>s[e-i]) {
                left=false;
                break;
            }
        }
        if(left) putchar(s[b++]);
        else putchar(s[e--]);
    }
    return 0;
}

코드는 위와 같은데, POJ에서 80번째 문자마다 개행문자 넣으라는 걸 만들지 않았다.

(책에 있는 코드와 완전히 같다.)

사실 난 이게 생각이 잘 안된다. ㅠ

딱 코포 C번 느낌이다.

기본적인 문제인데.. 뭔가 생각 정리를 할 수가 없다.

답을 보면 "아 저거구나~!" 하는데, 더 쉽게 생각하는 방법이 있으면 누가 댓글좀... ㅠ