811. Subdomain Visit Count

학기 끝나고 오랜만에 풀어보는 알고리즘 문제다. C++을 사용하다가 Java로 넘어오면서 적응하느라 고생을 좀 했다.

 

문제

 - 숫자와 도메인으로 이루어진 String pair

 - 앞에 숫자는 도메인을 얼마나 방문했는지 나타내는 것

 - 도메인을 "."으로 나누었을 때 각각 총 방문 숫자를 각각 나태는 List를 return 할 것

 

해결 방법

 - Hash Table과 Brute Force를 이용하기

 

public List<String> subdomainVisits(String[] cpdomains) {
        int size = cpdomains.length;
        HashMap<String, Integer> map = new HashMap<>();
        List<String> output = new ArrayList<String>();
        
        for (int i = 0; i < size; i++){
            //Splitting the number and domains
            String[] numb = cpdomains[i].split(" ", 0);
            String[] domain = numb[1].split("[.]", 0);
            int val = Integer.parseInt(numb[0]);
            String tmp = "";

 

숫자와 도메인을 먼저 나누면 String Array에 두개의 element가 생기게 됩니다 (ex. numb = ["9001", "discuss.leetcode.com"]).

 

그런 뒤 두번 째 element를 또 split 해주게 되면 domain = ["discuss", "leetcode", "com"]과 같은 배열을 가지게 됩니다. 여기서 조심해야 할 점은 discuss.leetcode.com, leetcode.com, com이 각각 앞에 숫자를 더 할 때 구분해서 더 해줘야 되는거죠.

 

그래서 사용한 방법이 array 뒤에서 부터 접근하는 방법이었습니다.

for(int j=domain.length-1; j >= 0; j--){
                if(j==domain.length-1){
                    tmp += domain[j];
                    if(map.containsKey(tmp)){
                        map.put(tmp, map.get(tmp)+val);
                    }else{
                        map.put(tmp,val);
                    }
                }else{
                    tmp = domain[j] + "." + tmp;
                    if(map.containsKey(tmp)){
                        map.put(tmp, map.get(tmp)+val);
                    }else{
                        map.put(tmp, val);
                    }
                }
            }
        }

배열 뒤에서부터 접근 했을 때 HashMap에 들어가는 Key의 순서는 com => leetcode.com => discuss.leetcode.com 순으로 들어가게 됩니다. 

 

처음 알고리즘을 디자인 했을 때는 앞에서 부터 접근하는 방법이었는데 이런 방법으로 접근하게 되면 discuss, leetcode 등 앞에 있는 도메인 주소를 삭제해줘야하는 번거로움이 있더라구요. 그래서 backtracking 방법이 훨씬 편하게 쓰일 수 있었습니다.

 

 

 for (String e : map.keySet()){
            String tmp = String.valueOf(map.get(e)) + " " + e;
            output.add(tmp);
        }
        
        return output;

그리고 마지막으로 List<String>에 문제에서 원하는 방식대로 add 하고 return 해줍니다.

 

새롭게 써본 것들

 -map.containsKey(Object): it returns boolean if the map contains "object".

 -map.put(key, value): it puts the value into the key. If there is key in the map, it updates the value.

 -map.get(key): It returns the value of key.

 -List.add(Element): It adds the element into the list.

 -valueOf: It returns the "relevant Number Object holding the value of the argument passed".

 -Integer.paseInt: It converts the string into integer.