Part 04 집합 (Set)

1. 집합 (Set)

  - 선형 데이터 구조 + 탐색 알고리즘

  - list와 다르게 set은 중복을 허락하지 않는다.

  - set은 순서를 보장하지 않는다.

 

  - 합집합: setA.addAll(setB) - B의 원소를 모두 A에 추가한다.

  - 차집합: setA.removeAll(setB) - A에서 B의 원소 모두 제거

  - 교집합: setA.retainAll(setB)

 

 

  Ex) Set 연습

java

열기 줄바꿈

import java.util.LinkedHashSet;
import java.util.Objects;
import java.util.Set;

class MyData{
	int v;
	
	public MyData(int v) {
		this.v = v;
	}
	
	public String toString() {
		return "" + v;
	}
	
	 @Override
	public boolean equals(Object o) {
		if(this == o)	return true;
		if(o == null || getClass() != o.getClass())	return false;
		MyData mydata = (MyData) o;
		return v== mydata.v;
	}
	 
	 @Override
	public int hashCode() {
		return Objects.hash(v);		
			// 같은 value가 들어가면 같은 해시값이 나온다.
			// 키로 사용되는 것은 해시코드를 호출해서 나온 해시값을 이용해서 인덱스로 이용한다.
	}
}

public class SetPractice {

	public static void main(String[] args) {
		
		Set<MyData> setA = new LinkedHashSet<>(); // set은 순서를 보장하지않는다.(중복 여부만 확인된다.)
		Set<MyData> setB = new LinkedHashSet<>();

		setA.add(new MyData(1));
		setA.add(new MyData(2));	
		setA.add(new MyData(3));
	
		setB.add(new MyData(2));
		setB.add(new MyData(3));	
		setB.add(new MyData(4));
	
//합집합		setA.addAll(setB);				// [1, 2, 3, 4 ]
//차집합		setA.removeAll(setB);			// [1]
//교집합		setA.retainAll(setB);			// [2, 3]
		System.out.println(setA);		
		
	}
}

 

  Ex) 로또 번호

java

열기 줄바꿈

	class Solution {
		public boolean solution(int [] lotto) {
			Set<Integer> set = new HashSet<>();
			for(int l : lotto ) {
				if( l < 1 || l > 45) return false;
				set.add(l);
				
			}
			return set.size() == lotto.length;
		}
	}

  - 먼저, 1~45 사이가 아니면 false를 반환한다.

  - 1~45 만족하면 l을 set에 추가한다. 

  - 마지막에 set의 사이즈와 배열 lotto의 길이가 같은지 boolean형태로 반환한다.

 

  Ex) 끝말 잇기

java

열기 줄바꿈

import java.util.*;
class Solution {
    public boolean solution(String[] words) {
       
        Set<String> set = new HashSet<>();
        set.add(words[0]);
        char last = words[0].charAt(words[0].length() - 1); 	// 첫번째 단어의 마지막 글자를last에 저장
        
        for(int i = 1; i < words.length; ++i){ 		// i는 0이 아닌 1부터 시작
            
            String w = words[i]; 	// 스트링을 w에 저장
            char first = w.charAt(0); 	// w의 첫 글자를 first에 저장
            
            if(last != first ) return false;
            if(!set.add(words[i])) return false;
            
            last = w.charAt(w.length() - 1);   // 다시 last에 마지막 글자를 넣어준다.
        }
        return true;
    }
}

  - words.length : String 배열 words의 크기

  - w.length(): String w의 길이 (글자 수)

  - set.add(words[i]) 에서 이미 있는 원소를 추가하려면 false가 반환되므로 이를 조건으로 이용한다.

 

  Ex) 배열에서 중복된 숫자 제거하고 나타내기

java

열기 줄바꿈

import java.util.*;
public class Solution{
	public int[] solution(int [] arr) {
			List<Integer> list = new LinkedList<>();
			int last = -1;
			
            for(int i = 0; i < arr.length; ++i) {
				if(last == arr[i]) continue;
				last = arr[i];
				list.add(arr[i]);			
			}
		return list.stream().mapToInt(Integer::intValue).toArray();
	}
}

  - 같은 숫자가 여러 개 나올 수 있기 때문에 set이 아닌 list를 이용한다.

 

 

출처: https://programmers.co.kr/learn/courses/13577