SWExpertAcademy의 스타일리쉬 들여쓰기(3378 / d4) 문제이다.
[ 문제풀이 ]
1) 문제에 대한 정확한 이해와 본인이 사용한 풀이법에 대해서 간략하게 알아보자.
(2번으로 바로 넘어가도 무방 !)
먼저 문제에서 무엇을 구해야하는지 부터 확실하게 알아보고 가도록 하자.
입력으로 "전문가가 쓴 문장" 들과 "내가 쓴 문장" 들이 각각의 갯수에 맞게 입력된다.
이 때, "전문가가 쓴 문장"은 스타일리쉬 하게 들여쓰기 잘 되었을수도, 아니면 안되었을 수도 있다.
우리는 "전문가가 쓴 문장" 으로부터 R, C, S의 값들을 찾아서 "내가 쓴 문장"에 R, C, S값을 적용시켜 들여쓰기
를 해야하는 것이 문제이다. 구체적으로 해야 할 일은 밑에서 더 자세하게 알아보도록 하자.
먼저, 문제를 해결하기 위해서 어떤 어떤 방법들이 있는지 한번 생각해보자.
가장 기본적인 방법으로는 "전문가가 쓴 문장"으로 부터 우리는 "미지수가 3개인 연립 방정식"을 구할수가
있다.
여기서 미지수가 3개인 이유는, 소괄호, 중괄호, 대괄호의 갯수에 대한, 즉 수학적인 식으로 써보자면
Rx(소괄호갯수의 차이) + Cy(중괄호갯수의차이) + Sz(대괄호갯수의차이) = 다음줄의 점의 갯수
이런 식으로 연립방정식을 여러개 구해서 R, C, S 값을 구할 수도 있을 것이다. 하지만 본인은 이 연립방정식을
어떻게 코드적으로 구현해야 할지 모르겠어서 다른 방법을 택했다.
그렇다면 본인이 해결한 방법을 알아보자.
본인은, R C S가 이룰 수 있는 모든 순열들을 이용해서 풀어보았다. R C S는 1이상 20이하의 범위를 갖는다.
즉, { R, C, S } = { 1, 1, 1 } , { 1, 1, 2 } , .... , { 20, 20, 20 } 이렇게 20^3 개 만큼의 순열들을 이용해 주었다.
이제부터 자세하고 구체적으로 알아보도록 하자.
2) 본인의 해결방법은 먼저 나올 수 있는 R C S 값의 모든 순열들을 구해놓고 "전문가가 쓴 문장" 으로부터
"가능성 있는 R C S값들" 만 추려내는 것이다. 물론, 여기서 말한 "가능성 있는" R C S 값들이 하나도 없을 수도 있고
한개만 나올수도 있고, 여러개가 나올 수도 있다. 무튼 ! 여기서 이런 가능성 있는 값들을 구해놓고 이 후에 "내가 쓴
문장" 들에 가능성 있는 R C S 값들을 모두 집어넣어봐서 결과를 도출하는 식으로 구현하였다.
문제가 문제인 만큼 우리가 구현해야 할 부분을 순서대로 알아보도록 하자.
3)
1. 가장 먼저, 3차원 배열을 이용해서 모든 순열들을 관리하기 위해서 설정해 주자 !
2. '전문가가 쓴 문장'들의 '.'의 갯수와 괄호의 갯수를 통해서 '가능성 있는 RCS 값들을 구하자!'
3. '가능성 있는 RCS값' 들을 이용해서 '내가 쓴 문장'들의 들여쓰기할 칸 수를 계산하자!'
이제부터 문제의 순서에 맞게 구현방법을 구체적으로 알아보도록 하자.
1. 3차원 배열을 이용한 중복순열값 관리
- 본인은 이를 관리해주기 위해서 3차원 Bool형 배열을 사용해 주었다. (본문 : Perm[21][21][21])
여기서 왜 중복순열인지 부터 알아보도록 하자.
RCS의 값은 { 1, 1, 1 } 이 될 수도 있고, { 1, 2, 3 } 이 될 수도 있다. 혹은 { 2, 1, 3 } 이 될 수도 있다.
즉, 중복된 값들을 선택할 수 있으면서 동시에 순서에 따라 결과가 달라지기 때문에
(R = 1, C = 2, S = 3과 R = 2, C = 1, S = 3 은 확연하게 다른 결과를 초래)
'중복순열'을 모두 구하면 R C S가 가질 수 있는 모든 후보들이 나오게 된다.
"그런데 나는 중복 순열을 구하는 법을 몰라요 !" 라고 할 수도 있는데 사실 이 문제에서는 중복순열을 직접 구할
필요가 없다. 왜 ?? R C S는 초기에 { 1, 1, 1 } 부터 { 20, 20, 20 } 까지 모든 경우를 후보로 가지게 된다.
물론 이 상태에서, "전문가가 쓴 문장"들을 통해 필터링 되면서 후보들이 간추려 지게 될 것이다.
따라서, 아래 코드와 같이 초기값을 설정해 주면 된다.
bool[A][B][C] = true의 의미는 "{ A, B, C } 는 가능성 있는 R C S 조합입니다" 가 된다.
for (int i = 0; i < 21; i++)
{
for (int j = 0; j < 21; j++)
{
for (int k = 0; k < 21; k++)
{
Perm[i][j][k] = true;
}
}
}
// 0이 들어간 조합은 말이 안됨. (R,C,S >= 1 이므로 !)
for (int i = 0; i < 21; i++)
{
for (int j = 0; j < 21; j++)
{
Perm[0][i][j] = Perm[i][0][j] = Perm[i][j][0] = false;
}
}
2. '전문가가 쓴 문장'들의 '.'의 갯수와 괄호의 갯수를 통해서 '가능성 있는 RCS 값들을 구하자!'
- 먼저 x번 문장의 들여쓰는 횟수는 이전 까지의 문장들의 괄호의 갯수를 통해서 결정되게 된다.
즉 0번부터 N번까지의 문장이 있다면, x번 문장의 들여쓰기는 0~x-1번 문장까지의 괄호의 갯수에 영향을 미친다.
또한, 소괄호는 소괄호끼리, 중괄호는 중괄호끼리, 대괄호는 대괄호끼리 서로 여는 괄호와 닫는괄호의 갯수만큼
서로 빼줘야 하므로 한꺼번에 관리할 수가 있다.
본인은 이를 관리해주기 위해서 GwalHo[10][3] 라는 2차원 배열을 사용해주었다.
GwalHo[i][0] = i번째 문장의 소괄호의 갯수 총합. ( '('일때는 ++, ')' 일때는 -- 연산 ! )
GwalHo[i][1] = i번째 문장의 중괄호의 갯수 총합, ( 위와 동일한데 괄호만 중괄호로 ! )
GwalHo[i][2] = i번째 문장의 대괄호의 갯수 총합. ( 위와 동일한데 괄호만 대괄호로 ! ) 가 저장해 주었다.
또한, Dot[] 이라는 배열을 만들어서 각 문장의 '.'의 갯수를 저장해 주는 배열을 생성해주었다.
여기서 한가지 주의해야 할 점은 문장 중간에 있는 '.'은 의미가 들여쓰기의 개념이 아니라는 것이다.
위에서 말한 Dot[] 배열은 들여쓰기를 하는 칸을 대신 표시해주는 '.'을 Count했다는 의미이지, 모든 '.'을 Count했다는
의미가 아니다 !
여기까지 구현을 했다면 우리가 지금까지 한 것은 전문가가 쓴 문장들에 대해서
1. 각 문장별로 소,중,대 괄호의 갯수를 저장
2. 각 문장별로 들여쓰기 한 '.'의 갯수를 저장 했을 것이다.
이제부터 들여쓰기한 칸과 괄호의 갯수를 이용해서 '가능성 있는 RCS값'들을 찾아야 한다.
이 때, 가장 첫 문장은 들여쓰기가 되어 있지 않기 때문에 0번 문장부터 시작했다면 1번문장부터, 1번문장부터
시작했다면 2번문장부터 계산을 해주면 된다.
어떻게 계산을 해야될까?! 우리는 방법을 알고 있따... 단지 코드로 구현하기가 어려울 뿐 !
위에서 말했듯이 "X번 문장의 '.'의 갯수 = 0 ~ X-1번 문장까지의 소,중,대 괄호의 갯수에 영향을 미친다".
우리는 모두 구해놨다. X번 문장의 '.'의 갯수도 구해놨고, 0 ~ X-1번 문장까지의 소,중,대 괄호의 갯수도 이미 구해놨다.
그렇다면, 0 ~ X-1번째 까지의 소괄호들 갯수의 총합, 중괄호들 갯수의 총합, 대괄호의 총합을 구해서
'가능성 있는 RCS값'들과 하나하나씩 계산했을 때, '.'의 갯수가 나오지 않는다면 '가능성 없는' RCS로 바꿔주기만 하면
된다.
" R x (0 ~ X-1번째 까지의 소괄호의 갯수) + C x (0 ~ X-1번째 까지의 중괄호의 갯수) +
S x (0 ~ X-1번째 까지의 대괄호의 갯수 = X번 문장의 '.'의 갯수와 일치하는가 ? " 를 판단하면 되는것이다.
이 부분을 아래의 코드를 통해서 알아보도록 하자.
void Check_Value(int S, int M, int L, int Idx)
{
for (int i = 0; i < 21; i++)
{
for (int j = 0; j < 21; j++)
{
for (int k = 0; k < 21; k++)
{
if (Perm[i][j][k] == false) continue; // 가능성 없는 RCS는 pass.
if ((i*S + j*M + k*L) != Dot[Idx]) Perm[i][j][k] = false;
// 가능성 있는 RCS값들을 각각에 알맞게 곱해주고 더하는 연산을 했을때의
// 결과가 현재 문장의 '.'의 갯수와 일치하지 않으면
// 그 RCS값들은 가능성이 없는 RCS값이 되어버린다 !
}
}
}
}
// ################### 여기부터 보세요 !! ########################
for (int i = 1; i < P; i++) // 0번 문장이 아닌 1번 문장부터 시작
{
int Small = 0, Middle = 0, Large = 0;
for (int j = 0; j < i; j++) // 0번부터 i - 1번째 문장까지
{
Small = Small + P_GwalHo[j][0]; // 소괄호의 갯수 모두 더해주기
Middle = Middle + P_GwalHo[j][1]; // 중괄호의 갯수 모두 더해주기
Large = Large + P_GwalHo[j][2]; // 대괄호의 갯수 모두 더해주기
}
Check_Value(Small, Middle, Large, i); // 가능성 있는 RCS값 찾기위한 함수 호출 !
}여기까지 우리가 뭘 한걸까??? 이 쯤에서 정리하자 !
우리는 지금까지 "전문가들이 쓴 문장"을 통해서 가능성 있는 RCS값들만 남겨 놓았다.
그걸 우리가 어떻게 알아요?? 가능성 있는 RCS값들은 Perm[][][] = true 로 저장되어 있을 것이다 !
3. '가능성 있는 RCS값' 들을 이용해서 '내가 쓴 문장'들의 들여쓰기할 칸 수를 계산하자!'
- 내가 쓴 문장도 전문가가 쓴 문장과 같이 첫 번째 문장은 볼 필요가 없다. 두 번째 문장부터만 계산을 해주면 된다.
내가 쓴 문장들 또한 괄호의 갯수를 알고 있어야 하기 때문에, 위에서 전문가들이 쓴 문장들의 괄호의 갯수를
구할 때 처럼 똑같이 먼저 각 문장별 소,중,대 괄호의 갯수를 모두 구해주자.
두 번째 문장부터 이전에 구해놓은 '가능성 있는 RCS값'들을 모두 넣어보면서 들여쓰기 하는 칸을 구해주면 된다.
여기서 문제가 끝이라면 정말 좋겠지만 여기서 끝나기 위해서는
'가능성 있는 RCS'가 한 개뿐이여야 한다. 만약 우리가 추려낸 가능성 있는 RCS의 값이 1개 뿐이라면 무조건 그 값을
집어 넣는게 정답이 된다. 하지만, 우리에게는 3가지 경우가 존재한다...
1. 전문가들이 들여쓰기를 자기 마음대로해서 그나마 추려낸 RCS값들이 0개라면 ??
2. 가장 이상적인 RCS값이 1개라면 ??
3. 가장 화가나는 RCS값이 2개 이상이라면 ??
문제를 다시한번 읽어보자면 전문가들이 몇 번 들여쓰기를 정확하게 하지 않아서 내 문장을 어떻게 들여써야할지
결정이 되지 않는다면 -1을 출력하라는 조건이 있다....
그렇다면, RCS값들이 0개라면 내 문장을 들여쓰기를 어떻게 해야 될지 모르는 상황이기 때문에 -1을 출력해야
맞는 것이다. 즉, 현재 문장에 들여쓰기를 해야되는 칸 수의 초기값은 -1이 된다.
RCS개 1개인 경우는 뭐 답이 그냥 나오니까 일단 넘어가도록 하자.
2개 이상인 경우는 어떻게 해야될까 ???
예를 들어서 한번 생각해보자.
우리가 추려낸 가능성 있는 RCS = { 1, 1, 1 } , { 1, 1, 2 } , { 1, 2, 3 } 이 있고
현재 문장의 들여쓰기를 위해서 이전까지 문장의 괄호의 갯수를 세었더니
소괄호는 1개, 중괄호는 0개, 대괄호는 0개가 있었다고 생각해보자.
위의 RCS값들을 순서대로 넣어보면
(1 x 1) + (1 x 0) + (1 x 0) = 1
(1 x 1) + (1 x 0) + (2 x 0) = 1
(1 x 1) + (2 x 0) + (3 x 0) = 1
로 모든 결과가 다 동일하게 나오게 된다. 이게 뭘 의미할까 ?? 바로 들여쓰기할 칸수를 의미하는 것이다.
즉, 현재 문장에는 '1'칸을 들여쓰기 하시면 되요 를 의미한다.
그럼 바꿔서, 소괄호 1개, 중괄호 1개, 대괄호 2개가 있었다고 생각해보자.
위의 RCS값들을 순서대로 넣어서 계산해보면
(1 x 1) + (1 x 1) + (1 x 2) = 4
(1 x 1) + (1 x 1) + (2 x 2) = 6
(1 x 1) + (2 x 1) + (3 x 2) = 9
이렇게 결과가 서로 다르게 나오는 경우가 있다. 이게 뭘 의미할까 ??
들여쓰기할 정확한 칸수가 정해지지 않아서 몇칸을 들여써야 할지 모르겠는 상황인 것이다.
즉, "-1"이 출력되야 하는 상황이 이러한 상황이다.
이 부분을 어떻게 구현해야할까...??? 코드와 주석 설명을 보면서 이해해보자.
int Count = 0;
int Value = 0;
int Temp_Result = -1;
for (int i = 0; i < 21; i++)
{
for (int j = 0; j < 21; j++)
{
for (int k = 0; k < 21; k++)
{
if (Perm[i][j][k] == true) // 가능성 있는 RCS값들에 대해서
{
Value = S * i + M * j + L * k; // 일단 계산을 해보고
Count++; // 계산한 횟수++
if (Count == 1) // This is First Answer // 만약 첫 번째 계산이라면??
{
Temp_Result = Value; // 일단 임시적으로 그 결과를 답으로 선택
}
else // 두 번 이상 계산을 했다면? = 가능성 있는 RCS값들이 2개 이상이라면?
{
if (Value != Temp_Result) // 현재 결과와 이전의 결과를 비교
{
Temp_Result = -1; // 다르다면 -1이 정답 !
}
}
}
}
}
}
이제 모든 문제 풀이가 끝났따 ! 문제가 문제인 만큼 풀이도 굉장히 길다보니 마지막으로 소스코드 참고하기 편하도록
본인이 사용한 변수명과 함수명들을 정리해주고 끝내겠다.
int P_GwalHo[MAX][3] = 전문가들이 쓴 문장의 괄호의 갯수를 저장하기 위한 변수.(0 = 소, 1 = 중, 2 = 대)
int Q_GwalHo[MAX][3] = 내가 쓴 문장의 괄호를 갯수를 저장하기 위한 변수.(0 = 소, 1 = 중, 2 = 대)
int Dot[MAX] = 전문가들이 쓴 문장에서 '.'의 갯수를 이용해서 몇 칸을 들여썼는지 확인하기 위한 변수.
bool Perm[21][21][21] = 가능성 있는 RCS값들을 찾고 관리하기 위한 bool형 배열.
vector<int> Answer = 정답을 저장하는 함수
void Count_Dot_And_GH_Num(char C)
= C가 'P'일 경우 전문가들이 쓴 문장의 '.'의 갯수와, 괄호의 갯수를 Count하기 위한 함수.
여기서 Count한 결과값들을 P_GwalHo[][] 와, Dot[] 에 저장해준다.
= C가 'Q'일 경우 내가 쓴 문장의 괄호의 갯수를 Count하기 위한 함수.
여기서 Count한 결과값들을 Q_GwalHo[][]에 저장해준다.
void Check_Value(int S, int M, int L, int Idx)
= 전문가들이 쓴 문장에서 가능성 있는 RCS값들을 판단하기 위해서 사용된 함수.
void Find_Answer(int S, int M, int L)
= 내가 쓴 문장들을, 가능성 있는 RCS값들을 통해서 정답을 도출하는 함수.
[ 소스코드 ]
#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#define endl "\n"
#define MAX 10
using namespace std;
int P, Q;
int P_GwalHo[MAX][3];
int Q_GwalHo[MAX][3];
int Dot[MAX];
bool Perm[21][21][21];
string P_Str[MAX], Q_Str[MAX];
vector<int> Answer;
void Initialize()
{
memset(Dot, 0, sizeof(Dot));
memset(Q_GwalHo, 0, sizeof(Q_GwalHo));
memset(P_GwalHo, 0, sizeof(P_GwalHo));
for (int i = 0; i < MAX; i++)
{
P_Str[i].clear();
Q_Str[i].clear();
}
Answer.clear();
for (int i = 0; i < 21; i++)
{
for (int j = 0; j < 21; j++)
{
for (int k = 0; k < 21; k++)
{
Perm[i][j][k] = true;
}
}
}
for (int i = 0; i < 21; i++)
{
for (int j = 0; j < 21; j++)
{
Perm[0][i][j] = Perm[i][0][j] = Perm[i][j][0] = false;
}
}
}
void Input()
{
cin >> P >> Q;
for (int i = 0; i < P; i++)
{
string Inp; cin >> Inp;
P_Str[i] = Inp;
}
for (int i = 0; i < Q; i++)
{
string Inp; cin >> Inp;
Q_Str[i] = Inp;
}
}
void Count_Dot_And_GH_Num(char C)
{
if (C == 'P')
{
for (int i = 0; i < P; i++)
{
bool Middle_Dot = false;
for (int j = 0; j < P_Str[i].length(); j++)
{
if (P_Str[i][j] == '.')
{
if (Middle_Dot == false)
{
Dot[i]++;
}
}
else
{
Middle_Dot = true;
if (P_Str[i][j] == '(') P_GwalHo[i][0]++;
else if (P_Str[i][j] == ')') P_GwalHo[i][0]--;
else if (P_Str[i][j] == '{') P_GwalHo[i][1]++;
else if (P_Str[i][j] == '}') P_GwalHo[i][1]--;
else if (P_Str[i][j] == '[') P_GwalHo[i][2]++;
else if (P_Str[i][j] == ']') P_GwalHo[i][2]--;
}
}
}
}
else
{
for (int i = 0; i < Q; i++)
{
for (int j = 0; j < Q_Str[i].length(); j++)
{
if (Q_Str[i][j] == '(') Q_GwalHo[i][0]++;
else if (Q_Str[i][j] == ')') Q_GwalHo[i][0]--;
else if (Q_Str[i][j] == '{') Q_GwalHo[i][1]++;
else if (Q_Str[i][j] == '}') Q_GwalHo[i][1]--;
else if (Q_Str[i][j] == '[') Q_GwalHo[i][2]++;
else if (Q_Str[i][j] == ']') Q_GwalHo[i][2]--;
}
}
}
}
void Check_Value(int S, int M, int L, int Idx)
{
for (int i = 0; i < 21; i++)
{
for (int j = 0; j < 21; j++)
{
for (int k = 0; k < 21; k++)
{
if (Perm[i][j][k] == false) continue;
if ((i*S + j*M + k*L) != Dot[Idx]) Perm[i][j][k] = false;
}
}
}
}
void Find_Answer(int S, int M, int L)
{
int Count = 0;
int Value = 0;
int Temp_Result = -1;
for (int i = 0; i < 21; i++)
{
for (int j = 0; j < 21; j++)
{
for (int k = 0; k < 21; k++)
{
if (Perm[i][j][k] == true)
{
Value = S * i + M * j + L * k;
Count++;
if (Count == 1) // This is First Answer
{
Temp_Result = Value;
}
else
{
if (Value != Temp_Result)
{
Temp_Result = -1;
}
}
}
}
}
}
Answer.push_back(Temp_Result);
}
void Solution()
{
// About P's string
Count_Dot_And_GH_Num('P'); // Count String's Dot Num & Save.
for (int i = 1; i < P; i++)
{
int Small = 0, Middle = 0, Large = 0;
for (int j = 0; j < i; j++)
{
Small = Small + P_GwalHo[j][0];
Middle = Middle + P_GwalHo[j][1];
Large = Large + P_GwalHo[j][2];
}
Check_Value(Small, Middle, Large, i);
}
//for (int i = 0; i < 21; i++)
//{
// for (int j = 0; j < 21; j++)
// {
// for (int k = 0; k < 21; k++)
// {
// if (Perm[i][j][k] == true)
// {
// cout << " { " << i << " , " << j << " , " << k << " } " << endl;
// }
// }
// }
//}
// About Q's string
Answer.push_back(0); // First String have only Zero Value.
Count_Dot_And_GH_Num('Q');
for (int i = 1; i < Q; i++)
{
int Small = 0, Middle = 0, Large = 0;
for (int j = 0; j < i; j++)
{
Small = Small + Q_GwalHo[j][0];
Middle = Middle + Q_GwalHo[j][1];
Large = Large + Q_GwalHo[j][2];
}
Find_Answer(Small, Middle, Large);
}
}
void Solve()
{
int Tc; cin >> Tc;
for (int T = 1; T <= Tc; T++)
{
Initialize();
Input();
Solution();
cout << "#" << T << " ";
for (int i = 0; i < Answer.size(); i++)
{
cout << Answer[i] << " ";
}
cout << endl;
}
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen("Input.txt", "r", stdin);
Solve();
return 0;
}
'[ SWEA Code ] > # SWEA - ' 카테고리의 다른 글
| [ SWEA 5648 ] 원자 소멸 시뮬레이션 (C++) (0) | 2019.04.09 |
|---|---|
| [ SWEA 2112 ] 보호 필름 (C++) (2) | 2019.04.09 |
| [ SWEA 1873 ] 상호의 배틀필드 (C++) (0) | 2019.03.10 |
| [ SWEA 1213 ] String (C++) (0) | 2019.03.04 |
| [ SWEA 1251 ] 하나로 (C++) (2) | 2019.03.04 |