오늘 배운 내용
프로그래머스 - 귤 고르기
이 문제는 귤의 크기를 index로, 귤의 갯수를 Value로 가지는 배열을 이용해서 해결할 수 있었다.
그런데 문제 조건에서 귤의 최대 크기가 1000만 이 되어서 테스트 케이스중 시간이 2000ms가 걸리는게 있었다.
그런데 귤의 갯수는 10만개 밖에 안됬기 때문에 귤의 크기마다 모두 배열을 만드는게 아니라 존재하는 귤의 크기만
따로 만들어주면 시간을 많이 단축할 수 있을꺼라고 생각했다.
using System;
public class Solution {
// 귤을 크기별로 분류하고
// 한 상자에 귤의 종류가 최소가 되도록 담는다
// 배열에 index == 귤의크기 value == 갯수로 배열을 만든다.
// 배열을 정렬해서 종류가 많은 귤부터 상자에 담는다.
public int solution(int k, int[] tangerine)
{
int[] classify = new int[10000001];
int answer =0;
foreach(int i in tangerine)
{
classify[i]++;
}
Array.Sort(classify);
Array.Reverse(classify);
foreach(int i in classify)
{
k -= i;
answer++;
if(k <= 0)
{
break;
}
}
return answer;
}
}
그래서 존재하는 귤만 Dictionary를 사용해서 갯수를 추가해주기로 했다.
그리고 Dictionary는 순서가 없기 때문에 내림차순으로 정렬하기 위해서 System.Linq의 ToList()를 이용해서 리스트로 만든다음 정렬해 주었다.
그리고 내림차순 정렬을 위해서 (x,y) => y.Value.CompareTo(x.Value) 를 y를 기준으로 정렬했다.
이렇게 바꾸고 나니까 최대 40ms대에 모든 테스트 케이스를 통과하도록 개선할 수 있었다.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
// 귤을 크기별로 분류하고
// 한 상자에 귤의 종류가 최소가 되도록 담는다
// 배열에 index == 귤의크기 value == 갯수로 배열을 만든다.
// 배열을 정렬해서 종류가 많은 귤부터 상자에 담는다.
// 배열로 만들면 실행시간이 너무 오래걸린다. -> 배열의 최대 길이가 10,000,000 되기 떄문
// 테스트는 통과하지만 대충 2000ms까지 걸림
// 딕셔너리를 정렬하기 위해서 List로 만든다. -> 딕셔너리에는 순서가 없어서
// 테스트 최대 40ms대
public int solution(int k, int[] tangerine)
{
int max = tangerine.Max();
Dictionary<int,int> classify = new Dictionary<int,int>();
int answer =0;
foreach(int i in tangerine)
{
if(classify.ContainsKey(i))
{
classify[i]++;
}
else
{
classify.Add(i,1);
}
}
List<KeyValuePair<int,int>> classifyList = classify.ToList();
classifyList.Sort((x,y) => y.Value.CompareTo(x.Value));
// (x,y)에서 x.CompareTo(y) 는 오름차순 y.CompareTo(x)는 내림차순이다.
for (int i = 0; i< classifyList.Count; i++)
{
k -= classifyList[i].Value;
answer++;
if(k <=0)
{
break;
}
}
return answer;
}
}
알고리즘 문제를 풀때는 난이도가 올라갈수록 시간 제한이 빡빡해지기 때문에
최대한 연산할 갯수를 줄여서 연산을 시작하는것이 도움이 될 것 같다.
