[코딩 테스트] 가장 많이 받은 선물

 

코딩 테스트 학습을 시작하게 된 계기

많은 공채나, 채용과정을 보다 보면 항상 빠짐없이 나오는 항목이 코딩 테스트항목을 볼 수있습니다. 하지만, 저는 코딩 테스트에 대해서 고민해 본 적도 없고, 시간을 내서 학습해 본 적이 없었습니다. 스터디를 시작하고 스터디원들과 잠깐 시간을 내어 학습하였을 때는 알고리즘이나, 언어에 대한 이해도를 점검할 수 있지만, 해당 문제의 문제 인식, 문제 해결방식에 대한 생각의 흐름도 점검이 가능하다고 생각하여 이제부터 주 단위로 조금씩 풀어보고자 합니다. 프로그래머스 문제의 레벨 1단계를 시작으로 4~5레벨을 넘어 많은 문제를 푸는 저만의 스토리를 작성해보겠습니다. 

 

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

프로그래머스

첫 번째 문제로 해당 링크의 문제로 시작해보려고 합니다.

가장 많이 받은 선물 : 출처 "프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges”

 

조건

1. 선물을 주고 받은 기록이 있다면, 더 많은 선물을 준 사람은 다음달에 선물을 하나 받습니다.

2. 선물을 주고 받은 기록이 없거나, 횟수가 같다면, 선물 지수가 더 큰 사람이 더 작은 사람에게 선물을 하나 받습니다.

2-1. 이 때 선물 지수가 같다면? 다음 달에 선물을 주고 받지 않습니다.

 

선물지수란?

이번 달까지 자신이 친구들에게 준 선물의 수에서 받은 선물의 수를 뺀 값입니다.

 

이 때 1차원 문자열 friends와 이번달까지 친구들이 주고받은 선물 기록을 담은 1차원 문자열 배열 gifts의 매개변수로 주어질 때 다음달에 가장 많은 선물을 받는 친구가 받을 선물의 수를 return하도록 solution 함수를 완성하시오.

 

풀이 과정

---

문제를 읽고 이해하면서, 중요하게 생각하였던 부분은 어떤 자료 구조를 활용하고, 문제에서 제시하는 조건식을 얼마나 잘 적용하는 가에 대한 고민을 정말 많이하였습니다. 
문제를 읽으며, 각 조건들에 대해서 도출하였고, 자료구조의 활용은 조건식을 사용하기위해 적합한 방향으로 결정하였습니다. 

 

• 자료 구조 : Dictionary, 2차원 배열

선택 이유

문제에서 제시한 친구들의 이름을 통해, 각 친구별 친구들간의 선물을 주고 받은 개수를 적용해야 되기 때문에 2차원 배열을 활용하고자 하였고, 이 때 각 배열의 인덱스를 접근하기위해서, 친구들의 이름을 Key, Value 형태인 Dictionary 자료 구조를 채택.
문제의 조건에서 각 친구들 간의 이름은 중복되지 않음.

 

친구들의 이름 인덱스 화하기

배열로 들어온 친구들의 이름을 이차원 배열에 그대로 활용하기위해서, Dictionary를 활용하여 Index로 치환 가능하게 설정

 

Dictionary<string, int> friend = new Dictionary<string, int>();
int friendCount = friends.Length;
for (int index = 0 ; index < friendCount ; index++)
{
	friend.Add(friends[index], index);
}

 

친구들간의 이번달 선물을 주고받은 내역을 이차원 배열로 정리.

친구 본인 스스로 선물을 본인에게 줄수없으니, 이차원 배열 안에서 Row, Colume이 동일한 Index는 무시하고, 아래 코드를 적용하면  아래의 표로 각 친구들 끼리의 선물의 개수가 합산됩니다.

int[,] sum = new int[friendCount ,friendCount ];
for(int index = 0; index< gifts.Length; index++)
{
	string[] gift = gifts[index].Split(' ');
	friend.TryGetValue(gift[0], out int send);
	friend.TryGetValue(gift[1], out int receive);
	sum[send ,receive]++;
}

↓준 사람 \ 받은 사람→	hyunwoo	Cheese	Cream	Madeleine
hyunwoo	x	3	2	5
Cheese	5	x	3	4
Cream	2	3	x	5
Madeleine	4	4	3	x

 

친구 각자의 선물 지수 계산하기

친구별 선물을 받은 개수와, 선물을 준 개수를 계산하여 친구별 선물 지수를 계산을 진행합니다. 이 때 Row(행)에 해당하는 친구는 선물을 준 사람으로 선물지수를 더해주고, Column(열)에 해당하는 친구는 선물을 받은 친구로 선물 지수에 빼줍니다. 소스에 반영하면 아래와 같습니다.

for (int index = 0; index < friendCount; index++)
{
	for(int indexJ= 0; indexJ <friendCount; indexJ++)
	{
		if (index == indexJ)
			continue;
		sendWeight[index] += sum[index, indexJ];
		sendWeight[indexJ] -= sum[index, indexJ];
	}
}

 

여기 까지 진행하면, 문제에서 나오는 이번달의 친구들끼리의 선물을 주고받은 정보에 대한 가공및 정렬이 완료 됩니다.
이제 이번달의 친구들의 선물 지수와, 각 친구들간의 선물을 주고받은 데이터를 토대로 조건식을 작성합니다. 

 

각 조건식을 적용

for (int index = 0; index < friendCount; index++)
{
	for(int indexJ= 0; indexJ <friendCount; indexJ++)
    {
    	if (index ==indexJ )
        	continue;
        // 주고받은 선물이 같거나, 없을 때 선물 지수 비교(조건식2)
		if (sum[index, indexJ] == sum[indexJ, index])
		{
         	if (sendWeight[index] > sendWeight[indexJ])
            {
            	result[index]++;
			}
		}
        // 친구 A가 친구 B에게 준 선물이더 많을 때 친구 A가 받을 선물 1증가 (조건식1)
		else if ( sum[index, indexJ] > sum[indexJ, index])
        {
        	result[index]++;
		}
	}
}

 

위 문제 분석 및 데이터 정리 조건식 대입을 통해 문제를 풀어보았고, 추가적인 시간 복잡도에 대한 검토를 진행해 보았습니다. 시간 복잡도는 소스에서 볼 수있듯이,  O(2 x N² + K)로 확인이 가능했고, 여기서 시간 복잡도를 구하면, O(N²)로 계산하였고, 이를 GPT를 통해 검증하였습니다. 

 

첫 번째 문제를 마치며..

문제를 풀면서 어떤 자료구조를 활용해야 하는지, 더 좋은 방법은 없는지? 문제를 정확하게 이해하였는지를 고민하는 시간이 정말 많이 들었고, 이러한 생각들과 아이디어를 통해 코딩을하여 결과를 뽑아내는데는 오랜 시간이 걸리지 않았습니다.
문제를 다풀고 해당 알고리즘의 시간복잡도에 대해서도 혼자 생각해보고 하면서, 프로그래밍에 있어서 설계(아키텍쳐, 자료구조)등에 대한 고민이 선행되어야 실제 문제해결을 위한 소스에서 알맞은 문제 해결 흐름이 나오게 되는 것이라고 생각하는 계기가 되었습니다.