티스토리 뷰
728x90
https://programmers.co.kr/learn/courses/30/lessons/42883?language=swift
level 2 큰 수 만들기 (그리디)
정수로 된 문자열이 주어지고, 자연수 k가 주어지면
정수 문자열에서 k개의 문자를 제거하여 얻을 수 있는 수 중 가장 큰 수를 구하는 문제
문자열에서 문자를 제거하는 것이기 때문에 문자열의 순서는 보존되어야 한다.
접근방법
큰 수를 얻는게 목적인 만큼, 앞자리 수가 커야한다.
스택 하나를 두고, k개의 카드(앞으로 문자를 제거하는 걸 카드라고 표현한다)가 남아있는 한
새로 들어갈 수가 현재 스택의 맨 위의 수보다 커야한다.는 로직이면
가장 큰 수를 얻을 수 있다.
오답노트
이전 코드로 테스트케이스 12번이 통과가 안돼서 반례인 9991, k=2를 넣어봤더니, 99가 결과로 나와야 하는데, 9991이 결과로 나왔다.
n-k개의 문자열을 다 채우면 stack에 푸시되면 안된다는 조건이 없어서 였다.
if문으로 append하는 조건을 추가해줬고, 통과됐다.
소스코드
import Foundation
func solution(_ number:String, _ k:Int) -> String {
var answer = ""
var _k:Int = k
let numbers:[Character] = Array(number)
let n:Int = numbers.count
var stack:[Character] = []
for (i,num) in numbers.enumerated() {
while !stack.isEmpty && _k > 0 &&
stack.last!.wholeNumberValue! < num.wholeNumberValue! {
stack.removeLast()
_k -= 1
}
if stack.count < n-k {
stack.append(num)
}
}
return String(stack)
}
728x90
'알고리즘 문제풀이' 카테고리의 다른 글
[프로그래머스] 소수찾기 (Swift) (0) | 2022.03.05 |
---|---|
[프로그래머스] 멀쩡한 사각형 (Swift) (0) | 2022.03.03 |
[프로그래머스] 행렬 테두리 회전하기 (Swift) (0) | 2022.03.02 |
[프로그래머스] 기능개발 (Swift) (0) | 2022.03.02 |
[프로그래머스] 조이스틱 (C++) (0) | 2022.03.02 |
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 그리디알고리즘
- 브루트포스
- 웹크롤링
- 프로그래머스
- 토마토
- BFS
- 파이썬
- 이분탐색
- 백트래킹
- Swift
- 동적계획법
- 다이나믹프로그래밍
- dfs
- c++
- 트리
- 알고리즘
- 투포인터
- 최대힙
- 자바
- 최소힙
- 게임이론
- dp
- 가장 큰 수 Swift
- 백준
- 스택
- 우선순위큐
- 수학
- 최단경로
- 가장 큰 수 프로그래머스
- 정렬
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
글 보관함