소내기 블로그

초보 개발자 코드 트레이닝, Part 2: 알고리즘과 성능

이전 포스트에 이어서 또 퀴즈를 풀어보았습니다.

Quiz 1,2는 다른 사람들도 모두 풀었던 관계로 생략합니다. 예제속에 답이 있어서 좀싱거운듯. Quiz 3, 4를 이어서 풀었는데, subString 매칭 메쏘드는 좀 구현이 복잡해졌습니다. 다시 한번 리펙토링해야할듯. 일단 소스 나갑니다.





어느 배열이 어느 배열에 포함되는지 확인하는 메소드입니다. 순서도 맞아야합니다.

Quiz 3 :
    public static boolean isSubstring(char[] subChars, char[] targetChars) {
        boolean result = false;
        if(targetChars.length < subChars.length)
            result = false;
       
        char subFirst = subChars[0];
        // sub의 첫번째 문자가 targetChars에서 처음 만나는 index를 얻는다.
        int targetPos = targetChars.length;
        Queue targetPosQueue = new LinkedList();
       
        for(int index = 0 ; index < targetChars.length ; index++) {
            char eachTarget = targetChars[index];
            if(eachTarget == subFirst) {
                targetPos = index;
                targetPosQueue.offer(Integer.valueOf(targetPos));
            }
        }

        // 첫번재 만나는 인덱스 Queue를 얻어 성공할때까지 돌린다.
        Integer targetPosPoll = null;
        while((targetPosPoll = (Integer)targetPosQueue.poll()) != null
                && result == false) {
           
            targetPos = targetPosPoll.intValue();
           
            int subPos = 0;
            for(int index = targetPos ; index <  targetChars.length ; index++) {
                char eachTarget = targetChars[index];
               
                // subChars를 넘어가면 더이상 비교할필요없다.
                if(subChars.length <= subPos) {
                    break;
                }
               
                if(subChars[subPos] == eachTarget) {
                    result = true;
                    subPos++;
                } else {
                    result = false;
                    break;
                }
            }
            // 검사해야할 subChars가 남았다면 false
            //System.out.println("subPos:" + subPos);
            //System.out.println("subChars.length:" + subChars.length);
            if(result == true && (subPos < subChars.length)) {
                result = false;
            }
        }
       
        return result;
    }

배열의 순서까지 체크를 해야함으로 Sort를 해서 하나씩 비교하는건 불가능했습니다.(가능할지도) 소스가 조금 꼬였네요. 테스트 코드는 JUnit 4를 사용하였습니다.

Quiz 3 Test
public class PatternSubstringTest {

    @Test
    public void test() {
        char[] subChars = {'1', '2', '3', '4'};
        char[] targetChars1 = {'1', '2', '3'};
        char[] targetChars2 = {'1', '2', '3', '4'};
        char[] targetChars3 = {'1', '2', '3', '5'};
        char[] targetChars4 = {'1', '2', '3', '6'};
        char[] targetChars5 = {'1', '2', '3', '8'};
        char[] targetChars6 = {'0', '1', '2', '4', '1'};
        char[] targetChars7 = {'0', '1', '2', '3', '2'};
        char[] targetChars8 = {'0', '1', '2', '3', '4', '9'};

        assertFalse(PatternSubstring.isSubstring(subChars, targetChars1));
        assertTrue(PatternSubstring.isSubstring(subChars, targetChars2));
        assertFalse(PatternSubstring.isSubstring(subChars, targetChars3));
        assertFalse(PatternSubstring.isSubstring(subChars, targetChars4));
        assertFalse(PatternSubstring.isSubstring(subChars, targetChars5));
        assertFalse(PatternSubstring.isSubstring(subChars, targetChars6));
        assertFalse(PatternSubstring.isSubstring(subChars, targetChars7));
        assertTrue(PatternSubstring.isSubstring(subChars, targetChars8));
    }
}

이번에는 부등호를 포함한 괄호들이 서로 열고 닫음이 정확한지를 테스트하는 메소드입니다. html validator같은것을 만들때쓰일수 있겠네요. Stack를 쓰면 될것같았는데, 생각보다 구현이 어렵지 않았습니다. 자료구조 만세입니다!

Quiz 4:
public class MatchQuiz {

    private static char[] START_TAGS = { '(', '{', '[', '<'};
    private static char[] END_TAGS = { ')', '}', ']', '>' };

    public static boolean match(char[] src) {

        Stack<Character> checkStack = new Stack<Character>();
        Stack<Character> remainStack = new Stack<Character>();

        List<Character> startTags = new ArrayList<Character>();
        for (char o : START_TAGS) {
            startTags.add(o);
        }
        List<Character> endTags = new ArrayList<Character>();
        for (char o : END_TAGS) {
            endTags.add(o);
        }

        List<Character> allTags = new ArrayList<Character>();
        allTags.addAll(startTags);
        allTags.addAll(endTags);

       
        for (char eachChar : src) {
            if (!allTags.contains(eachChar)) {
                continue;
            }

            if (startTags.contains(eachChar)) {
                checkStack.push(eachChar);
            } else if (endTags.contains(eachChar)) {
                if (endTags.get(startTags.indexOf(checkStack.peek())).equals(
                        eachChar)) {
                    checkStack.pop();
                } else {
                    remainStack.push(eachChar);
                }
            }
        }

        System.out.println("LOG checkStack : " + checkStack.toString());
        System.out.println("LOG remainSTack : " + remainStack.toString());
        return checkStack.size() == 0 && remainStack.size() == 0 ? true : false;
    }

    public static void main(String[] args) {
        char[] first = { '(', '[', '<', '{', '}', '>', ']', ')' };
        char[] second = { '(', '[', '<', '{', '>', '}', ']', ')' };
        char[] third = { '(', 'a', 'c', ')', '[', '{', '}', ']' };
        System.out.println(match(first)); // yes
        System.out.println(match(second)); // no
        System.out.println(match(third)); // yes
    }
}

Java 1.4를 쓰다가 불편해서 1.5로 올렸습니다.(아 정말 1.4는 불편해요)