[백준/C++] 27740 시프트 연산

블로그 글 옮기는 중..

 

https://www.acmicpc.net/problem/27740

27740번: 시프트 연산

 

처음에는 그냥 가볍게 생각해서 세 가지 경우가 나왔다.

양쪽 끝이 1인 경우, 0인 경우, 다른 경우.

다음은 그때 작성했던 코드인데 나도 알아보기가 힘드므로 그냥 대충 넘기면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <deque>
#include <stack>
#include <cmath>
#include <string>

using namespace std;

void input();
void solve();

int n, one;
deque<int> d;
string ans;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	input();
	solve();

	return 0;
}

void input() {
	cin >> n;
	int num;
	for (int i = 0; i < n; i++) {
		cin >> num;
		d.push_back(num);
		if (num)
			one++;
	}
}

void solve() {
	while (one) {
		bool left = false;
		if (d[0] && d[n - 1]) { // 양쪽 끝이 다 1인 경우
			for (int i = 1; i < n - i - 1; i++) {
				if (d[i] == d[n - i - 1])
					continue;
				if (!d[i]) {
					left = true;
					break;
				}
				else if (!d[n - i - 1])
					break;
			}
		}

		else if (d[0]) { // 처음이 1인 경우
			left = true;
		}

		else if (d[n - 1]) { // 마지막이 1인 경우
			left = false;
		}

		else { // 둘 다 0인 경우
			for (int i = 1; i < n - i - 1; i++) {
				if (d[i] == d[n - i - 1])
					continue;
				if (d[i]) {
					left = true;
					break;
				}
				else if (d[n - i - 1])
					break;
			}

			if (left) {
				while (!d[0]) {
					ans += 'L';
					d.pop_front();
					d.push_back(0);
				}
			}
			else {
				while (!d[n - 1]) {
					ans += 'R';
					d.push_front(0);
					d.pop_back();
				}
			}
		}

		if (left) {
			while (d[0]) {
				ans += 'L';
				one--;
				d.pop_front();
				d.push_back(0);
			}
		}
		else {
			while (d[n - 1]) {
				ans += 'R';
				one--;
				d.push_front(0);
				d.pop_back();
			}
		}
	}

	cout << ans.length() << '\n';
	cout << ans;
}

 

그러니까 딱 끝부분만을 보고 판단해서 시프트를 하는 셈인데 역시 반례가 나왔다.

 

0 1 0 0 0 0 1 1 1 1

 

위 코드에 의하면 결과값은 RRRRRRRRR(9회)이지만 사실 답은 LLRRRRRR(8회)이다. 한쪽을 잠깐 시프트해서 0으로 만든 다음 나머지를 시프트하는 것이다.

 

여기서 내가 간과했던 부분이 나오는데, 앞서 언급했던 세 가지 경우는 모두 한쪽으로만 시프트하는 것을 전제로 한다는 것이다. LLRR처럼 굳이 왔다갔다 하는 경우가 있나? 하는 생각에 그랬던 것 같다.

 

그렇다면 이제 답의 형태는 두 가지이다.

1. 한쪽으로만 시프트하는 경우(LLL... 또는 RRR...)

2. 한쪽으로 잠깐 시프트했다가 다른 쪽으로 시프트하는 경우(LL...RRR... 또는 RR...LLL...)

 

어느 경우에 2번이 1번보다 유리할까? 위 반례를 이용해 고민해 보자.

 

0 1 0 0 0 0 1 1 1 1

 

이 수열은 크게 세 부분으로 나눌 수 있다.

= 왼쪽 부분 + 0이 연속으로 이어지는 부분 + 오른쪽 부분

 

각각의 경우에 대해 연산의 횟수를 구하는 과정은 다음과 같다.

1. 왼쪽 + 0 + 오른쪽

2. 왼쪽 + 왼쪽 + 오른쪽

 

중복되는 부분을 골라내면 결국 [한쪽 구간의 길이 < 0이 이어지는 구간의 길이]일 때  2번이 유리하다는 것을 볼 수 있다.

 

코드 구현 과정

1. 입력을 받으면서 0이 연속으로 이어지는 구간을 구한다 -> zero[i] 배열로 처리

2. 1번 경우 계산 -> 1이 먼저 나오는 쪽부터 시프트하면 됨

3. 2번 경우 계산 -> 수열의 처음/마지막부터 돌리면서 i < zero[i]일 때 정답 갱신

 

* 정답을 갱신할 때에는 일일이 문자열로 처리하면 비효율적인 것 같아 배열을 하나 사용했다.

   memo[0] = 시프트 방향(0: 왼쪽부터 1: 오른쪽부터)

   memo[1-2] = 왼쪽-오른쪽 시프트 횟수

 

* 다 쓰고 나니 중복되는 부분이 많아서 calc 함수로 분리했다.

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

void input();
void solve();
void calc(int, int);

int n;
vector<int> num;
int zero[300001];
int memo[3];
int ans = 300001;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	input();
	solve();
	
	return 0;
}

void input() {
	cin >> n;
	int cnt = 0;
	int idx = 0;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		num.push_back(tmp);
		if (cnt) {
			if (tmp == 0)
				cnt++;
			else {
				zero[idx] = cnt;
				cnt = 0;
			}
		}
		else {
			if (tmp == 0) {
				idx = i;
				cnt++;
			}
		}
	}

}

void solve() {
	// 한쪽으로 미는 경우
	// 양쪽에서 가장 먼저 나오는 1의 위치에 따라 시프트 횟수가 결정됨
	int l = n;
	int r = n;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (num[i]) {
			l = i;
			break;
		}
	}

	for (int i = n - 1; i >= 0; i--) {
		if (num[i]) {
			r = n - i - 1;
			break;
		}
	}

	if (l == r) // 1의 위치가 대칭인 경우
		calc(n - l, 0);
	else
        (l < r ? calc(n - r, 0) : calc(0, n - 1));

	// 한쪽으로 밀었다가 다시 미는 경우
	// 배열에 저장된 0의 개수와 인덱스를 이용해 왼쪽과 오른쪽 개수를 판단
	for (int i = 0; i < n; i++) {
		int z = zero[i];
		if (z) {
			l = i;
			r = n - i - z;
			if (l < z)
				calc(l, l + r);
			if (r < z)
				calc(l + r, r);
		}

	}

	string s = "";
	if (memo[0] == 0) {
		for (int i = 0; i < memo[1]; i++)
			s += 'L';
		for (int i = 0; i < memo[2]; i++)
			s += 'R';
	}

	else {
		for (int i = 0; i < memo[2]; i++)
			s += 'R';
		for (int i = 0; i < memo[1]; i++)
			s += 'L';
	}

	cout << ans << '\n' << s;
}

// 갱신용 함수
void calc(int l, int r) {
    int cnt = l + r;
	if (cnt < ans) {
		memo[0] = l < r ? 0 : 1;
		memo[1] = l;
		memo[2] = r;
		ans = cnt;
	}
}