[IBM Developer Works]초보개발자 코드 트레이닝 Part 2.

Posted 2008/05/16 16:42
저번달 부터 IBM Developer works에 "김승권(http://seal.tistory.com)"님께서 초보 개발자 코드 트레이닝이라는 주제로 글을 연재해주셨다. Part1에서는 Java로 짜여진 샘플 코드를 타 언어로 바꾸는 문제를 내 주셨는데 Interface와 Abstract Class를 사용한 샘플들이 기억에 남는다. 그 때 당시 시간적 여유가 많지 않아 참여하지 못했었는데, 이번에는 빈 Method를 Java를 사용하여 채우는 문제를 내주셔서 JAC를 준비할 겸 Netbeans에서 코딩해보았다.

선물 주신다구 그러셨는데, 책선물 주셨으면 좋겠다^^


문제1. 두 ArrayList의 원소를 모아 하나의 ArrayList를 만드는 both 메소드를 구현하시오.
  - 이 문제는 ArrayList의 clone() method와 addAll() method로 간단히 해결할 수 있었다.

import java.util.*;

public class FirstQuizSet {
    public static ArrayList both(ArrayList xs, ArrayList ys) {
        // TODO : 이곳을 채우는 문제입니다.
        ArrayList bothList = (ArrayList)xs.clone();
        bothList.addAll(ys);
        return bothList;
    }


   
    public static ArrayList either(ArrayList xs, ArrayList ys) {
        ArrayList eitherList = new ArrayList();
        Object y = null;
        Iterator elems = ys.iterator();
       
        while(elems.hasNext()) {
            y = elems.next();
            if(xs.contains(y))
                eitherList.add(y);
        }
        return eitherList;
    }
   
    public static ArrayList toArrayList(int[] xs) {
        ArrayList ys = new ArrayList();
        for(int i=0 ; i<xs.length ; i++)
            ys.add(new Integer(xs[i]));
        return ys;
    }
   
    public static void main(String[] args) {
        int[] xVec = {1,3,4,5,6,9,7};
        int[] yVec = {4,5,8,9,10,15,-1};
       
        ArrayList xs = toArrayList(xVec);
        ArrayList ys = toArrayList(yVec);
        System.out.println(both(xs, ys));
        System.out.println(either(xs, ys));
    }
}



문제2. 정렬된 두 ArrayList간에 공통된 원소를 뽑아 새로운 ArrayList를 만드는 fastEither() method를 구현하시오.
  - 이 문제는 샘플로 적어주신 fastBoth를 살짝 수정해서 구현할 수 있었다. 본래 의도가 샘플 소스를 참고하라는 의도셨으니까.. ㄳ^^;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
import java.util.*;

/**
 *
 * @author Administrator
 */
public class FastEitherQuiz {
   
    public static ArrayList fastEither(ArrayList xList, ArrayList yList) {
        // TODO: 이곳을 채우는 문제입니다.
        ArrayList eitherList = new ArrayList();
       
        final int xSize = xList.size();
        final int ySize = yList.size();
        Comparable x, y;
        int order = 0;
        int xpos = 0;
        int ypos = 0;
       
        while(xpos < xSize && ypos < ySize) {   
            x = (Comparable)xList.get(xpos);
            y = (Comparable)yList.get(ypos);
            order = x.compareTo(y);
           
            if(order == 0) {
                eitherList.add(x);
                ++xpos; ++ypos;
            }
            else if(order < 0) {
                ++xpos;
            }
            else {
                ++ypos;
            }
        }
       
        return eitherList;
    }


    public static ArrayList fastBoth(ArrayList xList, ArrayList yList) {
        ArrayList bothList = new ArrayList();
       
        final int xSize = xList.size();
        final int ySize = yList.size();
        Comparable x, y;
        int order = 0;
        int xpos = 0;
        int ypos = 0;
       
        while(xpos < xSize && ypos < ySize) {   
            x = (Comparable)xList.get(xpos);
            y = (Comparable)yList.get(ypos);
            order = x.compareTo(y);
           
            if(order == 0) {
                bothList.add(x);
                ++xpos; ++ypos;
            }
            else if(order < 0) {
                bothList.add(x);
                ++xpos;
            }
            else {
                bothList.add(y);
                ++ypos;
            }
        }
       
        if(ypos == ySize)
            bothList.addAll(xpos, xList);
        else
            bothList.addAll(ypos, yList);
       
        return bothList;
    }
   
    public static void main(String[] args) {
        int[] xVec = {1, 3, 4, 5, 6, 9, 7};
        int[] yVec = {4, 5, 8, 9, 10, 15, -1};
       
        ArrayList xs = FirstQuizSet.toArrayList(xVec);
        ArrayList ys = FirstQuizSet.toArrayList(yVec);
             
        Collections.sort(xs);
        Collections.sort(ys);
     
        System.out.println(xs); System.out.println(ys);
        System.out.println(fastBoth(xs, ys));
        System.out.println(fastEither(xs, ys));
    }
}



문제3. left에 있는 문자열이 right에 있는 문자열의 부분 문자열인지 확인하는 isSubstring() method를 구현하시오.
  - 경우 1 (문자열의 순서가 유지되어야 하는경우) : String으로 변환 후 indexOf() method를 사용하여 해결하였다.
  - 경우 2 (문자열의 순서가 유지되지 않아도 되는 경우) : 문자열의 순서가 유지되지 않아도 된다면 정렬후 간단하게 해결할 수 있다. 이것도, 전의 소스를 많이 참고했다.


import java.util.*;

public class PatternTest {

    public static boolean isSubstring(char[] left, char[] right) {
        // TODO : 이곳을 채우는 문제입니다.
       
        /* 문자열의 순서가 유지되야 하는경우 */
        String leftString = String.valueOf(left);
        String rightString = String.valueOf(right);
       
        return rightString.indexOf(leftString) > -1;
   
        /* 문자열의 순서가 무시되도 되는경우 */
        /*
        Arrays.sort(left);
        Arrays.sort(right);
       
        final int leftSize = left.length;
        final int rightSize = right.length;
       
        int leftIndex = 0;
        int rightIndex = 0;
       
        while(leftIndex < leftSize && rightIndex < rightSize) {
            if(left[leftIndex] == right[rightIndex]) {
                leftIndex++;
                rightIndex++;
            }
            else if(left[leftIndex] < right[rightIndex]) {
                break;
            }
            else {
                rightIndex++;
            }
        }
        return leftIndex == leftSize;
         */
    }

   
    public static void main(String[] args) {
        char[] first = {'a', 'b', 'c'};
        char[] second = {'a', 'c', 'b', 'c'};
        char[] third = {'a', 'a', 'b', 'c'};
        System.out.println(isSubstring(first, second));
        System.out.println(isSubstring(first, third));
    }
}



문제4. 문자열이 들어있는 배열을 받아 열고 닫는 괄호 문자가 짝이 맞는지 검사하는 match 프로시저를 구현하시오.
  - 4가지 문제중에 가장 어려웠던 문제이다. 일단 '{', '<', '[', '(' 를 괄호로 정의하였고 괄호의 열고 닫힘 확인 뿐만 아니라 전체 괄호의 유효성도 검사하였다. 만약 괄호의 열고닫힘의 순서를 지킬 필요가 없다면 각 괄호의 열기 몇개, 닫기 몇개. 이런식의 개수를 센 후 측정해 놓은 숫자만 비교해보면 된다.
  문제를 어떻게 하면 코딩을 간단하게 할 수 있을지 고민해봤다. 결국 뚜렷하게 나은 방법을 찾지는 못해서 전형적인 방법인 스택을 사용하여 해결하였다.

import java.util.Stack;


public class MatchTest {

    public static boolean match(char[] cs) {
        // TODO : 이곳을 채우는 문제입니다.
       
        Stack opStack = new Stack();
        char charValue;
       
        final int length = cs.length;
        for(int i=0 ; i< length ; i++) {
            if(cs[i] == '{' || cs[i] == '[' || cs[i] == '(' || cs[i] == '<') {
                opStack.push(cs[i]);
            }
            else if(cs[i] == '}' || cs[i] == ']' || cs[i] == ')' || cs[i] == '>') {
                if(opStack.isEmpty())
                    return false;
               
                charValue = (Character)opStack.pop();
               
                if(cs[i] == '}' && charValue != '{') return false;
                else if(cs[i] == ']' && charValue != '[') return false;
                else if(cs[i] == ')' && charValue != '(') return false;
                else if(cs[i] == '>' && charValue != '<') return false;
            }
        }
        return opStack.isEmpty();
    }
   
    public static void main(String[] args) {
        char[] first = { '(', '[', '<', '{', '}', '>', ']', ')'};
        char[] second = { '(', '[', '<', '{', '>', '}', ']', ')'};
        char[] third = { '(', 'a', 'c', ')', '[', '{', '}', ']'};
       
        System.out.println(match(first));
        System.out.println(match(second));
        System.out.println(match(third));
    }
}


이올린에 북마크하기

'C.S.E > Algorithm' 카테고리의 다른 글

[ACM] Problem B. Editor  (0) 2008/07/12
[ACM] 2007 Problem A - Molar mass  (0) 2008/07/09
[IBM Developer Works]초보개발자 코드 트레이닝 Part 2.  (0) 2008/05/16
[UVA] 10198 Counting  (0) 2008/05/06
[UVA] 10099 The Tourist Guide  (0) 2008/05/04
[UVA] 10183 How many Fibs?  (0) 2008/05/02
« PREV : 1 : ... 51 : 52 : 53 : 54 : 55 : 56 : 57 : 58 : 59 : ... 248 : NEXT »