[그리디] 큰 수 만들기 - 프로그래머스 Swift

문제 : https://programmers.co.kr/learn/courses/30/lessons/42883?language=swift 

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

 

첫번째 풀이방법 : 해쉬테이블

 

풀이방법

1. number를 for문 전체 한번 돌아서 dictionary로 바꾼다 [숫자: 그숫자가 있는 갯수]
2. 가장 작은 숫자부터 골라서 앞에서 부터 k번될 때까지 없앤다.

오류 : 1231231, k = 3 이면 3231 인데 가장작은 숫자(1)부터 없애서 2323이 되버린다.

 

코드

func solution2(_ number:String, _ k:Int) -> String {
    var map = number.map{String($0)}
    var dic: [String:Int] = ["1":0,"2":0,
                   "3":0,"4":0,
                   "5":0,"6":0,
                   "7":0,"8":0,
                   "9":0]
    var out = [String]()
    
    for element in number {
        dic[String(element)]! += 1
    }
    
    a: for filledNumber in 1...9 {
        if dic["\(filledNumber)"]! != 0 {
            
            var results = dic["\(filledNumber)"]!
            for one in 0..<results {
                dic["\(filledNumber)"]! -= 1

                out.append(String(filledNumber))
                
                if out.count == k {
                    break a
                }
            }
        }
    }
    
    var result = ""
    print(out)
    b: for one in map {
        c: for outOne in out {
           
            if one == outOne {
            
                if let firstIndex = out.firstIndex(of: one) {
                    out.remove(at: firstIndex)
                }
                continue b
            }
        }
      
        result += one
    }
 
    print(map)
    print(result)
    return result
}

let number = "1231234"
let k = 3
solution2(number, k)

 

 

2번째 풀이방법 : 그리디

 

풀이방법

1. 맨 높은자릿수에서부터 그 뒷자리의 수랑 크기 비교를한다
2. 뒷자리의 수가 더 크면 그 앞에있던 숫자를 빼버린다.
3. 숫자를 k번 제거 할 때까지 반복한다.

 

코드

func solution3(_ number:String, _ k:Int) -> String {
    var stack = [String]()
    let arr = number.map{String($0)}
    let blank = k
    var skippedCharCount = 0
	// for문의 끝에 들어가는 카운트로 O(n)에서 계속 연산을 하기 때문에 따로 변수로 지정해주면 시간을 줄일 수 있다고 한다.
    let numberCount = number.count
    
    for i in 0..<numberCount {
        while !stack.isEmpty && stack.last! < arr[i] && skippedCharCount < blank {
            stack.removeLast()
            skippedCharCount += 1
        }
        
        if skippedCharCount == blank {
            stack.append(contentsOf: arr[i...])
            break
        } else {
            stack.append(arr[i])
        }
    }
	//prefix하는 이유: 77777777, k=2일 경우 제거를 안하고 stack에 그대로 쌓이므로 자릿수에 맞게 배출하도록 함
  	return String(stack.joined().prefix(numberCount-blank))
}
print(solution3(number, k))