입력으로 문자열이 주어진다.
해당 문자열에서 1과 0을 절반만큼 제거하였을 때 나올 수 있는 문자열중 사전순으로 가장 빠른 것을 출력하면 된다.
예를 들어, 1010이라는 입력이 주어졌다고 가정해보자.
1이 2개이고, 0이 2개이므로 1을 1개 제거하고, 0을 1개 제거하면 된다.
경우는 아래와 같이 총 4개의 경우가 존재할 것이다.
즉, 나올 수 있는 문자열의 후보는 10, 01, 10, 10이다.
이 중, 사전순으로 가장 빠른 문자열은 01이므로, 01을 출력하면 된다.
문제 풀이
풀이는 간단하다.
제거해야할 1의 개수과 0의 개수를 세어준 뒤, 앞에서부터 1을 제거하고 뒤에서부터 0을 제거하면 된다.
0과 1로 이루어진 문자열중 사전순으로 빠른 문자열이라면, 문자열의 앞쪽에서부터 0이 가장 길게 배치되어있어야 한다.
000100, 000010 두 문자열을 비교한다면 첫 문자열은 앞에 0이 3개 배치되어있고 두 번째 문자열은 0이 4개 배치되어있다. 그러므로, 두 번째 문자열이 사전순으로 더 빠르다고 할 수 있을 것이다.
하지만, 이러한 경우도 있다.
000011, 000010 두 문자열의 경우엔 앞의 0의 개수는 똑같다. 그렇기 때문에 앞의 0의 개수로는 사전 정렬 순서를 비교할 수가 없다. 이 땐, 뒤에서부터 1이 몇개가 주어지는 지를 확인하면 된다.
뒤에서부터 세어봤을 때 1이 더 많다면, 사전순으로 더 느린 문자열이라고 할 수 있을 것이다.
그러므로, 어떤 문자열에서 1과 0을 제거해서 사전순으로 가장 빠른 문자열을 만들고 싶다면 앞쪽에 있는 1을 최대한 제거하고, 뒤쪽에 있는 0을 최대한 제거하는 것이 답이될 것이다.
위의 문자열을 보자. 1의 총 개수는 4개이고, 0의 총 개수도 4개이다.
그러므로, 1을 2개 제거하고, 0을 2개 제거해야 한다.
그렇다면, 아래와 같이 제거하는 것이 가장 사전순으로 빠른 문자열을 만드는 방법일 것이다.
가장 앞에 있는 1을 2개 제거하였고, 가장 뒤에있는 0을 2개 제거하였다.
정답 문자열은 0011이 된다.
풀이 코드
std::string InputStr;
std::cin >> InputStr;
int ZeroCount = 0;
int OneCount = 0;
for (int i = 0; i < InputStr.size(); i++)
{
if (InputStr[i] == '0')
{
ZeroCount++;
}
else
{
OneCount++;
}
}
ZeroCount /= 2;
OneCount /= 2;
먼저, 문자열을 입력받은 뒤, 1의 개수와 0의 개수를 세주었다.
그 다음, 1의 개수와 0의 개수를 절반으로 나눠 제거해야 할 개수를 구해주었다.
std::string Answer;
Answer.reserve(ZeroCount + OneCount);다음은 정답을 저장할 문자열을 선언하고, reserve를 이용하여 필요한 크기만큼 메모리를 할당해주었다.
for (int i = 0; i < InputStr.size(); i++)
{
if (OneCount > 0)
{
if (InputStr[i] == '1')
{
OneCount--;
InputStr[i] = '2';
}
}
else
{
break;
}
}
입력받은 문자열을 앞에서부터 선형으로 탐색하며, 현재 문자가 1이라면 OneCount를 1감소시켰고, 동시에 입력 문자열에서 해당 부분을 2로 바꿔주었다. (제거했다는 의미)
그리고, OneCount의 수만큼 모두 제거해주었다면 반복문을 종료해주었다.
for (int i = InputStr.size() - 1; i >= 0; i--)
{
if (ZeroCount > 0)
{
if (InputStr[i] == '0')
{
ZeroCount--;
InputStr[i] = '2';
}
}
else
{
break;
}
}
다음은 뒤에서부터 탐색하며 동일한 과정을 거쳐주었다.
문자가 0이라면, 문자를 2로 바꿔주고 ZeroCount를 감소시키며 계속 탐색하다 ZeroCount가 0이 되면 반복문을 종료해주었다.
for (int i = 0; i < InputStr.size(); i++)
{
if (InputStr[i] != '2')
{
Answer.push_back(InputStr[i]);
}
}
마지막으로 입력 문자열에서 2가 아닌 문자만 추출하여 Answer에 삽입해주었다.
std::cout << Answer;
return 0;
해당 문자열을 출력해주면 문제는 끝이다.
코드 전문
#include <iostream>
#include <vector>
void Init()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
}
int main()
{
Init();
std::string InputStr;
std::cin >> InputStr;
int ZeroCount = 0;
int OneCount = 0;
for (int i = 0; i < InputStr.size(); i++)
{
if (InputStr[i] == '0')
{
ZeroCount++;
}
else
{
OneCount++;
}
}
ZeroCount /= 2;
OneCount /= 2;
std::string Answer;
Answer.reserve(ZeroCount + OneCount);
for (int i = 0; i < InputStr.size(); i++)
{
if (OneCount > 0)
{
if (InputStr[i] == '1')
{
OneCount--;
InputStr[i] = '2';
}
}
else
{
break;
}
}
for (int i = InputStr.size() - 1; i >= 0; i--)
{
if (ZeroCount > 0)
{
if (InputStr[i] == '0')
{
ZeroCount--;
InputStr[i] = '2';
}
}
else
{
break;
}
}
for (int i = 0; i < InputStr.size(); i++)
{
if (InputStr[i] != '2')
{
Answer.push_back(InputStr[i]);
}
}
std::cout << Answer;
return 0;
}'코딩테스트 문제 풀이 (C++)' 카테고리의 다른 글
| 백준 13023 - ABCDE (C++) (0) | 2024.05.04 |
|---|---|
| 백준 20922 - 겹치는 건 싫어 (C++) (1) | 2024.04.30 |
| 백준 1522 - 문자열 교환 (C++) (0) | 2024.04.29 |
| 백준 5464 - 주차장 (C++) (1) | 2024.04.28 |
| 백준 7453 - 합이 0인 네 정수 (C++) (0) | 2024.04.27 |
