Q. 문자열 두 개가 주어졌을 때 이 둘이 서로 순열 관계에 있는지 확인하는 메서드를 작성하라.

첫 번째 방법: 정렬하라

두 문자열이 순열관계에 있다는 말이 무슨 의미인지 설명해 보라. 그 정의에 따라 문자열을 확인할 수 있겠는가?

순열 관계라는 것은 두 문자열에서 사용된 문자는 같은데 문자의 순서만 다른 형태라는 것을 의미한다. 따라서 문자열을 정렬하면 둘 다 같은 결과가 나와야 한다.

시간 복잡도

정렬은 O(n log n)의 시간이 걸린다.

Java 정렬 방식 시간 복잡도

• Arrays.sort()
  • DualPivotQuicksort
  • 평균 : O(nlog(n)) / 최악 : O(n^2)

    public static void sort(char[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

• Collections.sort()
  • TimeSort (삽입정렬과 합병정렬을 결합한 정렬)
  • 평균, 최악 : O(nlog(n))

    public static <T extends Comparable<? super T>> void sort(List<T> list) {
        list.sort(null);
    }

코드

public class QuestionA {	
	public static String sort(String s) {
		char[] content = s.toCharArray();
		java.util.Arrays.sort(content);
		return new String(content);
	}
	
	public static boolean permutation(String s, String t) {
		return sort(s).equals(sort(t));
	}	
	
	public static void main(String[] args) {
		String[][] pairs = {{"apple", "papel"}, {"carrot", "tarroc"}, {"hello", "llloh"}};
		for (String[] pair : pairs) {
			String word1 = pair[0];
			String word2 = pair[1];
			boolean anagram = permutation(word1, word2);
			System.out.println(word1 + ", " + word2 + ": " + anagram);
		}
	}
}

---

두 번째 방법: 문자열에 포함된 문자 출현 횟수가 같은지 검사하라

순열의 정의, 즉 두 문자열이 동일한 문자 개수를 갖고 있다는 점을 이용해서 알고리즘을 구현합니다. 배열 두 개 사용해서 각 문자열 내의 문자 출현 횟수를 기록한 다음, 두 배열을 비교한다.

public class QuestionB {	
	public static boolean permutation(String s, String t) {
		if (s.length() != t.length()) return false; // Permutations must be same length
		
		int[] letters = new int[128]; // Assumption: ASCII
		for (int i = 0; i < s.length(); i++) {
			letters[s.charAt(i)]++;
		}
		  
		for (int i = 0; i < t.length(); i++) {
			letters[t.charAt(i)]--;
		    if (letters[t.charAt(i)] < 0) {
		    	return false;
		    }
		}
		  
		return true; // letters array has no negative values, and therefore no positive values either
	}
	
	public static void main(String[] args) {
		String[][] pairs = {{"apple", "papel"}, {"carrot", "tarroc"}, {"hello", "llloh"}};
		for (String[] pair : pairs) {
			String word1 = pair[0];
			String word2 = pair[1];
			boolean anagram = permutation(word1, word2);
			System.out.println(word1 + ", " + word2 + ": " + anagram);
		}
	}
}