1) 문제 예시를 토대로 int[][] 2차원 배열에 각 i가 j로 준 선물 값을 세팅했다.
2) 이름값은 String인데, 2차원 배열을 int형으로 선언했기 때문에, 별도의 Map을 활용해서 각 String 별 idx 값을 세팅해주고, 그 idx값을 고유의 값으로 활용하려고 했다.
3) Map<Integer, Integer> pst 를 선언해서, 각 i에 대한 선물지수값을 세팅해줬다.
2차원 배열에는 각 i-j 간의 주고 받은 선물을 알기 위함이고
Map<Integer, Integer> pst 에는 각각의 i에 대한 선물지수 값을 세팅해는 용이다.
4) 이제 이 상태에서 이중 for문을 돌며 map[i[[j] 와 map[j][i] 값을 비교하고 둘 사이에 주고 받은 크기가 다를 때는 더 큰 쪽 기준으로 ++, 같거나 기록이 없어서 둘다 0 인 경우 선물 지수 값 큰 쪽으로 ++ 처리 했다.
이중 for문을 돌아도 된다고 생각했던 건 전체 사람 크기 데이터가 50까지만 들어오기 때문이다.
5) 그래서 가장 큰 선물값을 2로 나눠서 return 해줬고 정답 처리가 됐다.
🎈 2차원 배열을 순회하면서 ++처리 한 이후 arr[] 1차원 배열(=각 i별 다음 달 받을 선물 계산용 배열) 내부를 보면 기대했던 값보다 2배씩 컸다.
직접 그려보면서 값을++처리 해보니까 이유가 있다. 내가 2차원 배열을 순회하면서 각각 주고받은 정보를 2번씩 처리했기 때문이다. 2번씩 처리 된 것이니, 마지막에 제일 큰 값에 대해 2로 나눠서 return 해주면 되겠단 생각이 들었고 그렇게 했을 때도 정답 처리는 됐다.
만약, 중복없이 처리하고 싶다면 이중 for문은 똑같이 돌되, 앞선 i 행에서 처리한 값에 대해서는 continue 처리 해주면 된다.
import java.util.*;
class Solution {
static int N;
//솔루션 함수
public int solution(String[] friends, String[] gifts) {
N = friends.length;
Map<String, Integer> idx = new HashMap<>();
Map<Integer, Integer> pst = new HashMap<>();
for(int i=0; i<N; i++){
idx.put(friends[i], i);
pst.put(i, 0);
}
int[][] map = new int[N][N];
for(String x : gifts){
String a = x.split(" ")[0];
String b = x.split(" ")[1];
//a -> b로 향함
int A = idx.get(a);
int B = idx.get(b);
map[A][B]++;
//선물 지수 세팅
pst.put(A, pst.getOrDefault(A, 0) +1); //준 거
pst.put(B, pst.getOrDefault(B, 0) -1); //받은 거
}
//다음달에 받을 선물 계산용 배열
int[] arr = new int[N];
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(i==j) continue;
//i,j 둘 사이의 관계에서
if(map[i][j] > map[j][i]){ //i가 준게 더 크다면
arr[i]++;
}else if(map[j][i] > map[i][j]){ //j가 준 게 더 크다면
arr[j]++;
}else if(map[i][j] == map[j][i] || map[i][j] == 0 && map[j][i] == 0){ //기록 없거나, 같다면
//i, j선물 지수 비교
if(pst.get(i) > pst.get(j)) {
arr[i]++;
}else if(pst.get(j)> pst.get(i)){
arr[j]++;
}
}
}
}
int answer = 0;
for(int x : arr){
answer = Math.max(answer,x);
}
return answer/2;
}
}
💚 시간복잡도
내 생각에는 이중 for 문 돌면서 2차원 배열 처리해준 게 (사람 수 최대 50)이라서 2500 이고, gifts가 최대 10,000개 들어오지만 for문 1번 순회하면서 세팅해줬기 때문에 최악으로 10,000 돌았다고 해도 제한 시간 안에는 처리 될 거라 생각했다.
💚 회고
다 푼 이후에 내 코드가 단순 구현으로 너무 더럽게 푼 것 같아서 좀 더 깔끔하고 명확한 접근이 있을까 싶어서 찾아봤는데, 카카오 기출 해설지에도 이런 식의 단순 구현을 염두해두고 출제한 듯 하다.
내가 해설지와 조금 다르게 접근한 부분이 있다면 카카오 기출 해설지에서는 현재 i 기준으로 다른 N-1명에게 모두 준 선물은 배열 i행의 합, N-1명에게 받은 선물은 배열 i열의 합으로 구하여 선물 지수를 구하라고 되어 있는데, 나 같은 경우에는 HashMap<Integer, Integer> 로 애당초 2차원 배열 세팅해줄 때, 선물 지수를 세팅해줬다. 나는 이게 더 편하다. 카카오 기출 해설지
