boj, 백준) 2812 크게만들기( C, C++ )

1. 문제 링크

https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

2. 문제 개요

 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램 작성하기.

 

3. 문제 힌트

 시간 초과에 유의하기. -> N이 최대 500,000이므로 O(N^2)로는 구현하면 안 됨.

 즉, 1회의 Search로 답을 구해야 함.

 

여러 가지 예제를 직접 만들어보고 규칙 찾기, 앞 숫자와 뒷 숫자 간의 관계 등등.. 어떨 때 삭제하고 어떨때 남겨두는지 생각해보기.

 

4. 문제 풀이

(1) 자료구조. -> List를 사용했다. 단어 list를 만들어 조건에 맞으면 삭제하고 삽입하고자 하여 O(1)의 삽입 삭제 시간을 갖는 list선택.

 생각했던 것보다 실행시간이 길게 나와서 다른 분들의 풀이를 봤는데 Deque를 사용하신 분도 있었다.

※ List는 항상 생각했던 것보다 실행시간이 길게 나온다. 얼마 전에 찾아보니까 binary search 할 때도 Legacy Random Access Iterator는 뭐 nlogn이 아닌 n에 근접한다는 글도 봤던 것 같고.. 조금 더 공부해야겠다고 생각

 

(2) 알고리즘 -> 예제로 설명해보겠습니다.

 N = 4, K = 2 , STR = 1924..이다. 0번 index에서 n-2번 index까지 순회한다고 하고, (다음 index를 확인하므로 마지막인 n-1이 아닌 n-2까지)

x번째의 숫자가 x+1번째의 숫자보다 작으면  x번째 숫자를 POP / ERASE

크면 아무 일을 하지 않고 다음 index로 넘어가는 규칙을 찾을 수 있습니다.

그리고 K개를 지우지 않았음에도 불구하고 n-2번째의 index까지 도달했다면, 

모두 같거나 나보다 작은 수이기 때문에 맨뒤의 숫자부터 모자란 수만큼 제거해줍니다.

 

예를 들어 6 2 / 654321이면 아무 일 없이 순회가 끝납니다. 제거한 수는 0인데 K=2이므로 2개를 뒤에서부터 지워주면

6543이라는 정답을 얻을 수 있습니다.

 

5. 코드

#include <cstdio>
#include <list>
using namespace std;

int n, k;
list<int> str;

int main()
{
	scanf("%d %d ", &n, &k);

	for (int i = 0; i < n; ++i) {
		char c;
		scanf("%c", &c);
		str.push_back(c - '0');
	}

	int delnum = 0;

	list<int>::iterator iter;
	for (iter = str.begin(); iter != str.end();)
	{
		list<int>::iterator next = iter;
		next++;
		if (next == str.end())
			break;

		if (*iter >= *next)
		{
			iter++;
			continue;
		}
		else if (*iter < *next)
		{
			iter = str.erase(iter); //iter++포함.

			if (iter != str.begin())
				--iter;

			if (++delnum == k)
				break;
		}
	}
	if (delnum != k)
		for (int i = delnum; i < k; ++i)
			str.erase(--str.end());



	list<int> ::iterator ret;
	for (ret = str.begin(); ret != str.end(); ret++)
		printf("%d", *ret);

	return 0;
}

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~