[프로그래머스 / Java] 가장 많이 받은 선물

문제 정보 및 풀이 시간

• 난이도: 레벨 1

• 예상 태그: 구현, 시뮬레이션

• 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/258712

• 푸는 데 걸린 시간: 50m

풀이

A와 B 사이에 주고 받은 선물 중에서 누가 더 많이 주었는지를 판단해야한다. 행에 있는 사람이 giver, 열에 있는 사람이 taker인 테이블을 만들어야 한다.
이때 사람의 리스트가 String[]으로 주어지는데 테이블을 만들려면 사람을 인덱스로 바꾸어야하기 때문에 "key = 사람이름, value = 인덱스"인 HashMap을 선언해준다.

전체적인 풀이과정은 아래와 같다.

1. 선물을 주고 받는 선물 테이블을 만든다. (아래 코드에서 변수명이 table인 배열에 해당한다.)
2. 1에서 만든 2차원 배열을 이중 포문으로 돈다. 이때 주의할 점은 행렬의 우측 위만 봐야한다. 즉 i < j인 부분만 보는 것이다. 전체 행렬을 다 보게 되면 중복해서 세게 된다.
3. i, j 중 선물을 받게될 사람을 판단한다.
   (i) i가 j 보다 많이 줬거나, j가 i보다 많이 줬다면 많이 준 쪽의 count[인덱스] += 1 해준다.
   (ii) 둘의 주고 받은 수가 같다면(아니면 주고받은 기록이 없다면) 선물 지수를 구한다. 즉 총 준 수 (i행 값만 쭉 더한거) - 총 받은 수 (i열 값만 쭉 더한거)를 계산하는 것이다. 선물지수도 같다면 그냥 넘어간다.
4. count 배열을 돌면서 가장 큰 수를 찾아 리턴한다.

import java.util.*;

class Solution {
    public int solution(String[] friends, String[] gifts) {
        int answer = 0;
        int[] count = new int[friends.length];
        int[][] table = new int[friends.length][friends.length];
        
        Map<String, Integer> map = new HashMap<>();
        
        // 맵 만들기
        for(int i=0; i<friends.length; ++i) {
            map.put(friends[i], i);
        }
        
        // 초기화
        for(int i=0; i<friends.length; ++i) {
            for(int j=0; j<friends.length; ++j) {
                table[i][j] = 0;
            }
            count[i] = 0;
        }
        
        // 선물 테이블 만들기
        for(int i=0; i<gifts.length; ++i) {
            StringTokenizer st = new StringTokenizer(gifts[i]);
            int giver = map.get(st.nextToken());
            int taker = map.get(st.nextToken());
            
            table[giver][taker] += 1;
        }
        
        
        // 1을 이중 포문으로 돌기
        for(int i=0; i<friends.length; ++i) {
            for(int j=0; j<friends.length; ++j) {
                // if(i==j) continue;
                if(i >= j) continue; // 중복
                
                int i_give = table[i][j], j_give = table[j][i];
                if(i_give > j_give) {
                    count[i] += 1;
                } else if(i_give < j_give) {
                    count[j] += 1;
                } else { // 같음. 선물 지수 구하기
                    int i_score = 0;
                    int give = 0, take = 0;
                    for(int k=0; k<friends.length; ++k) {
                        give += table[i][k];
                        take += table[k][i];
                    }
                    i_score = give - take;
                    
                    int j_score = 0;
                    give = 0; take = 0;
                    for(int k=0; k<friends.length; ++k) {
                        give += table[j][k];
                        take += table[k][j];
                    }
                    j_score = give - take;
                    
                    if(i_score > j_score) {
                        count[i] += 1;
                    } else if(i_score < j_score) {
                        count[j] += 1;
                    }
                }
            }
        }
        
        // 가장 큰 값 구하기
        answer = count[0];
        for(int cnt : count) {
            if(answer < cnt) answer = cnt;
        }
        return answer;
    }
    
}

자체 피드백

쉬운 구현 문제인데 50분이 걸렸다.. 그 이유는

• 행렬의 우측 위만 봐야한다는 것을 처음에 파악하지 못하고, i==j 일때에만 continue 해서 넘어갔다. 이는 테스트 케이스 3개 중 하나를 보고 하나씩 손으로 계산해보다가 중복이 발생한다는 것을 깨달았다.
• 선물 지수를 구하는 부분에서 행,열을 헷갈렸는지, i,k와 j,k의 순서를 반대로 구해서 선물지수에 - 붙인 값을 구하게 되었었다.

풀이만 쓰지 말고 슈도 코드도 한번 써봐야 하나..? 싶다.
이런 자잘한 실수는 어떻게 빨리 파악할 수 있는 것일까