(프로그래머스) 큰 수 만들기

문제 링크

• 프로그래머스

요약

• 감소하다가 증가하는 지점을 찾는 문제에서는 stack을 사용하자.

최종 §

결과

• 핵심은 인접한 두 수에 대해 뒤에있는 놈이 더 크면 앞에있는놈을 지우는 것이다.
• 그래서 아래 코드처럼 stack에 쭉 쌓다가, 더 큰놈이 들어오면 이놈이 작아질때까지 pop하면 된다.

#include <string>
#include <vector>
 
using namespace std;
 
string solution(string number, int k) {
	string stk = "";
 
	for (auto n : number) {
		while (k > 0 && !stk.empty() && stk.back() < n) {
			stk.pop_back();
			k--;
		}
		stk.push_back(n);
	}
 
	while (k > 0) {
		stk.pop_back();
		k--;
	}
 
	return stk;
}

삽질 기록 §

코드1: deleted set 사용

#include <string>
#include <vector>
#include <set>
 
using namespace std;
 
string solution(string number, int k) {
	set<int> deleted_idx;
	string ret = "";
 
	for (int i = 0; i < k; i++) {
		for (int to_delete = 0; to_delete < number.size(); to_delete++) {
			if (deleted_idx.find(to_delete) == deleted_idx.end()) {
				int next = -1;
 
				for (int j = to_delete + 1; j < number.size(); j++) {
					if (deleted_idx.find(j) == deleted_idx.end()) {
						next = j;
						break;
					}
				}
 
				if (next < 0) {
					deleted_idx.insert(to_delete);
					break;
				} else if (number[to_delete] < number[next]) {
					deleted_idx.insert(to_delete);
					break;
				}
			}
		}
	}
 
	for (int i = 0; i < number.size(); i++) {
		if (deleted_idx.find(i) == deleted_idx.end()) {
			ret += number[i];
		}
	}
 
	return ret;
}

코드2: list 사용

#include <string>
#include <vector>
#include <set>
 
using namespace std;
 
string solution(string number, int k) {
	int head_idx = 0;
	vector<int> next_idx(number.size());
	vector<int> before_idx(number.size());
	string ret = "";
 
	for (int i = 0; i < number.size() - 1; i++) {
		next_idx[i] = i + 1;
		before_idx[i + 1] = i;
	}
 
	next_idx[number.size() - 1] = -1;
	before_idx[0] = -1;
 
	for (int i = 0; i < k; i++) {
		for (int to_delete = head_idx; to_delete != -1; to_delete = next_idx[to_delete]) {
			int next = next_idx[to_delete];
 
			if (next == -1) {
				next_idx[before_idx[to_delete]] = -1;
				next_idx[to_delete] = -1;
				before_idx[to_delete] = -1;
				break;
			} else if (number[to_delete] < number[next]) {
				if (to_delete == head_idx) {
					head_idx = next;
					before_idx[head_idx] = -1;
 
					next_idx[to_delete] = -1;
					before_idx[to_delete] = -1;
					break;
				} else {
					int before = before_idx[to_delete];
 
					next_idx[before] = next;
					before_idx[next] = before;
 
					next_idx[to_delete] = -1;
					before_idx[to_delete] = -1;
					break;
				}
			}
		}
	}
 
	for (int i = head_idx; i != -1; i = next_idx[i]) {
		ret += number[i];
	}
 
	return ret;
}

• 이전에 LeetCode에서 유사한 문제 를 푼 기억이 있었는데, 그때 stack으로 풀었던게 기억이 안났다.
• 그래서 처음에는 누가 지워졌는지 추적하는 set을 사용했다가, 너무 느려서 다음에는 좀 더 빠르게 deletion을 하기 위해 list를 구현해서 사용했다.
• 하지만 문제는 매번 맨 앞에서부터 순회하는 바람에 timeout.