20240305_인사고과(프로그래머스)

오늘의 TIL은 인사고과라는 프로그래머스의 문제에 대한 내용이다.

 

문제 링크

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

프로그래머스

 

문제 설명

근무 태도와 동료 평가 점수가 2차원 배열로 기록된 scores.

만약 어떤 사원이 다른 사원보다 두 점수가 모두 낮으면 인센티브를 받을 수 없음.

그렇지 않은 사원들은 두 점수의 석차에 따라 인센티브가 차등 지급.

동일하면 동석차로 취급하고, 동석차 수 만큼 석차를 건너뛴다.

각 사원의 근무 태도 점수와 동료 평가 점수가 scores로 주어지는 경우, 완호의 석차를 return하시오.

 

 

제한 조건

1 <= scores의 길이 <= 100,000

scores의 각 행은 한 사람의 근무 태도 점수와 동료 평가 점수를 나타내며 [a, b]의 형태

0 <= a, b <= 100,000

완호의 점수는 scores[0]

완호가 인센티브를 받지 못하는 경우는 -1을 return

 

 

해결 방안

완호의 석차를 알고 싶은 것이므로, 완호보다 점수의 합이 큰 경우의 데이터만 수집.

또, 완호보다 점수의 합이 높더라도 각각의 점수가 다른 사원보다 낮은 사원이 있을 수 있으므로 이를 제외.

 

 

통과한 답안

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

public class Solution {
    public int solution(int[,] scores) {
        int answer = 0;
        
        var scoresData = new List<Tuple<int, int, int>>();
        int wanhoScore1 = scores[0, 0];
        int wanhoScore2 = scores[0, 1];
        int wanhoTotal = wanhoScore1 + wanhoScore2;

        for (int i = 1; i < scores.GetLength(0); i++)
        {
            int score1 = scores[i, 0];
            int score2 = scores[i, 1];
            int total = score1 + score2;

            if (total > wanhoTotal)
            {
                scoresData.Add(new Tuple<int, int, int>(score1, score2, total));
            }
        }
        
        var newScoresData = new List<Tuple<int, int, int>>();
        
        foreach (var sd in scoresData)
        {
            bool isEligible = true;
            foreach (var other in scoresData)
            {
                if (other.Item1 > sd.Item1 && other.Item2 > sd.Item2)
                {
                    isEligible = false;
                    break;
                }
            }
            if (isEligible)
            {
                newScoresData.Add(sd);
            }
        }

        bool isIncentive = true;
        foreach (var sd in newScoresData)
        {
            if (wanhoScore1 < sd.Item1 && wanhoScore2 < sd.Item2)
            {
                isIncentive = false;
                break;
            }
        }
        answer = isIncentive ? newScoresData.Count + 1 : -1;
        
        return answer;        
    }
}

 

 

완호의 점수 등록 및 완호보다 점수 합이 큰 데이터 저장

int wanhoScore1 = scores[0, 0];
int wanhoScore2 = scores[0, 1];
int wanhoTotal = wanhoScore1 + wanhoScore2;
var scoresData = new List<Tuple<int, int, int>>();

for (int i = 1; i < scores.GetLength(0); i++)
{
    int score1 = scores[i, 0];
    int score2 = scores[i, 1];
    int total = score1 + score2;

    if (total > wanhoTotal)
    {
        scoresData.Add(new Tuple<int, int, int>(score1, score2, total));
    }
}

 

완호의 점수(wanhoScore1, wanhoScore2, wanhoTotal)를 구하고

다른 사원들의 점수 데이터를 저장할 리스트(scoresData)를 선언한다.

 

그 후에 완호보다 점수의 합이 큰 경우에만 그 데이터를 저장한다.

(여기에서 모든 사원이 아닌 일부 사원의 데이터만 1차적으로 저장)

 

 

주어진 조건을 만족시키는 사원들만 저장하는 새로운 리스트 생성

var newScoresData = new List<Tuple<int, int, int>>();
foreach (var sd in scoresData)
{
    bool isEligible = true;
    foreach (var other in scoresData)
    {
        if (other.Item1 > sd.Item1 && other.Item2 > sd.Item2)
        {
            isEligible = false;
            break;
        }
    }
    if (isEligible)
    {
        newScoresData.Add(sd);
    }
}

 

주어진 조건(다른 사원보다 두 점수가 각각 낮은 사원은 제외한다)에 맞는 사원들만을

저장하기 위한 새로운 리스트(newScoresData)를 새로이 선언한다.

 

위에서 1차적으로 선별한 scoresData에서 자격이 있는 사원들만 선별하는데

다른 사원보다 두 점수가 각각 모두 낮은 경우, 인센티브를 받을 수 없으므로 2차적으로 선별하는 요인으로 제외하고

인센티브를 받을 수 있는 사원들만 newScoresData에 추가한다.

 

즉, 1차 선별로 완호보다 점수가 낮은 사원들은 제외했으며,

2차 선별로 인센티브를 받을 수 없는 조건의 사원들은 제외했다.

 

 

완호의 석차 구하기

bool isIncentive = true;
foreach (var sd in newScoresData)
{
    if (wanhoScore1 < sd.Item1 && wanhoScore2 < sd.Item2)
    {
        isIncentive = false;
        break;
    }
}
answer = isIncentive ? newScoresData.Count + 1 : -1;

 

2차 선별로 만든 newScoresData의 담겨있는 각각 사원들에 대하여 완호의 석차를 구하는 과정을 거친다.

위의 2차 선별과 같은 방식으로 완호가 인센티브를 받을 자격이 있다면

완호의 석차는 newScoresData의 길이 + 1(자기 자신은 제외한 리스트이므로)이 되고

받을 자격이 없다면 -1을 return하게 된다.

 

 

오늘은 간단한 방식을 알고리즘 문제라고 생각했던 인사고과에 대한 내용을 정리했는데,

 

초기 접근 방식은 문제를 잘못 이해하여 주어진 조건(한 사원의 각각의 점수가 다른 사원보다 각각 낮은 경우 인센티브를 받을 수 없다)을 적용하지 않아 계속하여 오답이 되었다.

 

이 경험을 통해서 문제를 좀 더 꼼꼼히 읽고 해석하는 능력을 길러야겠다고 느꼈다.

(미뤄두었던 독서도 과정이 끝나면 다시 시작해서 1일1권의 템포로 돌아갈 예정이다)

 

또, 문제를 풀이하는 과정에서 주어진 조건에 따라서 각각의 사원을 비교하는데

이 과정에서 사원이 최대 100,000이므로 N^2의 결과로 인하여 시간 초과가 일어나는 경우가 있었다.

 

이를 해결하기 위해서 필요없는 데이터들(완호보다 점수합이 낮은 사원들, 주어진 조건을 만족하지 못하는 사원들)을

제외하는 과정을 추가했으며 이를 통해서 처리 속도의 향상을 달성했다.

 

어렵지 않게 풀 것이라 생각했던 문제를 오랜 시간을 들여서 풀이했는데,

이 과정에서 놓쳤던 정보들의 문제점과 최적화를 이룰 수 있는 요소들을 배울 수 있었다.