[Swift] 프로그래머스 LV2. 큰 수 만들기

프로그래머스 LV2. 큰 수 만들기

 

접근 방식

 

앞자리에 큰 숫자를 남길수록 전체 수가 커짐. 그래서 왼쪽부터 훑으면서 이미 쌓아둔 수보다 뒤에 더 큰 수가 나오면 앞의 작은 수를 버리는 방식으로 접근함. 버릴 수 있는 횟수는 k번으로 제한됨.

 

논리는 금방 잡혔는데 구현에서 계속 막혀서 세 번에 걸쳐 풀어냄.

 

(첫 도전) 2021/08/08

 

(두번째 도전) 2021/11/18

 

(세번째 도전) 2022/04/13

 

시행착오

 

첫 도전

 

첫 도전에서의 코드.

 

아래 사진을 보면 알 수 있듯 시간 초과로 실패함.

 

//
//  main.swift
//  algorithm
//
//  Created by Hamlit Jason on 2021/08/08.
//

/* 큰 수 만들기
 https://programmers.co.kr/learn/courses/30/lessons/42883
 실패
 */

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    
    var arr = Array(number)
    //print(arr)
    //var startIndex = 0
    var k = k
    //print("start k is \(k)")
    var collect = [Character]()
    
    collect.append(arr[0])
    arr.removeFirst()
    for i in 0..<number.count {
        var prev = collect[collect.endIndex - 1].wholeNumberValue!
        let next = arr[0].wholeNumberValue! // Int타입
        //print("\(i) -> prev: \(prev) next : \(next)")
        
        while true {
            //print("\(i) -> collect \(collect)")
            //print("\(i) -> arr \(arr)")
            if prev < next {
                collect.removeLast() // 마지막꺼 빼고
                k -= 1 // k 값 감소 카운팅
                //print("k in -> \(k) ")
                
                if k <= 0 {
                  //  print("out")
                    collect += arr
                    let answer = collect.reduce(""){"\($0)\($1)"}
                    return answer
                }
                
                if collect.count == 0 { // 뺐는데 컬렉터 값이 0이면
                    collect.append(arr[0])
                    arr.removeFirst()
                    break
                } else {
                    prev = collect[collect.endIndex-1].wholeNumberValue!
                }
            } else {
                //print(arr)
                if arr.isEmpty {
                    //collect += arr
                    let answer = collect.reduce(""){"\($0)\($1)"}
                    return answer
                }
                collect.append(arr[0])
                arr.removeFirst()
                break
            }
            
        }
        
//        print("collet : \(i) -> \(collect)")
//        print("arr : \(i) -> \(arr)")
    }
    
    return ""
}

print(solution("4177252841", 4))

 

 

2차 도전

 

//
//  main.swift
//  algorithm
//
//  Created by Hamlit Jason on 2021/11/18.
//https://programmers.co.kr/learn/courses/30/lessons/42883

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    
    // 걍 나보다 앞에 있는 수중에 작은거 다 없애면 되겠네
    var queue = [Character]() // Int type
    var arr = number.map{$0} // String type
    var count = k
//    print(type(of: arr))
//    print(arr[0])
    
    if k == 0 {
        return number
    } else if arr.count - 1 == k {
        return "\(arr.max()!)"
    }
    
    while true {

        print("while head \(count)")
        if arr.count == 1 {
            print("arr count 1")
            break
        }
        
     
        if arr[0] < arr[1] { // 내 뒤의 숫자가 더 크면
            print("\(arr[0]) \(arr[1])")
            arr.removeFirst()
            count -= 1
            if count == 0 {
                break
            }
            if !queue.isEmpty { // 큐가 비어있지 않다면
                // 큐의 마지막으로 들어간 숫자와 현재 숫자 비교
                
                while true {
                    
                    if queue.isEmpty {
                        break
                    }
                    print("queue \(queue)")
                    
                    if arr[0] < queue.last! { // 큐의 마지막 값이 크거나 같다면?
                        break
                    } else {
                        queue.removeLast()
                        count -= 1
                    }
                    
                    if count == 0 {
                        break
                    }
                }
            }
        } else {
            print("\(arr[0]) \(arr[1])")
            queue.append(arr[0])
            arr.removeFirst()
        }

        if count == 0 {
            break
        }
    }
    
    
    
    print("count\(count)")
    print("\(queue) \(arr)")
    var str1 = queue.reduce("") { s, ss in
        return "\(s)\(ss)"
    }
    var str2 = arr.reduce("") { s, ss in
        return "\(s)\(ss)"
    }
    
    var str3 = "\(str1)\(str2)"

    for _ in 0..<count {
//        print("count is \(count)")
        if let index = str3.firstIndex(of: str3.min()!) {
//            print("remove?")
            str3.remove(at: index)
        }
    }
    
//    print(str2)
    
    return "\(str3)"
}

//print(solution("4177252841", 4))
//print(solution("1924", 2))
//print(solution("1231234", 4))
//print(solution("99991", 3))
//print(solution("999", 1))

var a = [Character]()

for i in 0..<1000000 {
    a.append("9")
}

print(a)

//print(solution("111119", 3))

 

 

이번에도 실패함.

 

세 번째로 다른 방법을 알아보기로 함.

 

코드

 

세 번째 도전에서 성공함.

 

다른 분의 코드를 참고하긴 했으나 주석으로 정리하면서 이해했음.

 

핵심은 단조 스택임. 왼쪽부터 한 글자씩 넣되, 아직 지울 여유(count < k)가 있고 스택 맨 위 숫자가 새 숫자보다 작으면 pop해서 더 큰 수를 앞으로 당김. k를 다 쓰면 남은 글자를 그대로 붙이고, 마지막에 prefix(number.count - k)로 필요한 자릿수만 남김. 앞의 두 도전은 배열을 removeFirst로 앞에서 지우고 매번 문자열을 다시 이어 붙여 시간 초과가 났는데, 스택은 뒤에서만 넣고 빼서 그 비용이 사라짐.

 

//
//  42883.swift
//  Algorithm
//
//  Created by Hamlit Jason on 2022/04/13.
//
//https://programmers.co.kr/learn/courses/30/lessons/42883
import Foundation

struct p42883 {
    static func run() {
//        print(p42883.solution("4177252841", 4)) // 94
        print(p42883.solution("119119", 5)) // 9
    }
    
    static func solution(_ number:String, _ k:Int) -> String {
        
        let map = number.map { "\($0)" }
        var stack = [String]()
        var count = 0
        
        for i in 0..<number.count {
            // 아직 덜 지웠거고, 스택에 값이 들어있으면서, 스택의 마지막 값이 비교하는 수보다 작다면
            while count < k && !stack.isEmpty && stack.last! < map[i] {
                stack.removeLast() // 스택값 지우고
                count += 1 // 지웠다는 의미에서 + 1
            }
            
            if count >= k { // k만큼 지웠다면
                stack.append(contentsOf: map[i...]) // 스택에 수행하지 못하고 남은 값들 다 넣어줌
                break
            } else {
                stack.append(map[i]) // 스택에서 지울 수는 없는데, 지울게 남았다면 스택에 넣기
            }
        }
        
        // prefix를 하는 이유는 스택의 앞부분부터 우리가 원하는 출력 갯수를 맞춰주기 위함이다.
        // 예를 들면, "119119" 의 경우에는 99가 출력되기 때문에 이걸 예방하기 위함이다.
        print(stack.joined())
        return String(stack.joined().prefix(number.count-k))
    }
}