🔒 문제
💭 생각의 흐름
알고리즘
"앞 숫자가 뒷 숫자 보다 크면 지운다" (하나만 지우는게 아니라, 대상이 되는 뒷 숫자앞의 모든 숫자를 검사하자)
자료구조
특정 index 를 지워줘야겠네. => loop을 돌면서 index 컨트롤하기 상당히 어렵겠다! + loop 안에서 지워야 하니까 크기가 가변적인 자료구조를 선택해야겠다.
👉
MutableList쓰면 되겠는데?!
loop index 컨트롤이 귀찮아서 iterator 를 떠올렸는데 iterator가 더 어려웠다.
골치아픈 next, previous 의 메커니즘 차이때문 에..
🔗java & kotlin iterator next, previous 분석
😂 실수
(1) 모든 숫자가 "99999999999999999"로 동일한 경우 주어진 수 k 만큼 길이가 줄어들지 않는 로직을 짰다.
솔직히 이건 테스트 케이스 실행해보기 전엔 정신팔려서 실전에서도 실수할 듯 -_-
(2) Mutable List 선택이 틀린건 아닌데 최대 길이가 100만이라 속도 최적화 필요.
우리를 구원해줄 StringBuffer가 있었다. 아무래도 mutableList를 생성하면 원소 삭제시 원소간 포인터 연결 관계를 조정하느라 별도의 연산이 필요할 수 밖에 없다.
(3) 가변적으로 지우는게 귀찮아서 지울 대상이 될 숫자를 '0' 이나 '-1'로 대치하고자 했는데
이는 앞 숫자 검사 범위를 늘리는 꼴이다.
❌ 실패한 풀이 1 (Iterator 삽질)
// 지울 대상 : 앞자리수가 바로 뒷자리보다 작은 경우
// 1. 지울 대상인 애들을 모두 0으로 값을 대치한다.
// 2. for loop 이나 iterator 정방향 순회시 이전놈을 지워야하고 지울 때 마다 O(N) 이 소요되므로
// removeAll(0)을 쓴다.
// 3. mutable 리스트를 다시 string 으로 되돌린다.
class Solution {
fun solution(number: String, k: Int): String {
val charArray = number.toMutableList()
var count : Int = 0
val itr = charArray.listIterator()
while (itr.hasNext() && count <= k) {
var prev = itr.next()
if (itr.hasNext()) {
if (prev < itr.next()) {
itr.previous()
itr.previous()
itr.remove()
count++
while (itr.hasPrevious() && count <= k) {
var newPrev = itr.previous()
if (newPrev < itr.next()) {
itr.previous()
itr.previous()
itr.remove()
count++
}
}
} else {
itr.previous()
}
}
}
return charArray.toString()
}
}
fun main() {
Solution().solution("4177252841", 4).also { println(it) }
}❌ 실패한 풀이 2 (Mutable List)
// 지울 대상 : 앞자리수가 바로 뒷자리보다 작은 경우 => 여기서 틀림, 앞자리말고 더앞자리중 작은애들부터 지워야됨 (count 모자랄 수 있음)
class Solution {
fun solution(number: String, k: Int): String {
val charArray = number.toMutableList()
var count : Int = 0
var index : Int = 1
while (index < charArray.size && count <= k) {
val targetValue = charArray[index]
while ((index - 1) >= 0 && charArray[index - 1] < targetValue && count <= k) {
charArray.removeAt(index - 1)
count++
index--
}
index++ //
}
return String(charArray.toCharArray())
}
}
fun main() {
Solution().solution("4177252841", 4).also { println(it) }
}🔑 정답 풀이 (Kotlin)
// 지울 대상 : 앞자리수가 바로 뒷자리보다 작은 경우
// 1. 뒷자리를 대상으로 잡고 뒷자리보다 작은 모든 앞자리를 역방향으로 검사하며 지운다.
// 2. 지울 때 mutable list 의 크기와 index가 자동으로 조정되므로 index 컨트롤이 필요하다.
// 3. count 갯수가 3->4로 넘어가는 시점이 마지막 loop 이 된다.
class Solution {
fun solution(number: String, k: Int): String {
val charArray = StringBuffer(number)
var count : Int = 0
var index : Int = 0
while (++index < charArray.length && count < k) {
val targetValue = charArray[index]
while ((index - 1) >= 0 && charArray[index - 1] < targetValue && count < k) {
charArray.deleteCharAt(index - 1)
count++
index--
}
}
// 주어진 횟수만큼 다 지우지 못한경우 같은 숫자가 반복된 케이스
if (charArray.length > number.length - k) {
var count = charArray.length - (number.length - k)
for (index in 0 until count) {
charArray.deleteCharAt(charArray.length - 1)
}
}
return charArray.toString()
}
}
🆙 정답 풀이 개선 (Kotlin)
StringBuffer -> StringBuilder
StringBuffer는 동기화하고 StringBuilder는 동기화 하지 않는다. 나머지는 모두 같다.
∴ 싱글 스레드 프로그래밍시 동기화가 필요하지 않기 때문에 StringBuilder 를 사용하는 것이 더 빠르다.
class Solution {
fun solution(number: String, k: Int): String {
val charArray = StringBuilder(number)
var count : Int = 0
var index : Int = 0
while (++index < charArray.length && count < k) {
val targetValue = charArray[index]
while ((index - 1) >= 0 && charArray[index - 1] < targetValue && count < k) {
charArray.deleteCharAt(index - 1)
count++
index--
}
}
// 주어진 횟수만큼 다 지우지 못한경우 같은 숫자가 반복된 케이스
if (charArray.length > number.length - k) charArray.setLength(number.length - k)
return charArray.toString()
}
}
🆙 정답 풀이 개선 2 (Kotlin)
앞 숫자가 뒷 숫자보다 작을 때만 지운다라는 그리디 기준에서 앞 숫자 모두를 stack에 담고
기준 숫자가 stack의 top이 된다는 점을 이용한 풀이이다.
index control 로 부터 자유롭다는 장점이 있다.
class Solution2 {
fun solution(number: String, k: Int): String {
var count : Int = 0
val stack : Stack<Char> = Stack()
val numberArray = CharArray(number.length - k)
number.forEach {
while (stack.isNotEmpty() && stack.peek() < it && count < k) {
stack.pop()
count++
}
stack.push(it)
}
for (i in count until k) stack.pop()
stack.forEachIndexed { index, c -> numberArray[index] = c }
return String(numberArray)
}
}
🆙 정답 풀이 개선 2 (C++)
#include <string>
#include <stack>
using namespace std;
string solution(string numbers, int k) {
std::stack<char> stack;
int count = 0;
const unsigned int answerLength = numbers.length() - k;
char numCharacters[answerLength];
// C & C++ character array ends with null character
numCharacters[answerLength] = '\0';
for (const auto& number : numbers) {
while (!stack.empty() && stack.top() < number && count < k) {
stack.pop();
count++;
}
stack.emplace(number);
}
// k개 만큼 지워지지 않은 경우 그 차이만큼 빼줌
while (stack.size() > answerLength) stack.pop();
//copy all elements of stack to character array
for (int index = answerLength - 1; !stack.empty(); index--) {
numCharacters[index] = stack.top();
stack.pop();
}
return string(numCharacters);
}
🔗 Reference
I'm still hungry