반응형
안녕하세요. 개발 중인 정주입니다.
오늘은 프로그래머스 - 실패율 문제를 풀었습니다.
Github
문제 링크
https://programmers.co.kr/learn/courses/30/lessons/42889
풀이
실패율 문제는 카카오 문제인 만큼 테스트 케이스가 꽤 까다로웠습니다. (물론 왕초보인 제 기준에요.)
그래도 최종 버전까지 다른 사람의 코드를 보지 않고 스스로 개선했다는 점에서 뿌듯했네요.
첫 번째 통과
2중 반복문으로 O(n^2)을 사용하니 몇 가지 테스트 케이스에서 시간 초과가 났습니다.
그 다음 개선 방안으로는 반복문 도중 break를 줘서 실행 속도를 줄였습니다.
통과는 했지만 찜찜하여 추가 수정을 했습니다.
최종 개선
counts Array를 선언해서 stage를 index로 사용합니다.
각 stage에 머무는 count를 세는 것입니다.
위에서 내부 for문이 이 count를 세는 작업이었는데요. 이 방법을 이용해서 중첩 반복을 피할 수 있었습니다.
1 ~ N까지 위에서 구한 count와 score를 구해서 scores Tuple Array에 넣습니다.
마지막 return하는 곳에서는 score로 정렬해서 index 값을 return하면 됩니다.
전체 코드
import Foundation
func solution(_ N:Int, _ stages:[Int]) -> [Int] {
var scores: [(Int, Double)] = []
var stageCount = stages.count
var counts = Array(repeating: 0, count: N+1)
for stage in stages {
counts[stage-1] += 1
}
(1...N).forEach { i in
let count = counts[i-1]
let score = Double(count) / Double(stageCount)
scores.append((i, score))
stageCount -= count
}
return scores.sorted { $0.1 > $1.1 }.map { $0.0 }
}
let N = 5
let stages = [2, 1, 2, 6, 2, 4, 3, 3]
print(solution(N, stages))
아직은 초보 개발자입니다.
더 효율적인 코드 훈수 환영합니다!
공감과 댓글 부탁드립니다.
반응형