[알고리즘] 두개의 문자열이 서로 순열인지 확인하기[알고리즘] 두개의 문자열이 서로 순열인지 확인하기

Posted at 2015.02.12 13:05 | Posted in 알고리즘 문제



facebook에 글올리기



[알고리즘] 두개의 문자열이 서로 순열인지 확인하기


문제


문자열 두 개를 입력으로 받아 그중 하나가 다른 하나의 순열인지 판별하는 메서드를 작성하라.



풀이


순열이라는 것은 서로가 문자열의 종류와 숫자가 같으면서 배열된 순서가 다른 것을 말한다.

따라서 순열이라면 두 문자열의 길이가 같고 각각의 문자열을 정렬한 결과가, 같은 문자열이 되어야 한다.


* 여기서는 대/소문자가 구분되며, 공백도 하나의 문자로 취급한다. 

(다른 조건이라면 해당 조건을 변환하거나 체크해줘야 한다.)


 Colored By Color Scripter



import static org.junit.Assert.*;
import org.junit.Test;

public class Permutation {

    
    public boolean isPermutation(String targetStr, String basicStr){

        if(targetStr.length() != basicStr.length()) return false;        
        
        return sortString(targetStr).equals(sortString(basicStr));
    }
    
    private String sortString(String str){
        char[] arrayChar = str.toCharArray();
        java.util.Arrays.sort(arrayChar);
        return new String(arrayChar);
    }
    
    @Test
    public void isPermutationTest(){
        
        assertTrue(isPermutation("abcd", "dcba"));
        assertTrue(isPermutation("abc ", "a bc"));
        
        assertFalse(isPermutation("abcd", "abce"));
    }    
}



풀이 2

정렬하여 비교하는 방법은 직관적인 알고리즘이지만, 효율적인 측면을 강조하기 위해서는 다른 방법을 생각 할 수 있다.

각 문자열을 탐색하면서 각 문자의 출현 횟수를 비교하면 된다.


문자는 ASCII 코드라 가정하고 출현 카운트를 저장하는 letter[256] 배열을 선언한다.

문자열을 탐색하면서 해당 문자에 해당하는 ASCII 코드 인덱스의 값을 ++ 시키고 다른 문자열을 탐색하면서 출현한 문자를 -- 시키면서  -- 결과가 0보다 작으면, 출현횟수가 다른 것이므로 false를 반환한다.



Colored By Color Scripter



import static org.junit.Assert.*;
import org.junit.Test;

public class Permutation {

    
    public boolean isPermutation2(String targetStr, String basicStr){
        
        if(targetStr.length() != basicStr.length()) return false;
        
        int[] letters = new int[256];    // ASCII 코드 256개
        
        char[] targetArray = targetStr.toCharArray();
        for(char c : targetArray){
            letters[c]++;
        }
        
        for(int i = 0; i<basicStr.length(); i++){
            int c = (int)basicStr.charAt(i);
            if(--letters[c]<0){
                return false; 
            }
        }
        
        return true;
    }
    
    @Test
    public void isPermutation2Test(){
        
        assertTrue(isPermutation2("abcd", "dcba"));
        assertTrue(isPermutation2("abc ", "a bc"));
        
        assertFalse(isPermutation2("abcd", "abce"));
    }
}


이웃추가
facebook에 글올리기

Name __

Password __

Link (Your Website)

Comment

SECRET | 비밀글로 남기기