문제 이해 단계
문제는 아주 단순하다.
AAAA와 BB 두 개의 타일을 가지고 있는데, 주어진 X를 타일로 대체하는 것이다.
같은 경우는 구분하지 않고 그대로 출력하는 것인데,
이건 입력 예제를 보다 보면 바로 이해가 되는 것이기 때문에 자세히 다루지는 않겠다.
문제 접근 단계
이 알고리즘을 푸는 데에는 3가지 포인트가 있다.
1. "."을 기준으로 문자열 X를 나누는 구현
2. AAAA와 BB 타일을 배치하는 방법 구현
3. "-1"을 도출하는 방법 구현
Point 1
. 을 기준으로 문자열을 구분해야 하므로
문자열을 모두 받아 글자 하나하나씩 읽어가는 방식을 선택했다.
"X" 일 때와 "." 일 때를 구분하여 행동을 다르게 하였다.
"X"일 때는 문자열을 순차적으로 읽다가 "."을 만나면
그때까지의 문자열 집합을 AAAA나 BB로 계산하고
이후에는 "."을 출력 한 뒤, 문자열 집합을 초기화하고 해당 작업을 반복했다.
Point 2
이는 위에서 계산하는 문자열의 개수로 판단할 수 있다.
즉, 문자열의 길이가 4개, 2개씩 끊어서 해당 타일을 만들 수 있다.
예를 들어 XXXXXX는 문자열의 길이가 6이기 때문에 AAAA/BB 즉 4/2로 나눌 수 있다.
사전 순으로 출력하는 것이기 때문에 4개인지를 판단하는 작업을 먼저 해주고
그 뒤에 2개인지 판단하는 작업을 해줘야 한다.
작업을 하면서 해당 타일의 길이만큼 빼주면서 반복한다.
Point 3
이 조건은 간단하다.
BB 타일은 2개이기 때문에 짝수이기만 하면 BB 타일을 만들 수 있다.
즉, 문자열의 길이가 홀수이면 불가능하다는 소리이다.
문자열의 길이를 판단했을 때 홀수이면 -1을 출력하도록 하였다.
문제 구현 단계
bool Calculate(string word) {
int size = word.size();
if (size % 2 != 0) {
answer.clear();
answer.push_back("-1");
return true;
}
while (size > 0) {
if (size - 4 >= 0) {
answer.push_back("AAAA");
size -= 4;
}
else {
answer.push_back("BB");
size -= 2;
}
}
return false;
}실질적으로 타일을 배치하는 함수이다.
매개변수로 X의 집합을 받아 계산을 수행하도록 하였다.
일단 "-1"을 판단하기 위해 문자열의 길이가 홀수인지를 판단하였다.
만약 홀수라면 여태까지 answer에 모아뒀던 정답들을 모두 초기화하고 -1만 집어넣는다.
이후 true를 반환하며 함수를 종료한다.
여기서 true를 반환해 주는 이유는 계산이 불가능하다면 더 이상의 반복은 무의미하기 때문이다.
그래서 루프 탈출을 위해 정의해 두었다.
true이면 루프 탈출, false이면 루프를 의미한다.
"-1" 판단 이후, while(size > 0)로 남은 문자 길이가 0보다 클 때까지 반복한다.
위에서 말했듯이 AAAA가 우선순위가 높기 때문에 BB보다 먼저 판단한다.
현재 문자열 길이에서 AAAA만큼 가능할 때(X가 4개 이상일 때)
answer에 "AAAA"를 추가하고 size-4를 해준다.
마찬가지로 size - 4 >0가 아닐 때는 BB를 넣어준다.
여기서 size - 2 > 0를 판단하지 않는 이유는 이미 맨 위에서 "-1" 판단을 해줬기 때문이다.
이 말은 무조건 2의 배수라는 말이므로 AAAA가 아니라면 무조건 BB이다.
for (int i = 0; i < input.size(); i++) {
switch (input[i]) {
case 'X':
word.push_back(input[i]);
break;
case '.':
if (Calculate(word)) {
flag = true;
break;
}
else {
word.clear();
answer.push_back(".");
}
}
if (flag) break;
}
if (!word.empty()) Calculate(word);문자열을 처음부터 하나하나씩 읽어서 판단하는 코드이다.
스위치 문을 통해 해당 인덱스의 문자가 "X"일 때와
"."일 때를 구분하여 동작하도록 하였다.
word라는 변수를 뒀는데 이는 "."을 만나기 직전까지의 문자열들의 모임이다.
예를 들어, XXX.. XXX라면 처음 word는 XXX가 된다.
"."을 만나면 해당 word를 Calculate 함수에 넣고 계산한다.
이후, word를 초기화하고, "."은 그대로 출력해야 하기 때문에 "."을 추가한다.
여기서 Calculate(word)에 if문을 넣어 "-1"로 판단
즉, true라면 flag를 true로 만들고 전체 반복문을 탈출한다.
모든 작업이 끝난 뒤에는 word가 비어있는지 판단하는데 이는 예외케이스를 위한 것이다.
위의 반복문에서는 "."을 만나야 Calculate함수를 실행한다.
만약 XX.. XX에서 마지막 XX를 word에 담아두고 문자열 끝까지 읽었다면,
Calculate 함수를 실행하지 않고 반복문을 탈출한다.
이를 위해서 word가 비어있는지 체크하여 비어있지 않다면
다시 한번 Caculate 함수를 실행해 주는 것이다.
마지막으로 전체코드를 올리며 마무리하겠다.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
static vector<string> answer;
bool Calculate(string word) {
int size = word.size();
if (size % 2 != 0) {
answer.clear();
answer.push_back("-1");
return true;
}
while (size > 0) {
if (size - 4 >= 0) {
answer.push_back("AAAA");
size -= 4;
}
else {
answer.push_back("BB");
size -= 2;
}
}
return false;
}
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
string input;
cin >> input;
string word;
bool flag = false;
for (int i = 0; i < input.size(); i++) {
switch (input[i]) {
case 'X':
word.push_back(input[i]);
break;
case '.':
if (Calculate(word)) {
flag = true;
break;
}
else {
word.clear();
answer.push_back(".");
}
}
if (flag) break;
}
if (!word.empty()) Calculate(word);
for (int i = 0; i < answer.size(); i++) cout << answer[i];
}answer 벡터는 함수에서도 쓰이고 메인문에서도 쓰이기 때문에
static을 통해 전역변수로 설정하였다.
시행착오
실버 5였기 때문에 솔직히 빨리 풀 줄 알았는데 오래 걸렸다.
타일을 배치하는 알고리즘 구현은 금방 됐는데,
의외로 문자열을 구분하는 곳에서 오래 걸렸다.
처음에는 sstream 라이브러리를 사용하여 "."을 기준으로 분리하였는데
이렇게 하니까 "..."이라면 empty가 두 개로밖에 분리되지 않아 더 복잡하고, 코드가 굉장히 어지러워졌다.
특히, 예외케이스를 처리하는 부분이 어렵고, 뭔가 깔끔하지 않아 처음부터 다시 판단하였다.
그래서 String으로 받아 처음부터 하나하나 분석하는 방법을 사용하여 풀었다.
위 문제를 푸는 데 걸리는 시간은 2시간 정도 걸린 것 같다.
실버 5라고 방심했는데, 좀 더 열심히 공부해야겠다.
그리고 덕분에 sstream 라이브러리 사용에 익숙해져서 앞으로는 자주 이용할 것 같다.