[프로그래머스] 탐욕법(Greedy) - 큰 수 만들기 (Swift 풀이)

programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기

 

코딩테스트 문제를 풀 때 생각보다 시간초과 에러가 많이 발생한다. 아주 특수한 케이스에 대한 처리를 해주지 않아서 틀리는 경우도 있지만, 어마하게 큰 데이터를 입력받아서 발생하는 시간(메모리) 초과 에러도 아주 잦다. 시간 초과 에러가 발생하면 일단 '조금만 시간을 줄이면 되겠지'라는 생각은 접어야한다. 아예 풀이 방법과 알고리즘을 싹 뜯어 고쳐야한다. 모든 경우를 탐색하는 반복문을 줄이고, 새로운 방법으로 접근을 시도해보자. 이 문제도 시간초과 때문에 생각보다 오래 걸렸던 문제였다. 자료구조와 알고리즘 공부의 필요성을 크게 느꼈다...

 

TMI) 그래서 오늘 Swift 알고리즘 책 구매함 (이미 있는 것 부터 읽어야 하는데..)

---

문제에 대한 기본적인 아이디어

number를 앞에서부터 순차적으로 탐색할 때, 앞에 있는 숫자가 뒤에 있는 숫자보다 작다면 앞에 있는 숫자를 지워줘야 한다.

예를 들어 23xxx 라는 숫자가 있을 때, 2<3 이므로 2를 제거해야 3으로 시작하는 더 큰 수를 만들 수 있다.

 

number는 String형으로, 인덱스를 활용하기 불편하므로 Array형태로 바꿔서 사용하면 편리하다.

var numArr: [Character] = number.map { $0 }

숫자는 k개 제거되어야 하므로 제거된 숫자의 개수를 세는 count 변수를 둔다.

var count: Int = 0

 

---

처음 생각한 방식

반복문을 돌리면서 차례대로 탐색하려고 했다.

 

1. 이 루프는 삭제된 count가 k보다 작을 때 참이 된다.

while count < k { ... }

2. number를 앞에서부터 순차적으로 탐색하며 앞 숫자와 뒷 숫자의 대소를 비교한다.

for i in 0..<numArr.count-1 {
    if numArr[i] < numArr[i+1] { 
        ... 
    }
}

3. 앞숫자 < 뒷숫자 인경우 앞 숫자를 삭제한다. 삭제된 count를 기록한다.

    그리고 다시 최상위 루프의 처음으로 돌아간다. (count<k)

if numArr[i] < numArr[i+1] {
    numArr.remove(at:i)
    count += 1
    break
}

4. number를 끝까지 다 돌면서 한번도 삭제된 숫자가 없다면 내림차순 정렬되어 있다는 뜻이다.

    k-count개만큼 숫자를 더 제거해야 하므로, 남아있는 숫자의 맨 뒤에서부터 k-count 개 제거한다.

if noMore {
    for _ in 0..<k-count {
        numArr.removeLast()
    }
    break
}

 

1차 완성된 코드

func solution(_ number: String, _ k:Int) -> String {
    var numArr: [Character] = number.map { $0 }
    var count: Int = 0
    var noMore: Bool = true
    
    while count < k {
        noMore = true
        for i in 0..<numArr.count-1 {
            if numArr[i] < numArr[i+1] { // 앞 숫자가 뒷 숫자보다 작다면 삭제
                numArr.remove(at:i)
                count += 1
                noMore = false
                break
            }
        }
        
        if noMore {
            for _ in 0..<k-count {
                numArr.removeLast()
            }
            break
        }
    }
    
    let answer = numArr.reduce(""){"\($0)\($1)"}
    return answer
}

 

1차 결과

논리적으로는 정확한 듯 보이나, 역시 몇몇 케이스에서 시간이 상당히 오래 걸리는 것을 발견했다.

2중반복문을 사용하였고, 이미 탐색해서 지나가도 되는 범위까지 탐색하기 때문에 효율이 떨어질 수 밖에 없었다.

---

스택을 사용한 방식

앞 숫자와 뒷 숫자의 대소를 비교할 때, 삭제 후에 반복문으로 전체를 다시 훑을 필요가 없었다.

앞 숫자가 작다면 삭제하고, 그 삭제된 숫자의 하나 더 앞 숫자와 비교하면 된다.

 

예를 들어 6324xxx라는 숫자가 있다면, 6vs3, 3vs2, 2vs4를 순차적으로 비교한 뒤, 2<4이므로 2를 제거하고 634xxx가 남을 것이다.

그 다음 스텝으로는 다시 6vs3을 확인 할 필요 없이, 제거된 2의 앞 숫자인 3과 4를 먼저 비교하면 되는 것이다.

 

가장 최근에 만난 숫자를 먼저 비교하는 방식인데, 이것은 후입선출 스택을 이용하여 구현할 수 있다.

 

위의 예시를 다시 활용하자면 다음과 같은 흐름을 갖는다.

1. 6324에서 6을 스택에 넣는다. (현재 스택 : 6)
2. 스택의 마지막 숫자인 6과 다음 숫자인 3을 비교한다.
   6이 크므로 그대로 유지하고 3을 스택에 넣는다. (현재 스택 : 6,3)
3. 스택의 마지막 숫자인 3과 다음 숫자인 4를 비교한다.
   3이 작으므로 스택에서 3을 꺼내 제거한다. (현재 스택 : 6)
4. 앞숫자가 제거되었으므로 스택의 마지막 숫자인 6과 현재 숫자 4를 한번 더 비교한다.
   6이 크므로 그대로 유지하고 4를 스택에 넣는다. (현재 스택 : 6,4)
5. ...

2차 완성된 코드

func solution2(_ number: String, _ k:Int) -> String {
    var numArr: [Character] = number.map { $0 }
    var stack: [Character] = []
    var delete: Int = 0
    var i: Int = 0
    
    while delete < k && i < numArr.count {
        // 스택이 비어있으면 
        // 현재 인덱스의 숫자를 넣는다. (i 증가)
        guard let last = stack.last else {
            stack.append(numArr[i])
            i += 1
            continue
        }
        
        // 스택의 마지막 숫자보다 현재 인덱스의 숫자가 크면
        // 스택의 마지막 숫자를 꺼내고 현재 인덱스의 숫자를 넣는다.
        if last < numArr[i] {
            stack.removeLast()
            delete += 1
            continue
        }
        
        // 스택에 현재 인덱스의 숫자를 넣는다.(i 증가)
        stack.append(numArr[i])
        i += 1
    }
    
    // k개의 숫자를 제거 완료한 경우
    // 아직 탐색 못한 숫자들까지 합친다.
    if delete >= k {
        stack.append(contentsOf: numArr[i...])
    }
    
    // 인덱스를 끝까지 탐색했는데도 k개 제거하지 못했을 경우
    // 뒤에서부터 k개는 제거한다
    if i >= numArr.count {
        return stack[0..<numArr.count-k].reduce(""){"\($0)\($1)"}
    }
    
    return stack.reduce(""){"\($0)\($1)"}
}

 

2차 결과

10번 케이스도 통과되었고, 6,7,8 케이스만 봐도 시간이 현저히 줄어든 것을 볼 수 있었다!

---

 

깃허브에서 코드 확인

tngusmiso/MailProgramming