Strings: Making Anagrams java 풀이

Strings: Making Anagrams | HackerRank

 

 

시간복잡도 참고

https://hbase.tistory.com/185

[Java] 컬렉션들의 시간복잡도 (Collection Big-O)

 

list.contains의 시간복잡도는 O(n) 이기 때문에

내 풀이의 시간복잡도는 O(n^2)이 될 수 있다.

 

공식 풀이를 보면 아스키코드를 사용해서 O(n)에 끝내는걸 확인할 수 있는데

좋은 방법인 것 같음 :)

 

 

내 풀이

class Result {

	/*
	 * Complete the 'makeAnagram' function below.
	 *
	 * The function is expected to return an INTEGER. The function accepts following parameters: 1. STRING a 2. STRING b
	 */

	public static int makeAnagram(String a, String b) {
		// Write your code here
		ArrayList<Character> list = new ArrayList<Character>();

		for (char c : b.toCharArray())
			list.add(c);

		int res = 0;

		
		for (char c : a.toCharArray()) {
			if (list.contains(c)) {
				list.remove((Character)c);
			} else {
				res++;
			}
		}

		res = res + list.size();

		return res;
	}

}

공식 풀이 (아스키코드 사용)

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static int numberNeeded(String first, String second) {
        int[] charSet = new int[256];
        
        for(int i=0; i<first.length(); i++)
            charSet[first.charAt(i)]++;
        
        for(int i=0; i<second.length(); i++)
            charSet[second.charAt(i)]--;
        
        int numberNeeded = 0;
        for(int i=0; i<256; i++)
            numberNeeded += Math.abs(charSet[i]);
        
        return numberNeeded;
     }
  
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String first = in.next();
        String second = in.next();
        System.out.println(numberNeeded(first, second));
    }
}