[Lv.1] 프로그래머스 - 신고 결과 받기 : Java

프로그래머스

 

 

 

이해하기

처음 생각했던 프로세스는 다음과 같다.

• report의 중복을 없애자.
• map에 report 당한 사람의 이름과 횟수를 저장하자.
• id_list 순서대로, report 했더니 정지당한 사람의 수를 반환하자.

import java.util.*;
import java.util.Map.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        int[] answer = new int[id_list.length];
        Map<String, Integer> reportMap = new HashMap<>();
        Map<String, Integer> result = new HashMap<>();
        
        for (int i = 0; i < report.length; i++)  {
            for (int j = i + 1; j < report.length; j++) {
                if (report[i].equals(report[j])) {
                    report[j] = "";
                }
            }
        }
        
        for (String rep : report) {
            if (!rep.equals("")) {
                String key = rep.split(" ")[1];
                reportMap.put(key, reportMap.getOrDefault(key, 0) + 1);
            }
        }
        
        for (String id : id_list) {
            result.put(id, 0);
        }
        
        for (Entry<String, Integer> entry : reportMap.entrySet()) {
            if (entry.getValue() >= k) {
                for (String rep : report) {
                    if (rep.contains(entry.getKey()) && !rep.split(" ")[0].equals(entry.getKey())) {
                        result.put(rep.split(" ")[0], result.get(rep.split(" ")[0]) + 1);
                    }
                }
            }
        }
        
        for (int i = 0; i < id_list.length; i++) {
            for (Entry<String, Integer> entry : result.entrySet()) {
                if (entry.getKey().equals(id_list[i])) {
                    answer[i] = entry.getValue();
                    break;
                }
            }
        }
        
        return answer;
    }
}

 

위와 같이 작성해서 제출했더니 37.5점이 나왔다. 대부분은 시간초과!

제한 사항을 다시 보니 report의 길이가 최대 20만이었다.

내가 했던 풀이는 2중 for문이 많고, map도 2개나 있어서 그런지 시간이 오래 걸리는 것 같았다.

 

그래서 참고한 블로그⬇️

[프로그래머스] 신고 결과 받기 (Java)

 

Programmers - 신고 결과 받기(Java)

 

공통적으로 보이는 부분이 중복 제거 시 Set 사용, Map의 value에 Set<> 넣기였다.

 

 

문제풀이

import java.util.*;
import java.util.Map.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        int[] answer = new int[id_list.length];
        Map<String, HashSet<String>> map = new HashMap<>();
        Map<String, Integer> idxMap = new HashMap<>();
        
        for (int i = 0; i < id_list.length; i++) {
            String name = id_list[i];
            map.put(name, new HashSet<>());
            idxMap.put(name, i);
        }
        
        for (String s : report) {
            String[] str = s.split(" ");
            String from = str[0];
            String to = str[1];
            map.get(to).add(from);
        }
                
        for (int i = 0; i < id_list.length; i++) {
            HashSet<String> send = map.get(id_list[i]);
            if (send.size() >= k) {
                for (String name : send) {
                    answer[idxMap.get(name)]++;
                }
            }
        }
        
        return answer;
    }
}

 

앞부터 차분히 봐보자.

 

        int[] answer = new int[id_list.length];
        Map<String, HashSet<String>> map = new HashMap<>();
        Map<String, Integer> idxMap = new HashMap<>();

 

answer는 id_list의 길이만큼 만들어주고, 첫번째 Map에는 String과 HashSet<String>을 저장하도록 한다.

map의 String에는 신고 당한 사람의 이름, HashSet<>에는 그 사람을 신고한 사람의 set이 저장된다.

idxMap은 id_list의 순서(인덱스)를 저장해두는 용도이다.

 

        for (int i = 0; i < id_list.length; i++) {
            String name = id_list[i];
            map.put(name, new HashSet<>());
            idxMap.put(name, i);
        }

 

for문을 돌면서 id_list의 이름을 하나씩 가져와서 map의 key로 넣어주고, value로는 new HashSet<>()을 넣어준다.

idxMap에는 이름과 인덱스를 저장해둔다.

 

        for (String s : report) {
            String[] str = s.split(" ");
            String from = str[0];
            String to = str[1];
            map.get(to).add(from);
        }

 

report를 하나씩 가져와서 split(" ")하여 첫번째는 신고한 사람(from), 두번째는 신고당한 사람(to)으로 설정한다.

map.get(to)까지만 보면 신고당한 사람의 이름을 key값으로 하여 map에서 value를 가지고 오는데, 이 때 value는 HashSet이기에 add(from)을 할 수 있다.

 

        for (int i = 0; i < id_list.length; i++) {
            HashSet<String> send = map.get(id_list[i]);
            if (send.size() >= k) {
                for (String name : send) {
                    answer[idxMap.get(name)]++;
                }
            }
        }

 

다음으로 id_list순서대로 map에서 찾아 value를 가져와서 send라는 HashSet에 담는다.

이 때 send는 id_list[i] 라는 사람을 신고한 사람들의 set이다.

send의 사이즈가 k보다 크거나 같으면 정지당했다는 뜻이다.

 

정지당한 사람을 신고한 사람들은 알림을 받게 되니 answer[idxMap.get(name)]을 ++ 해준다.

 

 

 

중복 = Set 사용하기!

제한사항 잘 읽기!