Heart’s Develop Inside

    public static ArrayList both(ArrayList xs, ArrayList ys) {
            ArrayList bothList = new ArrayList();
            Object y = null;
            // 먼저 첫 번째 리스트를 몽땅 저장
            bothList.addAll(xs);
            Iterator elems = ys.iterator();
            while( elems.hasNext() ) {
                y = elems.next();
                // 첫 번째 리스트에 값이 없을 경우에만 추가
                if( !xs.contains(y) )
                    bothList.add(y);
            }
            return bothList;
        }

    public static ArrayList fastEither(ArrayList xList, ArrayList yList) {
        ArrayList eitherList = new ArrayList();
        final int xSize = xList.size();
        final int ySize = yList.size();
        Comparable x, y;
        int order, xpos, ypos;
        xpos = ypos = 0;
        while( xpos < xSize && ypos < ySize ) {
            x = (Comparable)xList.get(xpos);
            y = (Comparable)yList.get(ypos);
            order = x.compareTo(y);
            if( order < 0 ) {            // x가 작음
                xpos++;
            } else if( order > 0 ) {    // y가 작음
                ypos++;
            } else {                    // x = y
                eitherList.add(x);
                xpos++;
                ypos++;
            }
        }
        return eitherList;
    }

    public static boolean isSubstring(char[] left, char[] right) {
        final int leftCount = left.length;
        final int rightCount = right.length;
        for( int i = 0 ; i < rightCount ; i++ ) {
            if( left[0] == right[i] ) {
                boolean same = true;
                for( int j = 1 ; j < leftCount ; j++ ) {
                    if( left[j] != right[i+j] ) {
                        same = false;
                        break;
                    }
                }
                if( true == same )
                    return true;
            }
        }
        return false;
    }

    public class MatchTest {
        private static final String KIND_OF_BRACKETS_LEFT = "([< {";
        private static final String KIND_OF_BRACKETS_RIGHT = ")]>}";
 
        public static boolean isLeftBrackets(char ch) {
            if( -1 == KIND_OF_BRACKETS_LEFT.indexOf(ch) )
                return false;
 
            return true;
        }
 
        public static boolean isRightBrackets(char ch) {
            if( -1 == KIND_OF_BRACKETS_RIGHT.indexOf(ch) )
                return false;
 
            return true;
        }
 
        public static boolean isBracketMatch(char leftBracket, char rightBracket) {
            int leftBracketIdx = KIND_OF_BRACKETS_LEFT.indexOf(leftBracket);
            int rightBracketIdx = KIND_OF_BRACKETS_RIGHT.indexOf(rightBracket);
 
            if( (-1 == leftBracketIdx) || (-1 == rightBracketIdx) )
                return false;
 
            return (leftBracketIdx == rightBracketIdx);
        }
 
        public static boolean matchUseStack(char[] cs) {
            final int length = cs.length;
            if( 0 == length )
                return false;        // 길이가 0인 경우도 짝이 없다고 가정함
 
            /*
             * ArrayList로 할 수도 있지만 배열 사이즈가 어느 정도 정해져 있기 때문에 이렇게 함
             * cs의 크기가 크다면 ArrayList가 나을 수도 있음(하지만 ArrayList를 사용하면 Object로 저장해야 함)
             *
             * Stack의 길이는 cs의 길이의 반이면 됨, 그 이상 넘어가면 짝이 있을 수 없음.
             */
            int stackLen = length / 2;
 
            char[] stack = new char[stackLen];
 
            int stackIdx = 0;
            for( int i = 0 ; i < length ; i++ ) {
                char ch = cs[i];
 
                if( isLeftBrackets(ch) ) {
                    // Stack에 집어넣음
                    if( stackIdx >= stackLen ) {
                        // Stack이 꽉 찼음. 짝이 없음을 의미
                        return false;
                    }
 
                    stack[stackIdx] = ch;
                    stackIdx++;
 
                } else if( isRightBrackets(ch) ) {
                    // Stack에서 하나를 빼서 비교
                    if( stackIdx >= 0 ) {
                        stackIdx--;
                        char stackCh = stack[stackIdx];
 
                        // 꺼낸 괄호가 짝이 아니면 짝이 아님을 리턴
                        if( !isBracketMatch(stackCh,ch) )
                            return false;
                    } else {
                        // Stack에서 꺼낼 왼쪽 괄호가 없음. 짝이 없음을 의미
                        return false;
                    }
                }
                // 괄호 종류가 아니면 무시
            }
            return true;
        }
 
        public static boolean match(char[] cs) {
            return matchUseStack(cs);
        }
 
        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
        }
    }