귤 고르기
경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.
예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.
경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
- 1 ≤ tangerine의 원소 ≤ 10,000,000
입출력 예
| 6 | [1, 3, 2, 5, 4, 5, 2, 3] | 3 |
| 4 | [1, 3, 2, 5, 4, 5, 2, 3] | 2 |
| 2 | [1, 1, 1, 1, 2, 2, 2, 3] | 1 |
입출력 예 설명
입출력 예 #1
- 본문에서 설명한 예시입니다.
입출력 예 #2
- 경화는 크기가 2인 귤 2개와 3인 귤 2개 또는 2인 귤 2개와 5인 귤 2개 또는 3인 귤 2개와 5인 귤 2개로 귤을 판매할 수 있습니다. 이때의 크기 종류는 2가지로 이 값이 최소가 됩니다.
입출력 예 #3
- 경화는 크기가 1인 귤 2개를 판매하거나 2인 귤 2개를 판매할 수 있습니다. 이때의 크기 종류는 1가지로, 이 값이 최소가 됩니다.
접근 방법
귤의 수를 정확히 맞출 필요는 없다.
귤의 크기의 범위는 정해져있다.
- 1 ≤ tangerine의 원소 ≤ 10,000,000
이므로 귤의 크기 만큼 배열을 생성해주는데 배열의 최대 크기 는 귤의 크기의 최대치로 설정한다.
(귤 크기별 개수를 알기 위해서이다)
1. 귤의 크기별로 몇 개가 포함되어 있는지 배열에 추가해준다
귤의 크기가 50이라면 numlist[50] 을 +1, 귤의 크기가 132라면 numlist[132]를 해준다.
2. 겹치는 귤의 개수가 많은 순서대로 내림차순 정렬을 해준다.
3. 필요한건 겹치는 귤의 크기 종류의 수.
겹치는 귤의 크기 종류의 수를 구할 때 가장 많은 개수의 귤부터 차례대로 귤의 개수에 더해주면 된다.
귤의 개수에 더하지만 필요한건 크기별 종류의 수 이므로 한 개의 종류를 더해줄 때 마다 answer에 + 1을 해준다.
4. 선택 조건( 조건 설명)
필요 귤 개수. 현재까지 추가한 귤의 수 선택된 귤크기 종류 남은 배열(크기별 귤의 개수)
6 0 0 [4, 3, 2, 1, 0]
해당 조건에서 시작했다고 가정할 경우 첫 번째로 4를 선택했을 때 아래처럼 된다.
필요 귤 개수. 현재까지 추가한 귤의 수 선택된 귤크기 종류 남은 배열(크기별 귤의 개수)
6 4 1 [3, 2, 1, 0]
라고 쳤을 경우 다음 귤의 수는 꼭 2일 필요가 없다
그냥 첫 번째인
3을 선택하면 된다.
귤 개수를 정확하게 맞출 필요가 없다.
우린 3개의 귤을 선택하지만 실제로 포장할 땐 크기가 3인 귤을 2개만 넣으면 되기 때문이다.
달리 말해 귤의 개수가 부족한건 안되지만 귤의 개수가 넘치는건 허용된다는 뜻.
변수 설명
max : 귤의 최대 크기 (불 필요한 공간 낭비를 덜기 위해)
numlist : 귤의 크기 별 귤의 개수를 저장할 배열
answer: 귤 크기 종류의 수
count: 선택된 귤의 수
실패코드
시간초과
for i in numlist{
}
내에서 계속 removeFirst()가 실행되며 배열 내애서의 삭제, 재배치가 모든 반복마다 이루어지면서 시간초과가 발생했다.
func solution(_ k:Int, _ tangerine:[Int]) -> Int {
let max = tangerine.max()!
var numlist = Array(repeating: 0, count: max + 1)
for i in tangerine{
numlist[i] += 1
}
// var count = numlist.reduce(0){ $0 + $1}
numlist.sort(by: >)
// 종류의 수
var answer = 0
//귤의 수
var count = 0
for i in numlist{
if( count < k ){
count += numlist.first!
numlist.removeFirst()
answer += 1
}
}
return answer
}성공코드
func solution(_ k:Int, _ tangerine:[Int]) -> Int {
// 공간 낭비를 줄이기 위해 귤의 최대크기를 배열의 최대크기로
let max = tangerine.max()!
//귤 크기별 개수를 저장할 배열
var numlist = Array(repeating: 0, count: max + 1)
//귤 크기별 개수를 센다
for i in tangerine{
numlist[i] += 1
}
//귤 크기별 개수의 내림차순으로 정렬한다
numlist.sort(by: >)
// 귤 크기 종류의 수
var answer = 0
//선택 된 크기의 귤의 수
var count = 0
//배열 요소는 몇개까지 있나.
let howmany = numlist.count
//0번 인덱스(가장 큰 수)부터 차례대로 접근
for i in 0..<howmany{
//선택된 귤의 수가 목표치보다 적다면
if( count < k ){
//가장 많은 귤부터 추가한다.
count += numlist[i]
//한 종류의 크기를 선택했으니 1증가
answer += 1
}
}
return answer
}지속적인 배열의 Update가 아니라 요소를 순회하며 귤의 수를 추가하는거로 업데이트.