SUPPORT

Thebee Calendar

≫ SUPPORT ≫ 개발 스터디

chapter 03. 배열

진기원 1 Comment 2015년 4월 16일 149 (3)

개발 스터디 ≫ 2015 상반기 자바스터디 ≫ chapter 03. 배열

3.1 Java의 배열

배열 : 객체이며, t[]형태, t는 배열의 원소 타입.

ex) 원소 타입이 프리미티브인 int이면 배열 타입은 int[]

배열의 원소 타입 – 프리미티브, 클래스, 인터페이스, 배열 모두 가능

ex) int[] a //원소는 프리미티브 타입 int

String[] args //원소는 객체 타입 String

List[] lists; //원소는 인터페이스 타입 List

double[][] matrix //원소는 배열 타입 double[]

1) 배열의 선언과 초기화, 값 할당

new 연산자 : 배열 – 메모리 할당, []안의 수만큼 메모리 할당, 원소타입이 프리미티브 일때 해당 타입의 0값으로 초기화

비배열 – 클래스 생성자 호출

public static void main(String[] args) {

	int[] a = {1,2,3}; 	                //1)선언+초기화+값 할당(초기화 리스트(Initialization list)
	System.out.println("a[1]: "+a[1]);

	int[] b;	                          //2)선언 - 원소가 프리미티브타입 int인 배열로 객체 b선언
	b= new int[3];		                //초기화 - new연산자로 메모리 할당(객체 b 생성), 배열의 크기는 3
	b[1] = 99;		                    //값 할당
	System.out.println("b[0]: "+b[0]);		
	System.out.println("b[1]: "+b[1]);		

	int[] c;                               //3)선언
	c = new int[]{4,5,6};                  //초기화 + 값할당
	////new int[]{4,5,6}; 익명배열(anonymous array)
	System.out.println("c[1]: "+c[1]);	
}

public static void main(String[] args) {

int[] a = {1,2,3}; //1)선언+초기화+값 할당(초기화 리스트(Initialization list)

System.out.println("a[1]: "+a[1]);

int[] b; //2)선언 - 원소가 프리미티브타입 int인 배열로 객체 b선언

b= new int[3]; //초기화 - new연산자로 메모리 할당(객체 b 생성), 배열의 크기는 3

b[1] = 99; //값 할당

System.out.println("b[0]: "+b[0]);

System.out.println("b[1]: "+b[1]);

int[] c; //3)선언

c = new int[]{4,5,6}; //초기화 + 값할당

////new int[]{4,5,6}; 익명배열(anonymous array)

System.out.println("c[1]: "+c[1]);

}

배열의 크기 : a.length

ArrayIndexOutOfBoundsException : 배열의 크기 a를 벗어나면 예외처리

public static void main(String[] args) {						
   try{						
      int value;						
      int array[] = {6, 16, 26,36,46,56,66,76};						
     int index = 8;						
      value = array[index];   // <-- 여기서 발생						
      System.out.println("Execution does not reach here if there is a invalid index.");						
   }catch(ArrayIndexOutOfBoundsException e){						
      System.out.println( "Valid indexes are 0, 1,2,3, 4,5,6 or 7" );						
   }						
 }

public static void main(String[] args) {

try{

int value;

int array[] = {6, 16, 26,36,46,56,66,76};

int index = 8;

value = array[index]; // <-- 여기서 발생

System.out.println("Execution does not reach here if there is a invalid index.");

}catch(ArrayIndexOutOfBoundsException e){

System.out.println( "Valid indexes are 0, 1,2,3, 4,5,6 or 7" );

}

java에서 배열의 특성

1) 다른 객체와 마찬가지로 배열도 그에 대한 여러개의 참조를 가질 수 있다.

int[] aa = a;

2) 메소드의 매개변수 리스트에 배열 매개변수를 선언할 수 있다.

public void print(int[] a)

3) 배열은 이름만 이용해서 메소드로 전달된다.

print(a);

4) 배열 타입은 메소드에 대한 리턴 타입이 될 수 있다.

public int[] randomArray(int n)

5) 배열을 다른 배열에 할당해도 실제로 복사되는 것이 아니라, 다른 이름(참조)만 부여하게 된다.

b = a; //a[]와 b[]는 동일 배열이 됨

6) 배열을 복사하려면, System 클래스에 정의된 arraycopy() 메소드를 이용할 수 있다.

System.arraycopy(a, 0, b, 0, a.length);

7) 중복 배열을 생성하려면, Object 클래스에 정의된 clone() 메소드를 이용할 수 있다.

b= (int[])a.clone(); //clone()에 대한 리턴 타입이 Object이므로, 타입을 배열로 변환해야 함

8) 배열은 대개 for루프를 이용해서 처리된다.

for(int i = 0; i < a.length; i++)

a[i] = random.netxInt(1000);

9) 배열이 final로 선언되면 그 참조는 재할당될 수 없다.

final int[] a = {22,44, 66,88};

a[3] = 99; //ok

a = new int[8] //불법임

10) 메모리 할당 참조

[리스팅3.1] 배열의 테스팅

public class Main {
    private static java.util.Random random = new java.util.Random();

    public static void main(String[] args) {
        int[] a = randomInts(10,1000);
        int[] aa = (int[])a.clone();  // creates a duplicate of a in aa
        print(a);
        print(aa);
        a[0] = a[1] = a[2] = 888;
        print(a);
        print(aa);
    }

    public static int[] randomInts(int n, int range) {
        int[] a = new int[n];
        for (int i=0; i<n; i++)
            a[i] = random.nextInt(range);
        return a;
    }

    public static void print(int[] a) {
        System.out.print("{"+a[0]);
        for (int i=1; i<a.length; i++)
            System.out.print(","+a[i]);
        System.out.println("}");
    }
}

public class Main {

private static java.util.Random random = new java.util.Random();

public static void main(String[] args) {

int[] a = randomInts(10,1000);

int[] aa = (int[])a.clone(); // creates a duplicate of a in aa

print(a);

print(aa);

a[0] = a[1] = a[2] = 888;

print(a);

print(aa);

}

public static int[] randomInts(int n, int range) {

int[] a = new int[n];

for (int i=0; i<n; i++)

a[i] = random.nextInt(range);

return a;

}

public static void print(int[] a) {

System.out.print("{"+a[0]);

for (int i=1; i<a.length; i++)

System.out.print(","+a[i]);

System.out.println("}");

}

3.2 Java에서 배열의 프린팅

배열의 이름 : 배열에 대한 참조 변수의 이름

메모리(Stack)에서 배열의 시작주소를 저장, 16진수

예) [I@73d6a5

[ : 배열 I : int @ : at 73d6a5 : 배열 첫번째 바이트의 16진수 주소. 0x73d6a5

질문 : [리스팅 3.2]배열의 크기가 7이고, int는 4byte를 차지하는데 왜 56byte를 메모리에서 갖나?

ox73d6a5 + 0×37 = ox73d6dd(십진수 7,591,589 ~ 7,591,645)

[리스팅3.2] 배열 참조의 프린팅

public class Print {
    public static void main(String[] args) {
        int[] a = {66, 33, 99, 88, 44, 55, 22};
        System.out.println(a);
    }
}

public class Print {

public static void main(String[] args) {

int[] a = {66, 33, 99, 88, 44, 55, 22};

System.out.println(a);

}

3.3 간단한 배열 알고리즘

알고리즘 3.1 – 최대값 원소

입력 : 비교가능한 원소들의 시퀀스{a1, a2….. , an-1}

출력 : 인덱스 값 m

후조건 : 모든 i에 대해 am >= ai

public static void main(String[] args) {
    int[] a = {66, 33, 99, 88, 44, 55, 22};

    int max_i;
    max_i = max(a);

    System.out.println(max_i);
}

static int max(int[] x){
	int m = 0;

    for (int i = 0; i < x.length; i++){
    	if (x[i] > x[m]){
    		m = i;		    	
    	}
    }      
 	return m;        	
}

public static void main(String[] args) {

int[] a = {66, 33, 99, 88, 44, 55, 22};

int max_i;

max_i = max(a);

System.out.println(max_i);

}

static int max(int[] x){

int m = 0;

for (int i = 0; i < x.length; i++){

if (x[i] > x[m]){

m = i;

}

return m;

}

알고리즘 3.2 – swap

[리스팅3.3] swap() 메소드

void swap(int[] a, int i, int j) {
    int ai = a[i], aj = a[j];
    if (ai == aj) return;
    a[i] = aj;
    a[j] = ai;
}

void swap(int[] a, int i, int j) {

int ai = a[i], aj = a[j];

if (ai == aj) return;

a[i] = aj;

a[j] = ai;

}

3.4 객체의 배열

배열의 타입이 프리미티브라면 모든 원소는 동일 타입이어야 함.

원소 타입이 참조라면 선언된 원소 타입의 확장에 속하기만 하면 됨. -> 이질배열(heterogeneus array)

[리스팅3.4] 객체의 이질 배열

public class ObjectArray {
  public static void main(String[] args) {
    String s="Mercury";
    Float x = new Float(3.14159);
    java.util.Date d = new java.util.Date();
    int[] a = new int[] {11, 33, 55, 77, 99};
    Object[] objects = {s, x, d, a};
    print(objects);
  }

  static void print(Object[] a) {
    System.out.print("{" + a[0]);
    for (int i=1; i<a.length; i++)
      System.out.print("," + a[i]);
    System.out.println("}");
    if (a[0] instanceof String)
      System.out.println(((String)a[0]).charAt(6));
    if (a[1] instanceof Float)
      System.out.println(((Float)a[1]).isNaN());
    if (a[2] instanceof java.util.Date)
      System.out.println(((java.util.Date)a[2]).getTime());
    if (a[3] instanceof int[])
      System.out.println(((int[])a[3]).length);
  }
}

public class ObjectArray {

public static void main(String[] args) {

String s="Mercury";

Float x = new Float(3.14159);

java.util.Date d = new java.util.Date();

int[] a = new int[] {11, 33, 55, 77, 99};

Object[] objects = {s, x, d, a};

print(objects);

}

static void print(Object[] a) {

System.out.print("{" + a[0]);

for (int i=1; i<a.length; i++)

System.out.print("," + a[i]);

System.out.println("}");

if (a[0] instanceof String)

System.out.println(((String)a[0]).charAt(6));

if (a[1] instanceof Float)

System.out.println(((Float)a[1]).isNaN());

if (a[2] instanceof java.util.Date)

System.out.println(((java.util.Date)a[2]).getTime());

if (a[3] instanceof int[])

System.out.println(((int[])a[3]).length);

}

3.5 순차 탐색

알고리즘 3.3 순차탐색

입력 : 시퀀스{a0, a1, a2…. an-1}, 목표 값 x

출력 : 인덱스 값 i

후조건 : ai = x 또는 모든 aj≠x 일 때 i = -n

복잡도 : Θ(n), 실행시간이 리스트의 길이 n에 비례한다. 크기가 2배 증가하면 실행시간도 2배 증가

[리스팅3.5] 순차탐색

public class TestSequentialSearch {

  public static void main(String[] args) {
    int[] a = {66,44,99,33,55,22,88,77};
    print(a);
    System.out.println("search(a," + 55 + "): " + search(a,55));
    System.out.println("search(a," + 50 + "): " + search(a,50));
  }

    public static void print(int[] a) {
        System.out.print("{"+a[0]);
        for (int i=1; i<a.length; i++)
            System.out.print(","+a[i]);
        System.out.println("}");
    }

   static int search(int[] a, int target) {
    for (int i=0; i<a.length; i++)
      if (a[i]==target) return i;
    return -a.length;
  }
}

public class TestSequentialSearch {

public static void main(String[] args) {

int[] a = {66,44,99,33,55,22,88,77};

print(a);

System.out.println("search(a," + 55 + "): " + search(a,55));

System.out.println("search(a," + 50 + "): " + search(a,50));

}

public static void print(int[] a) {

System.out.print("{"+a[0]);

for (int i=1; i<a.length; i++)

System.out.print(","+a[i]);

System.out.println("}");

}

static int search(int[] a, int target) {

for (int i=0; i<a.length; i++)

if (a[i]==target) return i;

return -a.length;

}

3.6 복잡도 분석

3.7 이진 탐색

알고리즘 3.4 – 이진탐색

입력 : 시퀀스{a0, a1, a2….. An-1} 와 목표값 x

출력 : index 값 i

선조건 :시퀀스는 정렬되어 있음, 즉 a0<= a1<=….. an-1

후조건 : ai = x; 또는 모든 j<p에 대해서 aj<x이고 모든 j>=p에 대해서 aj>x일 때 i = -p-1

1. p= 0, q= n-1로 놓음
2. p<=q 이면 단계 2-5수행
3. I = (p+q)/2로 놓음
4. ai = x이면 i리턴
5. aj<x이면, p= i+1로 놓음, 그렇지 않으면 q= i-1로 놓음

[리스팅3.6] 이진 탐색

public class TestBinarySearch {

  public static void main(String[] args) {
    int[] a = {22, 33, 44, 55, 66, 77, 88, 99};
    System.out.println("search(a," + 55 + "): " + search(a, 55));
    System.out.println("search(a," + 50 + "): " + search(a, 50));
  }

  static int search(int[] a, int x) {
    int p = 0, q = a.length-1;
    while (p <= q) {           // search the segment a[p..q]
      int i = (p+q)/2;         // index of element in the middle
      if (a[i] == x) return i;
      if (a[i] < x) p = i+1;   // search upper half
      else q = i-1;            // search lower half 
    }
    return -p-1;               // not found 
  }
}

public class TestBinarySearch {

public static void main(String[] args) {

int[] a = {22, 33, 44, 55, 66, 77, 88, 99};

System.out.println("search(a," + 55 + "): " + search(a, 55));

System.out.println("search(a," + 50 + "): " + search(a, 50));

}

static int search(int[] a, int x) {

int p = 0, q = a.length-1;

while (p <= q) { // search the segment a[p..q]

int i = (p+q)/2; // index of element in the middle

if (a[i] == x) return i;

if (a[i] < x) p = i+1; // search upper half

else q = i-1; // search lower half

}

return -p-1; // not found

}

복잡도 : Θ(lg n), 1,000개의 원소 배열을 탐색하는데 3ms가 소요되었다면 1,000,000일 때는 6m가 걸린다.

3.8 java.util.Arrays 클래스

https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html

[리스팅3.7] java.util.Arrays 클래스의 사용

public class TestJavaUtilArrays {

  public static void main(String[] args) {
    int[] a = {77, 44, 55, 22, 99, 66, 33, 88}; 
    print(a);
    java.util.Arrays.sort(a);
    print(a);
    test(a,55);
    test(a,60);
    test(a,88);
    test(a,90);
  }
  static void test(int[] array, int target) {
    int i = java.util.Arrays.binarySearch(array,target);
    System.out.print("target="+target+", i="+i);
    if (i >= 0) System.out.println("\ta[" + i + "]=" + array[i]);
    else System.out.println("\tInsert " + target+" at a["+(-i-1)+"]");
  }

  static void print(int[] a) {
        System.out.print("{"+a[0]);
        for (int i=1; i<a.length; i++)
            System.out.print(","+a[i]);
        System.out.println("}");
  }
}

public class TestJavaUtilArrays {

public static void main(String[] args) {

int[] a = {77, 44, 55, 22, 99, 66, 33, 88};

print(a);

java.util.Arrays.sort(a);

print(a);

test(a,55);

test(a,60);

test(a,88);

test(a,90);

}

static void test(int[] array, int target) {

int i = java.util.Arrays.binarySearch(array,target);

System.out.print("target="+target+", i="+i);

if (i >= 0) System.out.println("\ta[" + i + "]=" + array[i]);

else System.out.println("\tInsert " + target+" at a["+(-i-1)+"]");

}

static void print(int[] a) {

System.out.print("{"+a[0]);

for (int i=1; i<a.length; i++)

System.out.print(","+a[i]);

System.out.println("}");

}

3.9 사용자정의 IntArrays 클래스

System.arraycopy(a, m , aa, mm, k)

a[] : 소스 배열 aa[] : 목표 배열 m: a[]의 시작 인덱스 mm: aa[]의 시작인덱스 k: 복사할 원소의 수

{a[m], …, a[m+k-1]}를 {aa[mm], … , aa[mm+k-1]}의 위치로 복사

    public static void main(String[] args) {
        int[] a = {1,2,3,4,5, 6, 7, 8};
        print(a);        
        System.arraycopy(a, 2, a, 4, 2);
        print(a);      
    }    

    public static void print(int[] a) {
        System.out.print("{"+a[0]);
        for (int i=1; i<a.length; i++)
            System.out.print(","+a[i]);
        System.out.println("}");
    }

public static void main(String[] args) {

int[] a = {1,2,3,4,5, 6, 7, 8};

print(a);

System.arraycopy(a, 2, a, 4, 2);

print(a);

}

public static void print(int[] a) {

System.out.print("{"+a[0]);

for (int i=1; i<a.length; i++)

System.out.print(","+a[i]);

System.out.println("}");

}

[리스팅3.8] 사용자 정의 유틸리티 IntArrays클래스

public class IntArrays {
    private static java.util.Random random = new java.util.Random();

    /**
     * Determines whether the specified array is in ascending order.
     * 
     * @param  a the array.
     * @return true if a[] is in ascending order, otherwise false.
     */
    public static boolean isSorted(int[] a) {
        for (int i=1; i<a.length; i++)
            if (a[i] < a[i-1]) return false;
        return true;
    }

    /**
     * Prints all the elements in the specified array.
     * 
     * @param  a the array.
     */
    public static void print(int[] a) {
        System.out.print("{"+a[0]);
        for (int i=1; i<a.length; i++)
            System.out.print(","+a[i]);
        System.out.println("}");
    }

    /**
     * Returns a new array of n random integers. If range>0, then
     * the elements will be uniformly distributed in the range
     * 0 <= a[i] < range; otherwise, they will range over all int
     * values.
     * 
     * @param  n the length of the new array.
     * @param  range determines the range of the element values.
     * @throws IllegalArgumentException.
     * @return the new array.
     */
    public static int[] randomInts(int n, int range) {
        int[] a = new int[n];
        if (n<2) throw new IllegalArgumentException();
        for (int i=0; i<n; i++)
            a[i] = random.nextInt(range);
        return a;
    }

    /**
     * Returns a new array of size n that contains the elements of
     * the specified array a and 0s thereafter.
     * 
     * @param  a the array to be copied.
     * @param  n the length of the new array.
     * @throws IllegalArgumentException.
     * @return the new array.
     */
    public static int[] resize(int[] a, int n) {
        if (n<a.length) throw new IllegalArgumentException();
        int[] aa = new int[n];
        System.arraycopy(a,0,aa,0,a.length);
        return aa;
    }

    /**
     * Interchanges element i with element j in the specified array.
     * 
     * @param  a the array.
     * @param  i index of one element.
     * @param  j index of the other element.
     */
     public static void swap(int[] a, int i, int j) {
        int ai = a[i], aj = a[j];
        if (ai==aj) return;
        a[i] = aj;
        a[j] = ai;
    }
}

public class IntArrays {

private static java.util.Random random = new java.util.Random();

/**

* Determines whether the specified array is in ascending order.

* @param a the array.

* @return true if a[] is in ascending order, otherwise false.

public static boolean isSorted(int[] a) {

for (int i=1; i<a.length; i++)

if (a[i] < a[i-1]) return false;

return true;

}

/**

* Prints all the elements in the specified array.

* @param a the array.

public static void print(int[] a) {

System.out.print("{"+a[0]);

for (int i=1; i<a.length; i++)

System.out.print(","+a[i]);

System.out.println("}");

}

/**

* Returns a new array of n random integers. If range>0, then

* the elements will be uniformly distributed in the range

* 0 <= a[i] < range; otherwise, they will range over all int

* values.

* @param n the length of the new array.

* @param range determines the range of the element values.

* @throws IllegalArgumentException.

* @return the new array.

public static int[] randomInts(int n, int range) {

int[] a = new int[n];

if (n<2) throw new IllegalArgumentException();

for (int i=0; i<n; i++)

a[i] = random.nextInt(range);

return a;

}

/**

* Returns a new array of size n that contains the elements of

* the specified array a and 0s thereafter.

* @param a the array to be copied.

* @param n the length of the new array.

* @throws IllegalArgumentException.

* @return the new array.

public static int[] resize(int[] a, int n) {

if (n<a.length) throw new IllegalArgumentException();

int[] aa = new int[n];

System.arraycopy(a,0,aa,0,a.length);

return aa;

}

/**

* Interchanges element i with element j in the specified array.

* @param a the array.

* @param i index of one element.

* @param j index of the other element.

public static void swap(int[] a, int i, int j) {

int ai = a[i], aj = a[j];

if (ai==aj) return;

a[i] = aj;

a[j] = ai;

}

3.10 java.util.Vector클래스

버전 1.1에서 java.util패키지에 Vector클랙스를 도입. 이후 java.util.ArrayList클래스에 의해 데체.

크기조정가능 배열(resizable array) : 동일 원소를 포함하는 더 큰 배열로 대체되고, 기본적으로 2배의 길이를 갖는다.

public static void main(String[] args) {
    int[] a = {1,2,3,4,5, 6, 7, 8};
    print(a);        

    int n = a.length;
    int[] aa = new int[2*n];
    print(aa);  
    System.arraycopy(a, 0, aa, 0, n);
    print(aa);   
}

public static void main(String[] args) {

int[] a = {1,2,3,4,5, 6, 7, 8};

print(a);

int n = a.length;

int[] aa = new int[2*n];

print(aa);

System.arraycopy(a, 0, aa, 0, n);

print(aa);

}

[리스팅3.9] 정수 배열의 크기 조정

  int resize(int[] a) {
    int n = a.length;
    int[] aa = new int[2*n]
    System.arraycopy(a, 0, aa, 0, n);
    return aa;
  }

int resize(int[] a) {

int n = a.length;

int[] aa = new int[2*n]

System.arraycopy(a, 0, aa, 0, n);

return aa;

}

[리스팅3.10] java.util.Vector클래스의 단순화된 버전

Vector객체는 지원배열(backing array)이라고 하는 자신의 고유한 protected Object[] 배열 안에 Object참조들의 시퀀스를 유지한다.

line 2 : 지원 배열 선언

line 3 : 실제로 저장된 객체의 수를 추적, 초기값 0

line 4 : (지원배열의) 용량 10으로 정의

line 6 : 지원배열을 capacity만큼 할당

line 11 : 초기값의 지원배열을 할당하기 위해 line6을 호출

line 15 : size()는 size필드 접근자 메소드

line 21~26 : 리스팅3.9의 지역버전. 객체를 사용하고 Objects에 할당.

public class Vector {
  protected Object[] objects;       // backing array
  protected int size;               // actual number of Objects stored
  protected static final int CAPACITY=10;  // default array length

  public Vector(int capacity) {
    if (capacity<=0) throw new IllegalArgumentException("capacity<=0");
    objects = new Object[capacity];
  }

  public Vector() {
    this(CAPACITY);
  }

  public int size() {
    return size;
  }

  //...

  protected void resize() {
    int n=objects.length;
    Object[] temp = new Object[2*n];
    System.arraycopy(objects, 0, temp, 0, n);
    objects = temp;
  }
}

public class Vector {

protected Object[] objects; // backing array

protected int size; // actual number of Objects stored

protected static final int CAPACITY=10; // default array length

public Vector(int capacity) {

if (capacity<=0) throw new IllegalArgumentException("capacity<=0");

objects = new Object[capacity];

}

public Vector() {

this(CAPACITY);

}

public int size() {

return size;

}

//...

protected void resize() {

int n=objects.length;

Object[] temp = new Object[2*n];

System.arraycopy(objects, 0, temp, 0, n);

objects = temp;

}

[리스팅3.11] Vector 클래스를 위한 toString() 메소드

line 19~25 : 벡터의 모든 객체를 보여주는 문자열을 return.

public class Vector {
  protected Object[] objects;       // backing array
  protected int size;               // actual number of Objects stored
  protected static final int CAPACITY=10;  // default array length

  public Vector(int capacity) {
    if (capacity<=0) throw new IllegalArgumentException("capacity<=0");
    objects = new Object[capacity];
  }

  public Vector() {
    this(CAPACITY);
  }

  public int size() {
    return size;
  }

  public String toString() {
    if (size == 0) return "()";
    StringBuffer buf = new StringBuffer("(" + objects[0]);
    for (int i = 1; i < size; i++)
      buf.append("," + objects[i]);
    return buf + ")";
  }

  //...

  protected void resize() {
    int n=objects.length;
    Object[] temp = new Object[2*n];
    System.arraycopy(objects, 0, temp, 0, n);
    objects = temp;
  }
}

public class Vector {

protected Object[] objects; // backing array

protected int size; // actual number of Objects stored

protected static final int CAPACITY=10; // default array length

public Vector(int capacity) {

if (capacity<=0) throw new IllegalArgumentException("capacity<=0");

objects = new Object[capacity];

}

public Vector() {

this(CAPACITY);

}

public int size() {

return size;

}

public String toString() {

if (size == 0) return "()";

StringBuffer buf = new StringBuffer("(" + objects[0]);

for (int i = 1; i < size; i++)

buf.append("," + objects[i]);

return buf + ")";

}

//...

protected void resize() {

int n=objects.length;

Object[] temp = new Object[2*n];

System.arraycopy(objects, 0, temp, 0, n);

objects = temp;

}

[리스팅3.12] 배열을 적재하는 생성자

line 15~20

public class Vector {
	  protected Object[] objects;       // backing array
	  protected int size;               // actual number of Objects stored
	  protected static final int CAPACITY=10;  // default array length

	  public Vector(int capacity) {
	    if (capacity<=0) throw new IllegalArgumentException("capacity<=0");
	    objects = new Object[capacity];
	  }

	  public Vector() {
	    this(CAPACITY);
	  }

	  public Vector(Object[] a) {
	    int n = a.length;
	    objects = new Object[2*n];
	    System.arraycopy(a,0,objects,0,n);
	    size = n;
	  }

	  public int size() {
	    return size;
	  }

	  public String toString() {
	    if (size == 0) return "()";
	    StringBuffer buf = new StringBuffer("(" + objects[0]);
	    for (int i = 1; i < size; i++)
	      buf.append("," + objects[i]);
	    return buf + ")";
	  }

	  //...

	  protected void resize() {
	    int n=objects.length;
	    Object[] temp = new Object[2*n];
	    System.arraycopy(objects, 0, temp, 0, n);
	    objects = temp;
	  }
}

public class Vector {

protected Object[] objects; // backing array

protected int size; // actual number of Objects stored

protected static final int CAPACITY=10; // default array length

public Vector(int capacity) {

if (capacity<=0) throw new IllegalArgumentException("capacity<=0");

objects = new Object[capacity];

}

public Vector() {

this(CAPACITY);

}

public Vector(Object[] a) {

int n = a.length;

objects = new Object[2*n];

System.arraycopy(a,0,objects,0,n);

size = n;

}

public int size() {

return size;

}

public String toString() {

if (size == 0) return "()";

StringBuffer buf = new StringBuffer("(" + objects[0]);

for (int i = 1; i < size; i++)

buf.append("," + objects[i]);

return buf + ")";

}

//...

protected void resize() {

int n=objects.length;

Object[] temp = new Object[2*n];

System.arraycopy(objects, 0, temp, 0, n);

objects = temp;

}

[리스팅3.13] Vector 클래스의 테스팅

public class TestVector {
  public static void main(String[] args) {
    Vector v = new Vector(args);
    System.out.println(v);
  }
}

/*  Output:
(alpha,beta,gamma,delta,epsilon)
*/

public class TestVector {

public static void main(String[] args) {

Vector v = new Vector(args);

System.out.println(v);

}

/* Output:

(alpha,beta,gamma,delta,epsilon)

3.11 다차원 배열

2차원 배열 : 배열의 원소는 1차원배열 타입

[리스팅3.14] 2차원 배열의 사용

public class TwoDimensionalArrays {
  public static void main(String[] args) {
    int[][] a = new int[3][];        // an array of 3 sub-arrays (rows)
    a[0] = new int[]{22,44,66,88};   // the first row
    a[2] = new int[]{33,77};         // the third row
    System.out.println("a: " + a + "\na.length: " + a.length);
    IntArrays.print(a[0]);
    IntArrays.print(a[2]);
    System.out.println("a[2].length: " + a[2].length);
    int [][] b = { { 22,44,66,88 },    // the first row of b
                   {  0, 0, 0, 0 },    // the second row of b
                   { 33,55,77, 0 } };  // the third row of b
    System.out.println("b: " + b + "\nb.length: " + b.length);
    IntArrays.print(b[0]);
    IntArrays.print(b[2]);
    System.out.println("b[2].length: " + b[2].length);
  }
}

public class TwoDimensionalArrays {

public static void main(String[] args) {

int[][] a = new int[3][]; // an array of 3 sub-arrays (rows)

a[0] = new int[]{22,44,66,88}; // the first row

a[2] = new int[]{33,77}; // the third row

System.out.println("a: " + a + "\na.length: " + a.length);

IntArrays.print(a[0]);

IntArrays.print(a[2]);

System.out.println("a[2].length: " + a[2].length);

int [][] b = { { 22,44,66,88 }, // the first row of b

{ 0, 0, 0, 0 }, // the second row of b

{ 33,55,77, 0 } }; // the third row of b

System.out.println("b: " + b + "\nb.length: " + b.length);

IntArrays.print(b[0]);

IntArrays.print(b[2]);

System.out.println("b[2].length: " + b[2].length);

}

울퉁불퉁 배열(ragged array)

[리스팅3.15] 파스칼의 삼각형

삼각형 내부의 수는 바로위와 왼쪽 상단의 수의 합.

public class PascalsTriangle {
  public static void main(String[] args) {
    int rows = Integer.parseInt(args[0]);
    int[][] a = init(rows);
    print(a);
  }

  static int[][] init(int n) {
    int[][] a = new int[n][n];
    for (int i = 0; i < n; i++)
      for (int j = 0; j <= i; j++)
        if (j == 0 || j == i) a[i][j] = 1;
        else a[i][j] = a[i-1][j-1] + a[i-1][j];
 	  return a;
  }

  static void print(int[][] a) {
    for (int i = 0; i < a.length; i++) {
      for (int j = 0; j <= i; j++)
        print(a[i][j],5);
      System.out.println();
    }
  }

  static void print(int n, int w) {
    // prints n right-justified in a field on width w: 
    String s = "" + n, blanks = "                    ";
    int len = s.length();
    System.out.print(blanks.substring(0, w-len) + s);
  }
}

public class PascalsTriangle {

public static void main(String[] args) {

int rows = Integer.parseInt(args[0]);

int[][] a = init(rows);

print(a);

}

static int[][] init(int n) {

int[][] a = new int[n][n];

for (int i = 0; i < n; i++)

for (int j = 0; j <= i; j++)

if (j == 0 || j == i) a[i][j] = 1;

else a[i][j] = a[i-1][j-1] + a[i-1][j];

return a;

}

static void print(int[][] a) {

for (int i = 0; i < a.length; i++) {

for (int j = 0; j <= i; j++)

print(a[i][j],5);

System.out.println();

}

static void print(int n, int w) {

// prints n right-justified in a field on width w:

String s = "" + n, blanks = " ";

int len = s.length();

System.out.print(blanks.substring(0, w-len) + s);

}

3.12 사례연구 : 용어 색인의 구축

문서에 있는 모든 단어에 대한 인덱스. 단어와 라인의 번호로 구성.

ADT : Map

한 Map은 항목의 컬렉션으로, 각 항목은(키, 값) 쌍이다. 키 필드는 유일하고 불변해야 한다.

String get(String key) – 조사연산

리턴 : 주어진 키에 대한 현재 값, 또는 발견하지 못하면 null

후조건 : 이 맵은 변경되지 않음

String Put(String key, String value)

리턴 : 주어진 키에 대한 옛날 값, 또는 발견하지 못하면 null

후조건 : 항목 쌍(키, 값)이 맵에 조재함.

int size()

리턴 : 맵의 항목 쌍의 수

후조건 : 이 맵은 변경되지 않음

String toSting()

리턴 : 전체 컬렉션의 문자열 표현

후조건 : 이 맵은 변경되지 않음

[리스팅3.16] Map 인터페이스

Map 인터페이스를 구현하는 클래스의 이름은 ArrayMap.

단어를 key필드에, 라인번호 리스트를 value필드에 저장하는 Entry객체.

중첩 클래스 (nested class) : Entry 클래스의 멘버들이 ArrayMap 클래스 내부에서만 관련이 되므로, Entry클래스를 ArrayMap 클래스의 멤버가 되도록 정의.

public interface Map {
    public String get(String key);
    public String put(String key, String value);
    public int size();
    public String toString();
}

public interface Map {

public String get(String key);

public String put(String key, String value);

public int size();

public String toString();

}

[리스팅3.17] ArrayMap 클래스

public class ArrayMap implements Map {
  private static final int INITIAL_LENGTH=10;
  private Entry[] a = new Entry[INITIAL_LENGTH];
  private int size;

  public String get(String key) {
    for (int i=0; i<size; i++)
      if (a[i].key.equals(key)) return a[i].value;
    return null;
  }

  public String put(String key, String value) {
    for (int i=0; i<size; i++)
      if (a[i].key.equals(key)) return a[i].setValue(value);
    if (size==a.length) resize();
    a[size++] = new Entry(key,value);
    return null;
  }

  private void resize() {
    Entry[] aa = new Entry[2*a.length];
    System.arraycopy(a,0,aa,0,a.length);
    a = aa;
  }

  public int size() {
    return size;
  }

  public String toString() {
    StringBuffer buf = new StringBuffer();
    for (int i=0; i<size; i++)
      buf.append(a[i] + "\n");
    return buf.toString();
  }

  private static class Entry {
    String key, value;

    public Entry(String key, String value) {
      this.key = key;
      this.value = value;
    }

    public String setValue(String value) {
      String oldValue = this.value;
      this.value = value;
      return oldValue;
    }

    public String toString() {
      return key + ": " + value;
    }
  }
}

public class ArrayMap implements Map {

private static final int INITIAL_LENGTH=10;

private Entry[] a = new Entry[INITIAL_LENGTH];

private int size;

public String get(String key) {

for (int i=0; i<size; i++)

if (a[i].key.equals(key)) return a[i].value;

return null;

}

public String put(String key, String value) {

for (int i=0; i<size; i++)

if (a[i].key.equals(key)) return a[i].setValue(value);

if (size==a.length) resize();

a[size++] = new Entry(key,value);

return null;

}

private void resize() {

Entry[] aa = new Entry[2*a.length];

System.arraycopy(a,0,aa,0,a.length);

a = aa;

}

public int size() {

return size;

}

public String toString() {

StringBuffer buf = new StringBuffer();

for (int i=0; i<size; i++)

buf.append(a[i] + "\n");

return buf.toString();

}

private static class Entry {

String key, value;

public Entry(String key, String value) {

this.key = key;

this.value = value;

}

public String setValue(String value) {

String oldValue = this.value;

this.value = value;

return oldValue;

}

public String toString() {

return key + ": " + value;

}

[리스팅3.18] ArrayMap 클래스의 테스팅

new Main(args[0]); 의 arg[0]을 실제 파일명을 입력해서 테스트.

public class Main {

  public Main(String file) {
    Map map = new ArrayMap();
    int lineNumber = 0;
    try {
      BufferedReader in = new BufferedReader(new FileReader(file));
      String line = in.readLine();
      while(line!=null) {
        ++lineNumber;
        StringTokenizer parser = new StringTokenizer(line," ,:;-.?!");
        while (parser.hasMoreTokens()) {
          String word = parser.nextToken().toUpperCase();
          String list = map.get(word);
          if (list==null) map.put(word,""+lineNumber);
          else map.put(word,list+","+lineNumber);
        }
        System.out.println(lineNumber + ":\t" + line);
        line = in.readLine();
      }
      in.close();
    } catch(IOException e) { System.out.println(e); }
    System.out.println(map);
    System.out.println("lines: " + lineNumber);
    System.out.println("distinct words: " + map.size());
  }

  public static void main(String[] args) {
    new Main(args[0]);
  }
}

public class Main {

public Main(String file) {

Map map = new ArrayMap();

int lineNumber = 0;

try {

BufferedReader in = new BufferedReader(new FileReader(file));

String line = in.readLine();

while(line!=null) {

++lineNumber;

StringTokenizer parser = new StringTokenizer(line," ,:;-.?!");

while (parser.hasMoreTokens()) {

String word = parser.nextToken().toUpperCase();

String list = map.get(word);

if (list==null) map.put(word,""+lineNumber);

else map.put(word,list+","+lineNumber);

}

System.out.println(lineNumber + ":\t" + line);

line = in.readLine();

}

in.close();

} catch(IOException e) { System.out.println(e); }

System.out.println(map);

System.out.println("lines: " + lineNumber);

System.out.println("distinct words: " + map.size());

}

public static void main(String[] args) {

new Main(args[0]);

}

[리스팅3.19] 항목을 알파벳 순서로 삽입

public class ArrayMap implements Map {
  private static final int INITIAL_LENGTH=10;
  private Entry[] a = new Entry[INITIAL_LENGTH];
  private int size;

  public String get(String key) {
    for (int i=0; i<size; i++)
      if (a[i].key.equals(key)) return a[i].value;
    return null;
  }

  public String put(String key, String value) {
    int i=0;
    while (i<size) {
      if (a[i].key.equals(key)) return a[i].setValue(value);
      if (a[i].key.compareTo(key)>0) break;
      ++i;
    }
    if (size==a.length) resize();
    System.arraycopy(a,i,a,i+1,size-i);
    a[i] = new Entry(key,value);
    ++size;
    return null;
  }

  private void resize() {
    Entry[] aa = new Entry[2*a.length];
    System.arraycopy(a,0,aa,0,a.length);
    a = aa;
  }

  public int size() {
    return size;
  }

  public String toString() {
    StringBuffer buf = new StringBuffer();
    for (int i=0; i<size; i++)
      buf.append(a[i] + "\n");
    return buf.toString();
  }

  private static class Entry {
    String key, value;

    public Entry(String key, String value) {
      this.key = key;
      this.value = value;
    }

    public String setValue(String value) {
      String oldValue = this.value;
      this.value = value;
      return oldValue;
    }

    public String toString() {
      return key + ": " + value;
    }
  }
}

public class ArrayMap implements Map {

private static final int INITIAL_LENGTH=10;

private Entry[] a = new Entry[INITIAL_LENGTH];

private int size;

public String get(String key) {

for (int i=0; i<size; i++)

if (a[i].key.equals(key)) return a[i].value;

return null;

}

public String put(String key, String value) {

int i=0;

while (i<size) {

if (a[i].key.equals(key)) return a[i].setValue(value);

if (a[i].key.compareTo(key)>0) break;

++i;

}

if (size==a.length) resize();

System.arraycopy(a,i,a,i+1,size-i);

a[i] = new Entry(key,value);

++size;

return null;

}

private void resize() {

Entry[] aa = new Entry[2*a.length];

System.arraycopy(a,0,aa,0,a.length);

a = aa;

}

public int size() {

return size;

}

public String toString() {

StringBuffer buf = new StringBuffer();

for (int i=0; i<size; i++)

buf.append(a[i] + "\n");

return buf.toString();

}

private static class Entry {

String key, value;

public Entry(String key, String value) {

this.key = key;

this.value = value;

}

public String setValue(String value) {

String oldValue = this.value;

this.value = value;

return oldValue;

}

public String toString() {

return key + ": " + value;

}

About the Author

View all posts by 진기원
(주)더비소프트 SI&ITO사업부 ERP사업팀 과장
LG전자 GERP 재경, EDI SI업무

1개의 댓글이 등록되었습니다

김진규 2015년 4월 16일 11:19

저는 배열이 이번 스터디 과제에서 가장 중요한 요소 라고 생각됩니다.
거의 모든 자료 구조를 배열을 사용하여 구현 할 수 있다고 해도 과언은 아닐겁니다.
그만큼 이번 주 스터디에는 결석 없이 모두 참여 해 주셨으면 하는 바람입니다.^^
노트북을 필히 지참하여 예제에 나오는 소스를 같이 해보고 싶군요.
수고하셨습니다.

응답

Tag Cloud

Recent Comments

chapter 03. 배열

About the Author

1개의 댓글이 등록되었습니다

김진규 에 응답 남기기 응답 취소

댓글작성시 Code-Highlighter 삽입방법