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

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

프로그래머스

오래간만에 코딩테스트 연습을 해봤습니다. ㅎㅎ

 

※주의 : 정답이 잔뜩 적혀있으니 미리 고민 많이 하시고 시청하시는 것을 추천드립니다.

 

저의 풀이와 다른 사람의 풀이를 둘 다 작성해 보겠습니다.

다른 사람의 풀이는 간단하게 작성된 것을 채택하였습니다.

 

또한 저의 풀이는 다소 지저분한 성격이 있으니 주의 부탁드립니다.

 

문제는 각자 읽으셨을 테니 생략하고, 문제 풀이만 하겠습니다.

나의 풀이

import java.util.*;

class CodingT {
	public int solution(String[] friends, String[] gifts) {
		int answer = 0;
		//선물지수, 각 사람에게 몇 개의 선물을 줬는지 저장하는 Map
		Map<String, Map<String, Integer>> giftMap = new HashMap<String, Map<String, Integer>>();
		//다음 달에 받는 선물 개수 저장하는 Map
		Map<String, Integer> nextMonthGiftMap = new HashMap<String, Integer>();

		//giftMap 에 넣을 값 초기화 및 저장 (인원수에 맞게 저장)
		for (int j = 0; j < friends.length; j++) {
			Map<String, Integer> giftCount = new LinkedHashMap<String, Integer>();
			giftCount.put("index", 0);
			nextMonthGiftMap.put(friends[j], 0);

			for (int k = 0; k < friends.length; k++) {
				if (j != k) {
					giftCount.put(friends[k], 0);
				}
			}

			giftMap.put(friends[j], giftCount);

			//선물 주고 받은 내용으로 누가 누구에게 줬는지 giftMap에 저장 하는 반복문
			for (int i = 0; i < gifts.length; i++) {
				String[] separateGifts = gifts[i].split(" ");
				if (separateGifts[0].equals(friends[j])) { //현재 비교하는 내용이 준 사람일 때
					Integer index = giftMap.get(separateGifts[0]).get("index");
					giftMap.get(separateGifts[0]).put("index", index + 1);
					Integer count = giftMap.get(separateGifts[0]).get(separateGifts[1]);
					giftMap.get(separateGifts[0]).put((separateGifts[1]), count + 1);
				} else if (separateGifts[1].equals(friends[j])) { //현재 비교하는 내용이 받은 사람일 때
					Integer index = giftMap.get(separateGifts[1]).get("index");
					giftMap.get(separateGifts[1]).put("index", index - 1);
				}
			}
		}

		//이미 비교한 쌍을 추적하기 위한 Set
		Set<String> comparedPairs = new HashSet<>(); 
		//모든 사용자 간의 선물 교환 횟수 비교
		for (Map.Entry<String, Map<String, Integer>> entry1 : giftMap.entrySet()) {
			String giver1 = entry1.getKey(); // giver1 가져옴
			Map<String, Integer> giftsReceived1 = entry1.getValue(); // 해당 giver1가 받은 선물들을 가져옴

			for (Map.Entry<String, Map<String, Integer>> entry2 : giftMap.entrySet()) {
				String giver2 = entry2.getKey(); // giver2 가져옴

				// 이미 비교한 쌍인지 확인
				if (!giver1.equals(giver2) && !comparedPairs.contains(giver1 + "-" + giver2)) {
					Map<String, Integer> giftsReceived2 = entry2.getValue(); // 해당 giver2가 받은 선물들을 가져옴

					// giver1이 giver2에게 준 선물 개수
					int giver1ToGiver2 = giftsReceived1.getOrDefault(giver2, 0);
					int giver1Idx = giftsReceived1.getOrDefault("index", 0);

					// giver2가 giver1에게 준 선물 개수
					int giver2ToGiver1 = giftsReceived2.getOrDefault(giver1, 0);
					int giver2Idx = giftsReceived2.getOrDefault("index", 0);
					// 비교 결과 출력

					if (giver1ToGiver2 > giver2ToGiver1) { //1번이 2번한테 많이 줬을 때
						Integer nextMonthGift = nextMonthGiftMap.get(giver1);
						nextMonthGiftMap.put(giver1, nextMonthGift + 1);
					} else if (giver1ToGiver2 < giver2ToGiver1) { //2번이 1번한테 많이 줬을 때
						Integer nextMonthGift = nextMonthGiftMap.get(giver2);
						nextMonthGiftMap.put(giver2, nextMonthGift + 1);
					} else { //선물 주고 받은 개수가 같을때
						if (giver1Idx > giver2Idx) { //1번의 선물지수가 2번 보다 클 때
							Integer nextMonthGift = nextMonthGiftMap.get(giver1);
							nextMonthGiftMap.put(giver1, nextMonthGift + 1);
						} else if (giver1Idx < giver2Idx) { //1번의 선물지수가 2번 보다 클 때
							Integer nextMonthGift = nextMonthGiftMap.get(giver2);
							nextMonthGiftMap.put(giver2, nextMonthGift + 1);
						}
					}
					// 이미 비교한 쌍을 추가, 쌍은 양방향으로 추가해야 함
					comparedPairs.add(giver1 + "-" + giver2);
					comparedPairs.add(giver2 + "-" + giver1);
				}
			}
		}
		
		// 주어진 Map에서 가장 큰 값을 찾기 위해 초기값 설정
		int maxValue = 0;

		// 주어진 Map을 순회하면서 가장 큰 값과 그에 해당하는 키 찾기
		for (Map.Entry<String, Integer> entry : nextMonthGiftMap.entrySet()) {
			int value = entry.getValue();

			// 현재 값이 최대값보다 크면 최대값 및 그에 해당하는 키 업데이트
			if (value > maxValue) {
				maxValue = value;
			}
		}
		answer = maxValue;
		return answer;
	}
}

 

모든 예시는

String[] friends = {"muzi", "ryan", "frodo", "neo"};
String[] gifts = {"muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi", "frodo muzi", "frodo ryan", "neo muzi"};

이 값으로 진행하겠습니다.

 

1. friends에 저장된 각 사람에 대해 반복문을 사용하여, 선물 지수, 선물 준 사람과 개수를 설정합니다.

처음에 muzi의 지수와 선물 줄 사람을 저장합니다.

{muzi={index=0, ryan=0, frodo=0, neo=0}}

 

2. gift 배열을 반복문을 진행하여 준 사람과 받은 사람의 선물지수를 관리하고 선물을 줬다면 그 사람의 선물 개수를 증가합니다.

 

예시가 필요할 것 같아요.

muzi가 줬을 때와 받았을 때를 예로 들어볼게요.

muzi는 frodo에게만 2번 주고

ryan에게 3번 , frodo에게 1번, neo에게 1번 받았네요.

그러면 선물지수의 값은 -3 이 됩니다.

muzi={index=-3, ryan=0, frodo=2, neo=0} 이런 값으로 저장됩니다!

 

그래서 반복문을 다 돌고 나면

 

{ryan={index=2, muzi=3, frodo=0, neo=0}, muzi={index=-3, ryan=0, frodo=2, neo=0}, 

neo={index=1, muzi=1, ryan=0, frodo=0}, frodo={index=0, muzi=1, ryan=1, neo=0}}

 

이런 값으로 저장됩니다.

 

3. 모든 사용자의 선물 개수 비교 및 선물지수 비교입니다. 대신 중복되는 선물 비교는 제거했습니다.

muzi가 ryan에게 준거와 ryan이 muzi에게 준거를 비교하고 다음 달에 누가 받을지 확인 후

set에 저장하여 중복을 없애는 방식으로 진행합니다.

 

선물을 준 개수가 많으면 다음 달에 선물을 받고

선물 주고받은 개수가 같으면 선물지수로 비교해서 다음 달에 선물 받는 사람을 정합니다.

 

만약에 제 방식으로 풀어보신다면 계속 테스트를 해보면서 문제풀이를 진행하시면 될 것 같아요.

(어떤 값이 나오는지 확인)

 

간단한 풀이

class Solution {
	public int solution(String[] friends, String[] gifts) {
		// key 사람이름, value 숫자인 map 저장
		Map<String, Integer> map = new HashMap<>();
		for (int i = 0; i < friends.length; i++) {
			map.put(friends[i], i);
		}
		// 선물지수를 저장할 int 배열
		int[] index = new int[friends.length];
		// 선물 교환을 저장할 int 배열
		int[][] record = new int[friends.length][friends.length];

		// 선물 주고 받은 배열로 지수 및 선물 교환 배열 추가
		for (String str : gifts) {
			String[] cur = str.split(" ");
			index[map.get(cur[0])]++;
			index[map.get(cur[1])]--;
			record[map.get(cur[0])][map.get(cur[1])]++;
		}

		int ans = 0;
		for (int i = 0; i < friends.length; i++) {
			int cnt = 0;
			for (int j = 0; j < friends.length; j++) {
				if (i == j) //중복제거
					continue;
				if (record[i][j] > record[j][i]) // 준 개수가 많으면 다음 달 받을 선물 증가 
					cnt++;
				else if (record[i][j] == record[j][i] && index[i] > index[j]) //같으면 index 비교 해서 다음 달 받을 선물 증가
					cnt++;
			}
			ans = Math.max(cnt, ans);
		}
		return ans;
	}

 

1. map 에 사람의 이름을 key로 하고 사람의 순서를 value로 저장합니다.

2. 선물지수를 저장할 배열과 선물 교환을 저장할 배열을 선언합니다.

3. 선물 교환 배열을 반복문 돌려서 선물지수와 선물 교환 배열을 저장합니다.

4. 저장된 배열을 이용하여 다음 달에 선물을 받을 사람을 비교합니다.

준 개수가 많으면 cnt를 더하고, 준 개수와 받은 개수가 같으면 선물 지수를 비교하여 다음 달 받을 선물을 증가합니다.

5. 최대 값 비교하여 결과 값에 재할당합니다.

 

소감

문제를 풀면서 중요하게 생각되는 것이 해답을 보지 말고 일단 고민을 많이 해보는 것과 자신의 코드를 리뷰하는 것 그리고 나보다 더 뛰어난 사람의 풀이를 리뷰하는 것이 중요하다고 생각합니다.

이 세 가지를 잘 한다면 금방 문제풀이 실력이 늘지 않을까라는 생각이 듭니다.

처음에는 잘 풀리지 않지만 많이 풀다보면 잘 풀게 되지 않을까 생각이 됩니다.