[알고리즘/C#] 프로그래머스 - 인사고과 (Lv.3, 완전탐색?)

0. 실패 코드

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int[,] scores)
    {
        int WanhoScore = scores[0, 0] + scores[0, 1];

        List<int> scoresList = new List<int>();

        for (int i = 0; i < scores.GetLength(0); ++i)
        {
            bool dontContain = false;
            for (int j = 0; j < scores.GetLength(0); ++j)
            {
                if (i == j)     continue;
				
                // 1)
                if (scores[i,0] < scores[j,0] && scores[i,1] < scores[j,1])
                {
                    if (i == 0) return -1;

                    dontContain = true;
                    break;
                }
				
                // 2)
                if (i != 0 && scores[i, 0] + scores[i, 1] <= WanhoScore)
                {
                    dontContain = true;
                    break;
                }
            }

            if (dontContain == false)
                scoresList.Add(scores[i, 0] + scores[i, 1]);
        }

        scoresList.Sort(delegate (int a, int b) { return b.CompareTo(a); });

        for (int i = 0; i < scoresList.Count; ++i)
        {
            if (scoresList[i] <= WanhoScore)
                return i + 1;
        }

        return scoresList.Count + 1;
    }
}

🤦‍♂️ 실패 원인
이중포문으로 구조를 잡을 때 부터 불안했는데 역시나 시간초과가 났다.
for문 내의 경우의 수 조건들을 계속 줄여봤지만 여전히 마지막 두 케이스에서 시간초과가 발생했다.
추가한 제한 조건들은 다음과 같다.
1) 근무태도와 동료 평가점수가 모두 임의의 사원보다 낮은 경우 (문제 조건)
2) 완호보다 점수의 합이 낮거나 같은 경우 (경우의 수를 줄이기 위한 조건
조금 더 줄이면 가능할 것 같았는데 더 이상 방법이 생각나지 않아서 다른 해결방법을 찾기로 했다.

1. 성공 코드

👀 참고

• https://velog.io/@dohui/Lv.3-%EC%9D%B8%EC%82%AC%EA%B3%A0%EA%B3%BC-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-C
• https://school.programmers.co.kr/questions/43274

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int[,] scores)
    {
        int answer = 1;
        int WanhoScore = scores[0, 0] + scores[0, 1];

        List<(int, int)> scoresList = new List<(int, int)>();
        for (int i = 0; i < scores.GetLength(0); ++i)
            scoresList.Add((scores[i, 0], scores[i, 1]));
            
        // 동일 코드 ) scoresList = scoresList.OrderByDescending(x => x.Item1).ThenBy(x => x.Item2).ToList();
        scoresList.Sort(delegate ((int, int) a, (int, int) b)
        {
            if (a.Item1 == b.Item1)
                return a.Item2.CompareTo(b.Item2);
            return b.Item1.CompareTo(a.Item1);
        });

        int maxSecondScore = 0;
        foreach ((int, int) score in scoresList)
        {
            if (scores[0, 0] < score.Item1 && scores[0, 1] < score.Item2)
                return -1;

            if (score.Item2 >= maxSecondScore)
            {
                if (WanhoScore < score.Item1 + score.Item2) answer++;
                maxSecondScore = score.Item2;
            }
        }

        return answer;
    }
}

🎈 풀이 방법
1) 우선, 근무 태도 점수 (Item1) 를 기준으로 내림차순 정렬 한다.
이 순서로 정렬 함으로써 이미 하위 그룹들은 근무태도 점수가 상위 그룹보다 낮다.
따라서, 동료평가 점수라도 상위 그룹보다 같거나 높아야 인센티브를 받을 수 있다.
2) 즉, Item1이 동일할 경우 동료 평가 점수 (Item2) 기준으로 오름차순 정렬 한다.
최상위 그룹의 가장 높은 동료평가 점수보다 같거나 높은 하위 그룹만이 인센티브를 수령할 수 있다.
linq보다는 대리자를 사용하는 편이 더 빠르기 때문에 대리자를 사용했다.

---

😮 사담
c#의 버전이 맞지 않는건지 프로그래머스에서는 sort() 내의 람다 함수가 동작하지 않았다.
vscode에서 정상실행되는 것을 확인했는데 그대로 가져다 썼더니 에러가 났다.
결국 delegate 형태로 명시적으로 선언해서 해결했다.