[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로 간단히 해결할 수 있었다.
문제2. 정렬된 두 ArrayList간에 공통된 원소를 뽑아 새로운 ArrayList를 만드는 fastEither() method를 구현하시오.
- 이 문제는 샘플로 적어주신 fastBoth를 살짝 수정해서 구현할 수 있었다. 본래 의도가 샘플 소스를 참고하라는 의도셨으니까.. ㄳ^^;
문제3. left에 있는 문자열이 right에 있는 문자열의 부분 문자열인지 확인하는 isSubstring() method를 구현하시오.
- 경우 1 (문자열의 순서가 유지되어야 하는경우) : String으로 변환 후 indexOf() method를 사용하여 해결하였다.
- 경우 2 (문자열의 순서가 유지되지 않아도 되는 경우) : 문자열의 순서가 유지되지 않아도 된다면 정렬후 간단하게 해결할 수 있다. 이것도, 전의 소스를 많이 참고했다.
import java.util.*;
public class PatternTest {
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가지 문제중에 가장 어려웠던 문제이다. 일단 '{', '<', '[', '(' 를 괄호로 정의하였고 괄호의 열고 닫힘 확인 뿐만 아니라 전체 괄호의 유효성도 검사하였다. 만약 괄호의 열고닫힘의 순서를 지킬 필요가 없다면 각 괄호의 열기 몇개, 닫기 몇개. 이런식의 개수를 센 후 측정해 놓은 숫자만 비교해보면 된다.
문제를 어떻게 하면 코딩을 간단하게 할 수 있을지 고민해봤다. 결국 뚜렷하게 나은 방법을 찾지는 못해서 전형적인 방법인 스택을 사용하여 해결하였다.
선물 주신다구 그러셨는데, 책선물 주셨으면 좋겠다^^
문제1. 두 ArrayList의 원소를 모아 하나의 ArrayList를 만드는 both 메소드를 구현하시오.
- 이 문제는 ArrayList의 clone() method와 addAll() method로 간단히 해결할 수 있었다.
import java.util.*;
public class FirstQuizSet {
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));
}
}
public class FirstQuizSet {
public static ArrayList both(ArrayList xs, ArrayList ys) {
// TODO : 이곳을 채우는 문제입니다.
ArrayList bothList = (ArrayList)xs.clone();
bothList.addAll(ys);
return bothList;
}
// 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 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));
}
}
* 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;
}
// 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;
*/
}
// 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 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));
}
}
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();
}
// 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 |
- Filed under : C.S.E/Algorithm
- Tag : Algorithm, IBM Developer works
- Comment Trackback
