[LeetCode/EASY] 760. Find Anagram Mapping (JAVA) : 문제&풀이

 

 

애너그램 맵에 해당하는 인덱스를 반환하는 문제이다.

int 배열 두 개를 매개변수로 받는 anagramMappings 메서드의 틀이 주어진다.

 

Problem : 

public class FindAnagramMapping {
    public int[] anagramMappings(int[] A, int[] B) {

    }
}

풀이는 주어진 anagramMappings 메서드에 작성하면 된다.

 

Solution :

1. 주어진 배열 B로 anagram(key) - index(value)로하는 애너그램 맵을 만든다.
2. 주어진 배열 A를 돌며 애너그램 맵에서 해당하는 index를 구해서 배열로 반환한다.

import java.util.HashMap;
import java.util.Map;

public class FindAnagramMapping {

    // time complexity : for loop for given array -> O(n)
    // space complexity : HashSet (length of given array) -> O(n)
    public int[] anagramMappings(int[] A, int[] B) {
    
        Map<Integer, Integer> anagramMap = new HashMap<>();
        for(int i = 0; i < B.length; i++){
            anagramMap.put(B[i], i);
        }

        int[] result = new int[A.length];
        for(int i = 0; i < A.length; i++){
            result[i] = anagramMap.get(A[i]);
        }

        return result;
    }
}

 

 

Complexity :

• 시간복잡도 (Time Complexity)
  • 주어진 숫자 배열 길이에 따라 for문 반복하므로 O(n)
• 공간복잡도 (Space Complexity)
  • 주어진 숫자 배열 길이에 해당하는 HashSet을 사용하므로 O(n)

 

Sample(Test) :

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class FindAnagramMapping {

    // time complexity : for loop for given array -> O(n)
    // space complexity : HashSet (length of given array) -> O(n)
    public int[] anagramMappings(int[] A, int[] B) {
        
        Map<Integer, Integer> anagramMap = new HashMap<>();
        for(int i = 0; i < B.length; i++){
            anagramMap.put(B[i], i);
        }

        int[] result = new int[A.length];
        for(int i = 0; i < A.length; i++){
            result[i] = anagramMap.get(A[i]);
        }

        return result;
    }

    public static void main(String[] args){
        int[] A1 = {12, 28, 46, 32, 50};
        int[] B1 = {50, 12, 32, 46, 28};
        int[] A2 = {1, 2, 3, 4, 5};
        int[] B2 = {5, 4, 3, 2, 1};

        FindAnagramMapping f = new FindAnagramMapping();
        System.out.println(Arrays.toString(f.anagramMappings(A1, B1)));
        System.out.println(Arrays.toString(f.anagramMappings(A2, B2)));
    }
}

 

위 테스트 코드를 실행한 결과는 다음과 같다.

[1, 4, 3, 2, 0]
[4, 3, 2, 1, 0]