[코딩테스트] Programmers - 베스트 앨범 (실패)

 

https://school.programmers.co.kr/learn/courses/30/lessons/42579#

프로그래머스

 

 

풀이

해시 문제라서 Dictionary로 풀어봤다. 

 

1. 장르별 딕셔너리(genreDict)를 초기화

    ex) dict["classic"] = { classic 장르 재생 횟수들 저장 }

 

2. 장르별 딕셔너리를 재생횟수가 높은 장르별로 정렬 

 

3. 재생횟수가 높은 장르부터 2개씩 answer 배열에 고유번호를 저장 

 

 

코드1 - 오답

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    public int[] solution(string[] genres, int[] plays) 
    {
        List<int> answer = new List<int>();

        // 장르별 딕셔너리 초기화 
        Dictionary<string, List<int>> genreDict = new Dictionary<string, List<int>>();
        for(int i = 0; i < genres.Length; i++)
        {
            if(!genreDict.ContainsKey(genres[i]))
            {
                genreDict.Add(genres[i], new List<int>());
                genreDict[genres[i]].Add(plays[i]);
            }
            else
            {
                genreDict[genres[i]].Add(plays[i]);
            }
        }
        
        // 재생횟수가 높은 장르별로 정렬 
        genreDict = genreDict.OrderByDescending(genre => genre.Value.Sum()).ToDictionary();
        foreach(string genre in genreDict.Keys)
        {
            genreDict[genre].Sort();
        }
        
        foreach(string genre in genreDict.Keys)
        {
            // 1곡만 있으면 그 곡만 answer에 추가 
            if(genreDict[genre].Count == 1)
            {
                answer.Add(plays.IndexOf(genreDict[genre][0]));
            }
            // 2곡 이상이면 
            else if(genreDict[genre].Count > 1)
            {
                answer.Add(plays.IndexOf(genreDict[genre][0]));
                answer.Add(plays.IndexOf(genreDict[genre][1]));
            }
        }

        return answer.ToArray();
    }
}

 

ToDictionary 메서드는 매개변수로 2개의 인자가 필요한데 채우지 않았고, 배열(plays)에는 IndexOf 메서드는 없는데 사용해서 틀렸다. 

 

 

코드2 - 오답

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    public int[] solution(string[] genres, int[] plays) 
    {
        List<int> answer = new List<int>();

        // 장르별 딕셔너리 초기화 
        Dictionary<string, List<int>> genreDict = new Dictionary<string, List<int>>();
        for(int i = 0; i < genres.Length; i++)
        {
            if(!genreDict.ContainsKey(genres[i]))
            {
                genreDict.Add(genres[i], new List<int>());
                genreDict[genres[i]].Add(plays[i]);
            }
            else
            {
                genreDict[genres[i]].Add(plays[i]);
            }
        }
        
        // 재생횟수가 높은 장르별로 정렬 
        genreDict = genreDict.OrderByDescending(genre => genre.Value.Sum()).ToDictionary(x => x.Key, x => x.Value);
        foreach(string genre in genreDict.Keys)
        {
            genreDict[genre].Sort();
        }
        
        foreach(string genre in genreDict.Keys)
        {
            // 1곡만 있으면 그 곡만 answer에 추가 
            if(genreDict[genre].Count == 1)
            {
                answer.Add(Array.IndexOf(plays, genreDict[genre][0]));
            }
            // 2곡 이상이면 
            else if(genreDict[genre].Count > 1)
            {
                // 만약 장르가 1개이면? 
                if(genreDict.Keys.Count == 1)
                {
                    int count = genreDict[genre].Count % 2 == 0 ? genreDict[genre].Count : genreDict[genre].Count - 1;
                    for(int i = 0; i < count; i++)
                        answer.Add(Array.IndexOf(plays, genreDict[genre][genreDict[genre].Count - i - 1]));
                }
                else
                {
                    answer.Add(Array.IndexOf(plays, genreDict[genre][genreDict[genre].Count - 1]));
                    answer.Add(Array.IndexOf(plays, genreDict[genre][genreDict[genre].Count - 2]));
                }
            }
        }

        return answer.ToArray();
    }
}

 

테스트케이스2, 15에서 실패한다. 

뭐 때문인지 파악이 안 되서 llm에게 물어봤다. 

 

반례

• genres = ["pop", "pop"]
• plays = [2500, 2500]

위와 같이 주어지면 [0, 1]이 반환되야 한다. 그런데 내 코드로는 [0, 0]이 반환된다. 

IndexOf 메서드는 같은 값을 찾을 때는 앞에 있는 값의 인덱스를 가져오기 때문에 0번 인덱스만 반환해서 [0, 0]이 반환되고 있다. 

 

 

코드3 - 정답

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    public int[] solution(string[] genres, int[] plays) 
    {
        List<int> answer = new List<int>();

        // 장르별 딕셔너리 초기화 
        Dictionary<string, List<int>> genreDict = new Dictionary<string, List<int>>();
        for(int i = 0; i < genres.Length; i++)
        {
            if(!genreDict.ContainsKey(genres[i]))
            {
                genreDict.Add(genres[i], new List<int>());
                genreDict[genres[i]].Add(plays[i]);
            }
            else
            {
                genreDict[genres[i]].Add(plays[i]);
            }
        }
        
        // 재생횟수가 높은 장르별로 정렬 
        genreDict = genreDict.OrderByDescending(genre => genre.Value.Sum()).ToDictionary(x => x.Key, x => x.Value);
        foreach(string genre in genreDict.Keys)
        {
            genreDict[genre].Sort();
        }
        
        foreach(string genre in genreDict.Keys)
        {
            // 1곡만 있으면 그 곡만 answer에 추가 
            if(genreDict[genre].Count == 1)
            {
                answer.Add(Array.IndexOf(plays, genreDict[genre][0]));
            }
            // 2곡 이상이면 
            else if(genreDict[genre].Count > 1)
            {
                int index1 = Array.IndexOf(plays, genreDict[genre][genreDict[genre].Count - 1]);
                answer.Add(index1);
                plays[index1] = -1;
                
                int index2 = Array.IndexOf(plays, genreDict[genre][genreDict[genre].Count - 2]);
                answer.Add(index2);
                plays[index2] = -1;
            }
        }

        return answer.ToArray();
    }
}

 

이미 계산 처리가 된 것은 -1로 만들면 해결된다. 

이러면 같은 값을 찾을 수가 없게 된다.