백준 1467번 : 수 지우기

문제 접근

---

    세준이가 가지고 있는 N 자리 수에서 주어진 수를 하나씩 지워 만들 수 있는 가장 큰 수를 구하는 문제이다. 고민해보다가 앞자리부터 크게 만들면 가장 큰 수가 될 것 같았다. 따라서 0부터 9 까지의 수가 처음으로 나올 때까지 나열되어있는 다른 숫자 개수를 각각 temp 배열에 저장한 뒤, 9부터 0까지의 수를 전부 확인해 temp 배열 값을 다 지울 수 있다면 해당 수는 남도록 구현했다.

 

 

문제 접근

---

// 1:45 ~ 3:10
// 17:35 ~ 20:10
// 01:00 ~ 02:00

#include <iostream>
#include <vector>
#include <string>

// 테스트케이스 확인용 파일 입출력 헤더
#include <fstream>

using namespace std;

// erase_cnt : 지워야하는 수의 개수
// cur : sejun_num 에서의 현재 위치를 나타내는 변수
int erase_cnt, cur;
// 세준이가 가지고 있는 N 자리 수열
vector<int> sejun_num;
// 각 숫자별 지워야 하는 개수
int erase_num[10] = { 0, };

// pos 번째 수를 고정하는 함수
void search(int pos)
{
    // i, j : 반복문에 사용하는 변수
    // temp_cnt : pos 부터 지울 수의 개수
	int i, j, temp_cnt = 0;
    // possible : 지울 수 있는지 여부 확인
	bool possible;
	// temp[x][n] : x 가 나오기까지의 n 의 개수
	int temp[11][11] = { 0, };
	// isIn[x] : x 가 sejun_num 내에 존재하는지 확인
	bool isIn[11] = { false, };

	for (i = 0; i <= 10; ++i)
	{
		isIn[i] = false;
	
        // pos 부터 끝까지 탐색하며 i 가 나올 때까지의 수들을 temp[i] 에 저장한다.
		for (j = pos; j < sejun_num.size(); ++j)
		{
			if (sejun_num[j] == i)
			{
				isIn[i] = true;
				break;
			}

			++temp[i][sejun_num[j]];
		}
		
        // 해당 수가 배열 내에 없다면 전부 -1 로 초기화해준다.
		if (!isIn[i])
		{
			for (j = 0; j <= 10; ++j)
				temp[i][j] = -1;
		}
	}
	
    // 10 은 sejun_num 배열의 마지막에 임의로 추가한 값이다.
    // 10 부터 0 까지의 수 중 가능한 경우를 확인한다.
	for (i = 10; i >= 0; --i)
	{
		if (!isIn[i])
			continue;

		// 맨 앞자리에 0이 나올 수 없으니 멈춘다. -> 지워도 될 듯
		if (i == 0 && pos == 0)
			break;

		possible = true;
		
        // i 가 나올 때까지의 수의 개수가 지워야하는 수의 개수보다 작다면 i 가 pos 번째 수로 고정될 수 있다.
		for (j = 0; j < 10; ++j)
		{
			if (erase_num[j] < temp[i][j])
			{
				possible = false;
				break;
			}
		}

		if (possible)
		{
			// i 의 개수가 지워야 하는 개수랑 같다면 전부 지워야하니 pos 번째 수가 될 수 없다.
			if(temp[10][i] == erase_num[i])
			{
                // 만약 이미 pos 번째에 i 가 있다면 제거한다.
				if (i == sejun_num[pos])
				{
					temp_cnt = 1;
					--erase_num[sejun_num[pos]];
					--erase_cnt;
					--cur;
				}

				else
					continue;
			}
			
            // 지우는 수만큼 지워야하는 개수를 감소시키고, temp_cnt 를 증가시킨다. 
			else
			{
				for (j = 0; j < 10; ++j)
				{
					erase_num[j] -= temp[i][j];
					erase_cnt -= temp[i][j];
					temp_cnt += temp[i][j];
				}
			}
			
            // pos 부터 temp_cnt 개수만큼 지운다.
			sejun_num.erase(sejun_num.begin() + pos, sejun_num.begin() + pos + temp_cnt);

			break;
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int i;
	string input;

	erase_cnt = cur = 0;

	/*
	// Testcase 확인해보는 코드
	
	int num = 0;
	string res;
	string file_in, file_out;
	int success = 0, total = 0;

	while (++num <= 100)
	{
		file_in = "";
		file_out = "";
		sejun_num.clear();

		if (num < 10)
			file_in = "00" + to_string(num);

		else if (num < 100)
			file_in = "0" + to_string(num / 10) + to_string(num % 10);

		else
			file_in = "100";

		file_out = "./testcases/output_" + file_in + ".txt";
		file_in = "./testcases/input_" + file_in + ".txt";

		ifstream in(file_in);
		ifstream out(file_out);

		input = "";
		in >> input;

		for (i = 0; i < input.size(); ++i)
		{
			sejun_num.push_back(input[i] - '0');
		}

		sejun_num.push_back(10);
		input = "";
		in >> input;

		for (i = 0; i < input.size(); ++i)
		{
			++erase_cnt;
			++erase_num[input[i] - '0'];
		}

		cur = 0;

		while (erase_cnt)
		{
			search(cur++);
		}

		i = 0;

		res = "";

		for (; i < sejun_num.size() - 1; ++i)
		{
			res += (sejun_num[i] + '0');
		}
		input = "";
		out >> input;

		if (res == input)
		{
			cout << '[' << num << "] Clear!\n";
			++success;
		}

		else
		{
			cout << '[' << num << "] Fail!\n";
			cout << "Output : " << res << '\n';
			cout << "Answer : " << input << '\n';
		}

		++total;

		in.close();
		out.close();
	}

	cout << "Accuracy : " << (double)success / total * 100 << "%\n";
	*/

	cin >> input;

	for (i = 0; i < input.size(); ++i)
	{
		sejun_num.push_back(input[i] - '0');
	}

	// 숫자별 개수를 구하고 마지막에 문자 하나만 남는 경우 배제하기 위해 임시로 10 추가.
	sejun_num.push_back(10);

	cin >> input;

	for (i = 0; i < input.size(); ++i)
	{
		++erase_cnt;
		++erase_num[input[i] - '0'];
	}
	
    // 지워야하는 수의 개수가 0이 될 때까지 반복
	while (erase_cnt)
	{
		search(cur++);
	}

	i = 0;

	for (; i < sejun_num.size() - 1; ++i)
	{
		cout << sejun_num[i];
	}

	cout << '\n';

	return 0;
}

 

 

문제 접근

---

    두 번째로 풀어본 플레티넘 그리디 문제이다. 그리디 문제는 아이디어만 잘 생각하면 쉽게 풀리는 경우가 많아서 재미있는 것 같다. 하지만 이 문제는 잘 구현한 것 같은데 계속 WA를 받았다. 맞왜틀... 뭐가 문제인지 고민하다가 어떤 분이 올린 테스트케이스를 발견해서 파일 입출력으로 확인해봤다.

 

    알고보니 맨 앞의 수 뿐만 아니라 'pos 번째 수로 고정될 후보 숫자'가 '지워야하는 개수'와 같은지도 확인했어야 되는데 이 부분을 확인 못해서 생긴 문제였다. 앞으로 알고리즘 문제를 풀 때 코드마다 어떤 기능을 원하는지 잘 정리해보고, WA 를 받으면 각 코드가 제대로 기능하는지 부분적 검토를 통해 해결해야겠다. 그리고 이번 기회에 처음으로 외부 텍스트 파일로 저장된 입출력을 다뤄봤는데 좋은 경험이었다. 이번 문제를 풀면서 배운게 많아서 만족스럽다 :)