프로그래머스 Java Lv1 가장 많이 받은 선물

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

 

해당 문제는 단순 구현으로 쉽게 풀 수 있는 문제이다.

 

규칙은 단순하다.

1. 주고 받은 적이 있고, 그 정도에 차이가 있다면 많이 준 사람이 선물을 하나 받는다.

2. 주고 받은 적이 없거나, 그 정도가 같다면 선물 지수를 비교한다.

3. 선물 지수도 같다면 선물을 주고 받지 않는다.

 

이러한 규칙에 따라서 다음 달 받을 선물의 수를 계산하기 위해서 다음과 같은 변수가 필요하다.

1. 주고 받은 선물 내역을 저장할 변수

2. 선물 지수를 저장할 변수

3. 다음달 받는 선물의 수를 저장할 변수

 

다음과 같은 데이터를 저장하기 위해서 각각 다음과 같은 자료형이 필요하다.

1. 이차원 정수형 배열 int[][] history - 주어진 n명의 사람이 주고 받은 내역을 저장해야 하므로 이차원 배열

2. 일차원 정수형 배열 int[] giftScore - 주어진 n명의 사람의 선물 지수를 저장해야 하므로 일차원 배열

3. 일차원 정수형 배열 int[] nextMonthGift - 주어진 n명의 사람이 다음 달 받는 선물의 수를 저장해야 하므로 일차원 배열

 

그리고 각각의 사람의 이름과 변수에서의 index를 저장하기 위해 Map 자료형을 하나 필요로 한다.

4. HashMap<String, Integer> friendIdx - 주어진 사람의 이름과 배열에서의 index 를 저장

 

 

우선 주어진 gifts 입력으로부터 주고 받은 내역과 선물 지수를 계산하자.

gifts는 "A B" 형태의 문자열로 A가 B에게 주었다는 데이터를 담고 있기 때문에 주고 받은 내역과 선물 지수를 알 수 있다.

 

주고 받은 내역과 선물 지수만 있다면 다음 달 받는 선물의 수는 쉽게 계산할 수 있다.

처음 말했던 규칙에 따라 다음 달 받는 선물의 수만 계산하면 되기 때문이다.

단, 이 때 주의할 점은 history의 절반만 탐색하면 된다는 것이다.

 

3명의 사람 A, B, C가 있다고 생각해보자. 그렇다면 history 배열은 다음과 같은 형태를 하고 있을 것이다.

history 배열에서 값을 꺼내 주고 받은 내역을 계산하기 위해서 n*n 번 반복할 필요는 없다.

 

그림을 보자. 두 사람이 서로 선물을 주고 받았다면 그 위치는 대칭을 이룬다.

즉 history 배열에 접근할 때, 준 사람과 받은 사람의 index를 서로 바꾸면 되는 것이다.

 

A가 B에게 준 내역을 기록한 위치는 history[ 0 ][ 1 ] 이다.

B가 A에게 준 내역을 기록한 위치는 history[ 1 ][ 0 ] 이다.

 

A가 C에게 준 내역을 기록한 위치는 history[ 0 ][ 2 ] 이다.

C가 A에게 준 내역을 기록한 위치는 history[ 2 ][ 0 ] 이다.

 

 

이 문제를 푸는 사람 중 주고받은 기록이 없는 경우는 어떻게 처리하지? 에 대해 고민하는 사람이 있다면 고민하지 않아도 된다. 다음 문제의 규칙 중 "주고받은 기록이 없거나 주고받은 수가 같다면 선물지수를 비교"라는 규칙이 있다.

자바에서 정수형 이차원 배열을 초기화 하지 않는다면 기본적으로 0 값으로 초기화 된다. 즉, 주고받은 기록이 없다면 0 으로 초기화 되고, 주고받은 수가 0으로 같기 때문에 주고받은 기록이 없거나 같은 경우를 분리하지 않아도 된다.

 

코드

import java.util.HashMap;
import java.util.Arrays;

class Solution {
        public int solution(String[] friends, String[] gifts) {
        int n = friends.length;
        int[][] history = new int[n][n]; //주고 받은 선물 내역 저장
        int[] giftScore = new int[n]; //선물 지수 저장
        int[] nextMonthGift = new int[n]; //다음달 받는 선물의 수 저장

        HashMap<String, Integer> friendIdx = new HashMap<>(); //친구들의 index를 저장
        for (int i = 0; i < n; i++) {
            friendIdx.put(friends[i], i);
        }

        for (String gift : gifts) {
            String[] tmp = gift.split(" ");
            int giverIdx = friendIdx.get(tmp[0]);
            int takerIdx = friendIdx.get(tmp[1]);

            //선물을 주고 받은 내역 기록
            history[giverIdx][takerIdx]++;

            //선물 지수를 계산
            giftScore[giverIdx]++;
            giftScore[takerIdx]--;
        }

        //history 배열은 주고 받은 관계가 i와 j가 대칭을 이루므로 절반만 반복하면 된다.
        for (int giver = 0; giver < n; giver++) {
            for (int taker = giver + 1; taker < n; taker++) {
                int give = history[giver][taker];
                int take = history[taker][giver];

                //주고 받은 선물 계산
                if (give > take) {
                    nextMonthGift[giver]++;
                }
                else if (give < take) {
                    nextMonthGift[taker]++;
                }
                //주고 받은 기록이 없거나 주고 받은 수가 같은 경우 선물 지수를 비교한다.
                else {
                    if (giftScore[giver] > giftScore[taker]) {
                        nextMonthGift[giver]++;
                    } else if (giftScore[giver] < giftScore[taker]) {
                        nextMonthGift[taker]++;
                    }
                }
            }
        }

        //선물 지수 중 가장 큰 값을 찾아 반환
        return Arrays.stream(nextMonthGift)
                .max()
                .getAsInt();
    }
}