이번에는 집합 알고리즘에 대해 학습할 예정이다.
집합
명확한 조건을 만족하는 자료의 모임이다.
이번에는 집합을 다양한 메서드로 구현하는 것에 대해 살펴본다
- 집합
- 범위를 규정한 '어떤 것'의 모임 ------ 요소 개수가 1개여도 집합이고, 요소가 없는 집합(공집합)도 집합이다!
- 어떤 것: 요소
- 특징
- 집합에 포함되는 요소는 서로 달라야 한다. == 중복이 없어야 한다.
- 집합은 집합을 요소로 가질 수 없다.
- 집합의 요소에는 순서가 없다.
- 집합이 같다 == 같은 요소로 구성된다.
- 부분집합 / 진부분집합
- 다른 집합에 포함된 집합
- A = {1, 3} , B = {1, 3, 5} 와 같이 집합 A의 모든 요소가 B의 요소이면 A는 B의 부분집합이다.
'A는 B에 포함된다.' - A = {1, 3, 5} 일 때처럼 A와 B가 서로 같은 경우 A와 B는 서로 부분집합 관계가 된다.
- 1번째 예시는 A는 B의 부분집합이자 진부분집합이고, 2번째 A와 B가 같은 경우는 A는 B의 부분집합이지만
진부분집합은 아니다.
- 연산
- 합집합: 적어도 한 쪽에 속하는 요소의 집합
- 공집합: 양쪽 모두에 속하는 요소의 집합
- 차집합: 어떤 집합의 요소를 제외한 요소의 집합
배열로 구현
배열을 사용하여 집합을 표현하려면 집합의 요소 개수와 배열의 요소 개수는 항상 같아야 한다.
집합의 상태를 표현할 데이터가 필요하다.
따라서 집합을 표현하는 배열과 이 배열의 정보를 담은 클래스를 함께 사용하여 구현한다.
- 클래스
- 필드
- max: 집합의 최대 크기
- num: 집합의 요소 개수
- set: 집합을 저장할 배열 -- 집합 본체
- 필드
public class ArraySet {
private int max;
private int num;
private int[] set;
public ArraySet(int capacity){
num = 0;
max = capacity;
try{
set = new int[max]; //집합 배열 생성
}
catch(OutOfMemoryError e){
max = 0;
}
}
public int capacity(){
return max;
}
public int size(){
return num;
}
public int indexOf(int n){ //n찾아서 인덱스 반환
for(int i = 0; i < num; i++){
if(set[i] == n)
return i;
}
return -1;
}
public boolean contains(int n){
return indexOf(n) != -1; //집합에 n이 있는지 확인
}
public boolean add(int n){
if(num >= max || contains(n)) { //중복이지 않을 때 삽입
return false;
}
else {
set[num++] = n; //집합에 n 추가
return true;
}
}
public boolean remove(int n){
int idx;
if(num <= 0 || (idx = indexOf(n)) == -1){
return false;
}
else{
set[idx] = set[--num]; //마지막 요소를 삭제한 곳으로 옮긴다.
return true;
}
}
//내 집합을 다른 집합에 복사
public void copyTo(ArraySet s){
int n = (s.max < num) ? s.max : num;
for(int i = 0; i < n; i++){
s.set[i] = set[i];
}
s.num = n;
}
//다른 집합을 내 집합에 복사
public void copyFrom(ArraySet s){
int n = (max < s.num) ? max : s.num;
for(int i = 0; i < n; i++){
set[i] = s.set[i];
}
num = n;
}
public boolean equalsTo(ArraySet s){
if(num != s.num){
return false;
}
for(int i = 0; i < num; i++){
int j = 0;
for(; j < s.num; j++){
if(set[i] == s.set[j]){
break;
}
}
if(j == s.num){
return false;
}
}
return true;
}
//합집합
public void unionOf(ArraySet s1, ArraySet s2){
copyFrom(s1);
for(int i = 0; i < s2.num; i++){
add(s2.set[i]);
}
}
public String toString(){
StringBuffer sb = new StringBuffer("{ ");
for(int i = 0; i < num; i++){
sb.append(set[i] + " ");
}
sb.append("}");
return sb.toString();
}
public static void main(String[] args){
ArraySet s1 = new ArraySet(20);
ArraySet s2 = new ArraySet(20);
ArraySet s3 = new ArraySet(20);
s1.add(10);
s1.add(15);
s1.add(20);
s1.add(25);
s1.copyTo(s2);
s2.add(12);
s2.remove(25);
s3.copyFrom(s2);
System.out.println("s1 = " + s1);
System.out.println("s2 = " + s2);
System.out.println("s3 = " + s3);
System.out.println("집합 s1에 있는 15는 " +
(s1.contains(15) ? "포함됩니다." : "포함되지 않습니다."));
System.out.println("집합 s2에 있는 25는 " +
(s2.contains(25) ? "포함됩니다." : "포함되지 않습니다."));
System.out.println("집합 s1과 s2는 "+
(s1.equalsTo(s2)? "같습니다." : "같지 않습니다."));
System.out.println("집합 s2과 s3는 "+
(s2.equalsTo(s3)? "같습니다." : "같지 않습니다."));
s3.unionOf(s1, s2);
System.out.println("집합 s1과 s2의 합집합은 " + s3 + "입니다.");
}
}
- remove: 요소를 삭제하는 메서드입니다. num을 감소시키고 요소를 삭제한 자리에 마지막 요소를 대입합니다.
- unionOf: 두 집합의 합집합을 자신의 집합으로 복사하는 메서드입니다. -> 하나의 집합을 복사하고 다른 집합을 추가하는 방식
toString 복습
자바에서 toString은 java.lang 패키지의 클래스에서 정의되어 있다.
원래는 클래스 이름@해시값 의 형태로 문자열을 반환한다.
자바의 모든 클래스는 Object 클래스의 자식 클래스이다. 이때 toString 메서드를 정의하면
Object 클래스의 메서드를 재정의 했다고 한다.
class A {
}
class B{
int x;
B(int x){
this.x = x;
}
public String toString(){
return "b["+ x +"]";
}
}
public class toStringTest{
public static void main(String[] args){
A a1 = new A();
A a2 = new A();
B b1 = new B(18);
B b2 = new B(55);
System.out.println("a1 = " + a1);
System.out.println("a2 = " + a2);
System.out.println("b1 = " + b1);
System.out.println("b2 = " + b2);
}
}
재정의한 메서드대로 출력이 나온다.
a1 = A@3f99bd52
a2 = A@4f023edb
b1 = b[18]
b2 = b[55]
인스턴스의 상태를 간단한 문자열로 출력할 때는 public String toString() 형식으로 정의하는 것이 좋다.