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

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

 

✅ 이 문제는 정말 오랜기간 도전을 하여 풀어냈다.

(첫 도전) 2021/08/08

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

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

 

알고리즘 공부하다가 귀찮아서 계속 미뤘고, 자꾸 미루다가 결국 해야할 것 같아서 풀어냄!

 

이거 머릿속으로는 이해가 되는데, 구현하기가 너무 어려웠다.

 

✅ 첫 도전

 

첫 도전에서의 코드

아래 사진을 보면 알겠지만 시간 초과로 fail

//
//  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))

아 알고리즘은 맞는거 같은데 시.간.초.과

또 안된다 ^__^

 

 

음... 세번째 다른 방법도 알아보도록 하자.

 

✅ 세번째 도전

 

성공 !_!

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

몇몇 코드의 특이점이 있었는데, 꼭 확인해보도록 하자.

//
//  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))
    }
}

 

알 고 리 즘 성 장 완 료