연습#1 599. Minimum Index Sum of Two Lists

 

안녕하세요.

저는 알고리즘에 매우 취약하다는 약점을 가지고 있습니다. 이를 개선하기 위해 매일매일 쉬운 것부터 하나씩 풀어보기로 했습니다. 

언젠가 저도 알고리즘이 익숙할 날이 오겠죠?

 

LeetCode#599. Minimum Index Sum of Two Lists

Minimum Index Sum of Two Lists - LeetCode

 

 

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        
        List<String> answer = new ArrayList<String>();
        Map<String, Integer> list1Map = new HashMap<String, Integer>();
        for (int i=0; i<list1.length; i++) {
            list1Map.put(list1[i], i);
        }

        List<Pair<String, Integer>> pairs = new ArrayList();   
        for (int j=0; j<list2.length; j++) {
            if (list1Map.containsKey(list2[j])) {
                int sum = list1Map.get(list2[j]) + j;
                pairs.add(new Pair(list2[j], sum));
            }    
        }

        int min = pairs.get(0).getValue();
    
        for (int i=0; i<pairs.size(); i++) {
            if (min > pairs.get(i).getValue()) {
                min = pairs.get(i).getValue();
            }
        }

         for (int i=0; i<pairs.size(); i++) {
            if (pairs.get(i).getValue() == min) {
                answer.add(pairs.get(i).getKey());
            }
        }

       return answer.stream().toArray(String[]::new);
    }
}

총 3번의 Submit으로 얻어낸 결과입니다ㅠㅠ.. 

 

처음 두번은 이중 for문(O(n^2))으로 100ms가 넘게 나왔는데요,

두 배열을 비교할 때 이중 for문을 사용하지 말고 Map에 첫 번째 배열을 할당해놓고 for문 하나로 비교하는 방식을 사용하여 해결하였습니다. 

 

갈 길이 참 멉니다.