근데 그럼 그렇지, 이 입력값을 통해 원본판의 상하반전을 적용하여 재 압축한 결과를 출력해라.
처음예시에서 이게 무슨말인지 몰라 이해하는데 시간이 걸렸다.
저게 띄어써서 헷갈리는데 xxwwwb xwxxbbbww xxxwwbbbwwwwb b로 보면 이해할 수 있다.
||해결 계획
이런 하나의 페이지를 나누어 문제를 해결 = 분할정복 유형
처음에 여러 생각을 했었는데 그중 하려던게
1. 원본을 구해놓고
2. 상하 반전을 적용하고
3. 다시 재압축 하는것이다.
근데 생각해보니까 굳이 상하반전을 할 필요없이 합치는 순서를 다르게 하면 상하반전 처럼 보이지 않을까 했다.
처음에 1 + 2 + 3 + 4 순서로 합했다면, 3 + 4 + 1 + 2 로 합치면 상하반전이 된다!
1. 이 아이디어로 재귀를 전개했다.
이렇게 하면 Solve가 상하반전한 문자열을 반환해 준다.( = 믿는다)
각 4부분에서도 상하반전한 문자열을 반환 한다고 한다.( = 믿는다)
그럼 결국에는 상하반전한 문자열을 반환할것이다.
2. 그리고 Base case를 생각해본다.
base case는 문제의 최소단계 즉, 계속 4등분되면서 한칸이 될 때다.
||계획 검증
이 예시로 처음으로 재귀의 마지막이 될때까지만 써보자
x는 이 그림의 압축 문자열인 xwxwbbbww 이다.
첫번째 재귀
1 : x[0] = 'x' + Solve()
두번째 재귀
1 : x[1] = 'w'
2 : x[2] = 'x' + Solve()
세번째 재귀
1 : x[3] = 'w'
2 : x[4] = 'b'
3 : x[5] = 'b'
4 : x[6] = 'b'
재조합 : bbwb반환
두번째 재귀
1 : 'w'
2 : x + bbwb
3 : x[7] = w
4 : x[8] = w
재조합 : wwwxbbwb 반환
첫번째 재귀 (제일 상단 레벨이라 한가지 밖에 없다!)
1 : 'x' + wwwxbbwb
재조합 : xwwwxbbwb 반환
출력 : xwwwxbbwb
그럼 상하반전과 맞는지 확인하자.
이대로 압축을 해보면
xwwwxbbwb로 정답이 나온다.
하지만 위의 설계와 다른부분이 있는데 첫번째 재귀가 그렇다.
이는 main에서 따로 작성해주면 될것같다!
||구현
#include <iostream>
#include <queue>
#include <string>
using namespace std;
queue<char> q;
//현재 레벨 트리의 각 4분면 string을 구하고 재 조합하여 반환한다!
//불변식 : 이전레벨의 x는 없다.
string Solve(int lev)
{
//base case : 1칸일때, 두 가지 경우가 있다.
//1)최소레벨일때의 1칸, 2)최소레벨이 되지 않았을 때의 한칸
if (lev == 0 || q.size() == 1)
{
string ret(1, q.front()); q.pop();
return ret;
}
//1. 각 4분면의 문자열 저장
string temp[4];
for (int i = 0; i < 4; ++i)
{
temp[i] = q.front(); q.pop();
if (temp[i] == "x") temp[i] += Solve(lev - 1);
}
//2. 재 합성후 반환
return temp[2] + temp[3] + temp[0] + temp[1];
}
int main()
{
int n; cin >> n;
while (n--)
{
//1. Input value
queue<char> tq; q = tq;
string ts; cin >> ts;
for (auto & d : ts) q.push(d);
//2. Do solve
string ret(1, q.front()); q.pop();
if (ret == "x") ret += Solve(20);
cout << ret << "\n";
}
return 0;
}
||되돌아보기
들어온 값을 앞에서 부터 빼고 싶어서 queue를 사용해 입력값을 받았다.
그리고 불변식부분을 생각안하니까 헷갈렸는데
불변식으로 확정지으니까 편하게 작성할 수 있었다.
당황했던거는 최소 트리 레벨을 0으로 해야하는데 1로 작성을 잘못했던 것
그리고 기억할것은 상하반전이라는 부분문제를 좀 더 효율적으로 생각해본것에 있다.
다른 문제에서도 부분문제를 좀 더 효율적이게 생각해야지!
||개선 코드
입력값을 큐를 쓰지 않고 순회하는 방법을 적용해봤다.
더 가벼워진 느낌이다.
string str;
//현재 레벨 트리의 각 4분면 string을 구하고 재 조합하여 반환한다!
//불변식 : 이전레벨의 x는 없다.
string Solve(string::iterator& it, int lev)
{
//base case : 1칸일때, 두 가지 경우가 있다.
//1)최소레벨일때의 1칸, 2)최소레벨이 되지 않았을 때의 한칸
if (lev == 0 || it + 1 == str.end())
{
return string(1, *(it++));
}
//1. 각 4분면의 문자열 저장
string temp[4];
for (int i = 0; i < 4; ++i)
{
temp[i] = *(it++);
if (temp[i] == "x")
{
temp[i] += Solve(it, lev - 1);
}
}
//2. 재 합성후 반환
return temp[2] + temp[3] + temp[0] + temp[1];
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0);
string n; cin >> n;
//1.Check One & Zero
if (n == "0" || n == "1")
{
cout << n;
return 0;
}
//2. Calculate n + n
string ret;
bool plus = false;
while (0 < n.size())
{
int a = n.back() - '0';
n.pop_back();
a = plus ? a + a + 1 : a + a;
plus = 9 < a ? true : false;
ret += to_string(a % 10);
}
if (plus == true) ret += '1';
//3. And then ret minus 2
bool minus = false;
int temp = ret.at(0) - '0' - 2;
if (temp < 0)
{
minus = true;
temp += 10;
}
ret.at(0) = temp + '0';
int k = 1;
while (minus == true)
{
temp = ret.at(k) - '0' - 1;
if (0 <= temp)
{
ret.at(k) = temp + '0';
break;
}
//음수일 때
temp += 10;
ret.at(k) = temp + '0';
++k;
}
//3. Print
if(ret.back() != '0') cout << ret.back();
for (int i = ret.size() - 2; -1 < i; --i)
{
cout << ret.at(i);
}
return 0;
}
||되돌아보기
70자리수인걸 몰라봤던게 굉장히 아쉽다.
그 후에는 96%에서 계속 오답처리가 나오길래 예외를 생각해보았는데
해결했던게 0, 1처리였고 뺄셈을 계산했을 때 첫 자리가 0이면 제외되지 않는 경우가 있었다.
ex) N = 5 / result 08
시간은 한시간 정도 걸렸지만 예외도 잘 찾았고 끝까지 잘 풀어내서 좋았다.
||개선 코드
2를 빼는 부분을 더 간단하게 할 수 있을것 같아 줄여보았다.
//3. And then ret minus 2
int k = 0;
while (true)
{
if (k == 0) ret.at(k) -= 2;
else ret.at(k) -= 1;
//양수면
if ('0' <= ret.at(k)) break;
//음수일 때
ret.at(k) += 10;
++k;
}
아래는 다른 분의 코드인데 주석을 달아 분석해봤다.
#include <stdio.h>
#include <string.h>
using namespace std;
int l;
char a[100];
int main() {
int i;
scanf("%s", &a);
l = strlen(a);
//0 ~ 2까지는 값이 똑같다.
if (l == 1 && a[0] < '3') printf("%s", a);
//그 나머지 부분
else
{
//문자열의 zero based 사이즈 구함
l--;
//문자열의 처음부터 끝까지 반복하며 정수화 함.
for (i = 0; i <= l; i++)
{
a[i] -= '0';
}
//※1을 빼는 이유는 밑에서 *2를 해주기 위해서임.
//문자열의 마지막 수에서 1을 뺀다.
a[l]--;
//size값 복사
i = l;
//뒤에서부터 처음까지 양수가 나올때까지 탐색한다.
while (a[i] < 0)
{
//음수이기에 앞의 자리에서 10을 빌려오는것.
a[i] += 10;
//탐색자리수를 먼저 땡겨주고, 빌려준 자리를 정산한다.
a[--i]--;
}
//처음부터 끝까지 돌며 *2를 해준다.
for (i = 0; i <= l; i++)
{
a[i] *= 2;
}
//*2를 한 결과에서 다음 자리 수에게 올려줄 수가 있으면 계산해준다.
//중요한건 index 1까지만 계산한다.
for (i = l; i >= 1; i--)
{
if (10 <= a[i])
{
a[i] -= 10;
a[i - 1]++;
}
}
//결과 출력
//정수형으로 출력하기 때문에 위에서 마지막자리가 추가되도 가능했던것이다.
for (i = 0; i <= l; i++)printf("%d", a[i]);
}
}
