์ง‘ํ•ฉ์€ ๋‹จ์ˆœํžˆ ๊ณ ์œ ํ•œ ๊ฐœ์ฒด์˜ ๋ชจ์Œ์ž…๋‹ˆ๋‹ค. ๊ณ ์œ ํ•จ์€ ๋‘ ๊ฐœ์ฒด๊ฐ€ ๋™์ผํ•œ ๊ฐ’์„ ๊ฐ€์งˆ ์ˆ˜ ์—†์Œ์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ์„ธํŠธ์˜ ๊ตฌํ˜„์— ๋”ฐ๋ผ ์ฃผ๋ฌธํ•  ์ˆ˜๋„ ์žˆ๊ณ  ์ฃผ๋ฌธํ•˜์ง€ ์•Š์„ ์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค. ADT(Abstract Data Type)๋กœ์„œ์˜ Java ์„ธํŠธ์—๋Š” ๋ช‡ ๊ฐ€์ง€ ์ฃผ์š” ์ž‘์—…์ด ์žˆ์Šต๋‹ˆ๋‹ค(์—ฌ๊ธฐ์„œ T๋Š” int, String ๋˜๋Š” ๋ชจ๋“  ํด๋ž˜์Šค ๊ฐœ์ฒด์™€ ๊ฐ™์€ ๋ชจ๋“  ๋ฐ์ดํ„ฐ ์œ ํ˜•์„ ๋‚˜ํƒ€๋ƒ„). ์ธํ„ฐํŽ˜์ด์Šค๋กœ์„œ์˜ Java ์„ธํŠธ - 1
  • boolean add(T item): ํ•ญ๋ชฉ์ด ์ง‘ํ•ฉ์— ์„ฑ๊ณต์ ์œผ๋กœ ์ถ”๊ฐ€๋˜๋ฉด true๋ฅผ ๋ฐ˜ํ™˜ํ•˜๊ณ  ํ•ญ๋ชฉ์ด ์ด๋ฏธ ์ง‘ํ•ฉ์— ์žˆ์œผ๋ฉด false๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.
  • boolean remove(T item): ํ•ญ๋ชฉ์ด ์ง‘ํ•ฉ์—์„œ ์„ฑ๊ณต์ ์œผ๋กœ ์ œ๊ฑฐ๋˜๋ฉด true๋ฅผ ๋ฐ˜ํ™˜ํ•˜๊ณ  ๊ทธ๋ ‡์ง€ ์•Š์œผ๋ฉด false๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค(ํ•ญ๋ชฉ์ด ์ง‘ํ•ฉ์— ์—†๋Š” ๊ฒฝ์šฐ).
  • boolean contains(T item): ํ•ญ๋ชฉ์ด ์ง‘ํ•ฉ์— ์žˆ์œผ๋ฉด true๋ฅผ ๋ฐ˜ํ™˜ํ•˜๊ณ  ๊ทธ๋ ‡์ง€ ์•Š์œผ๋ฉด false๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.
  • boolean isEmpty(): ์ง‘ํ•ฉ์ด ๋น„์–ด ์žˆ์œผ๋ฉด true๋ฅผ ๋ฐ˜ํ™˜ํ•˜๊ณ  ๊ทธ๋ ‡์ง€ ์•Š์œผ๋ฉด false๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.
Java์˜ ์ง‘ํ•ฉ์—๋Š” ์„ค๋ช…์ด ํ•„์š” ์—†๋Š” ๊ฝค ์ž๋ช…ํ•œ ํ•จ์ˆ˜ ์„œ๋ช…์ด ์žˆ์Šต๋‹ˆ๋‹ค. ๋‘ ๊ฐœ์˜ ๋™์ผํ•œ ํ•ญ๋ชฉ์„ ์„ธํŠธ์— ์ถ”๊ฐ€ํ•˜๋ฉด ์ฒซ ๋ฒˆ์งธ๋กœ ์ถ”๊ฐ€๋œ ํ•ญ๋ชฉ๋งŒ ์„ธํŠธ์— ํฌํ•จ๋ฉ๋‹ˆ๋‹ค. ๋™์ผํ•œ ํ•ญ๋ชฉ์„ ์ถ”๊ฐ€ํ•˜๋ ค๋Š” ๋ชจ๋“  ํ›„์† ์‹œ๋„๋Š” ํ•ญ๋ชฉ์„ ๋จผ์ € ์ œ๊ฑฐํ•˜์ง€ ์•Š๋Š” ํ•œ ๋ฌด์‹œ๋ฉ๋‹ˆ๋‹ค. ๊ฐ€์žฅ ์ผ๋ฐ˜์ ์œผ๋กœ ์‚ฌ์šฉ๋˜๋Š” ์ง‘ํ•ฉ ์ž‘์—… ์ค‘ ํ•˜๋‚˜๋Š” ํ•ญ๋ชฉ์ด ์ฃผ์–ด์ง„ ์ง‘ํ•ฉ ๋‚ด์— ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ด ํ•จ์ˆ˜๋Š” ์ด์— ๋Œ€ํ•œ ํ›Œ๋ฅญํ•œ ๋Ÿฐํƒ€์ž„์„ ์ œ๊ณตํ•ฉ๋‹ˆ๋‹ค. ์‚ฌ์šฉ๋œ ๊ตฌํ˜„์ด a ์ธ์ง€ a contains()์ธ์ง€์— ๋”ฐ๋ผ O(1) ๋˜๋Š” O(log n) ์‹œ๊ฐ„ ๋ณต์žก๋„HashSetTreeSet, ๊ฐ๊ฐ. ๊ทธ๋ ‡๋‹ค๋ฉด ์„ธํŠธ๋Š” ๋ฌด์—‡์„ ์œ„ํ•ด ์‚ฌ์šฉ๋  ์ˆ˜ ์žˆ์Šต๋‹ˆ๊นŒ? ์Œ, ID, ์ด๋ฆ„ ๋˜๋Š” ๊ธฐํƒ€ ๊ณ ์œ  ์‹๋ณ„์ž์™€ ๊ฐ™์€ ๋งŽ์€ ๊ฐœ๋ณ„ ๊ฐœ์ฒด๋ฅผ ์ถ”์ ํ•ด์•ผ ํ•˜๊ณ  ์ด๋Ÿฌํ•œ ์ปฌ๋ ‰์…˜์— ํ•ญ๋ชฉ์ด ์žˆ๋Š”์ง€ ์ž์ฃผ ํ™•์ธํ•ด์•ผ ํ•˜๋Š” ๊ฒฝ์šฐ ์ง‘ํ•ฉ์ด ์ข‹์€ ์„ ํƒ์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. Student๋‹ค์Œ์€ ์ง‘ํ•ฉ์˜ ์‚ฌ์šฉ ์‚ฌ๋ก€ ์˜ˆ์ž…๋‹ˆ๋‹ค. ์ฃผ์–ด์ง„ ์ˆ˜์—…์˜ ๋ชจ๋“  ํ•™์ƒ์„ ๋‚˜ํƒ€๋‚ด๋Š” ๊ฐœ์ฒด ๋ชฉ๋ก์ด ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•ฉ๋‹ˆ๋‹ค . ๊ฐ๊ฐ์€ Student์ด ํด๋ž˜์Šค์— ๋Œ€ํ•ด ๊ณ ์œ ํ•œ ์ด๋ฆ„(๋ฌธ์ž์—ด) ๋ฐ ๋“ฑ๊ธ‰(int)์„ ๊ฐ€์งˆ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋ชจ๋“  A ํ•™์ƒ(๋“ฑ๊ธ‰ >=90)์˜ ๋ชฉ๋ก์„ ์ž์ฃผ ์ฐธ์กฐํ•˜๋ ค๋Š” ๊ฒฝ์šฐ ์ด ๋ชฉ๋ก์„ ๋ฐ˜๋ณตํ•˜๊ณ  ๋งค๋ฒˆ ๋ชจ๋“  ํ•™์ƒ์˜ ๋“ฑ๊ธ‰์„ ํ™•์ธํ•˜๋Š” ๊ฒƒ์€ ์ง€๋ฃจํ•  ๊ฒƒ์ž…๋‹ˆ๋‹ค. HashSet๋Œ€์‹  ๋‹ค์Œ ๊ณผ ๊ฐ™์ด ํด๋ž˜์Šค์˜ ๋ชจ๋“  A ํ•™์ƒ์„ ์ถ”์ ํ•˜๋Š” ๋ฌธ์ž์—ด์„ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค .
  • ํ•™์ƒ์˜ ์„ฑ์ ์ด ์—…๋ฐ์ดํŠธ๋  ๋•Œ๋งˆ๋‹ค ํ•™์ƒ์˜ ์ƒˆ๋กœ์šด ์„ฑ์ ์ด 90 ์ด์ƒ์ธ์ง€ ์•„๋‹Œ์ง€ ๊ฐ„๋‹จํžˆ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
    • ๊ทธ๋ ‡๋‹ค๋ฉด ๋‹ค์Œ์„ ์‚ฌ์šฉํ•˜์—ฌ A ํ•™์ƒ ์„ธํŠธ์— ์ถ”๊ฐ€ํ•˜์‹ญ์‹œ์˜ค.add()
      • ์ด๋ฏธ A ํ•™์ƒ์ธ ๊ฒฝ์šฐ ์ด ์ž‘์—…์€ ๋ฌด์‹œ๋ฉ๋‹ˆ๋‹ค.
    • ๊ทธ๋ ‡์ง€ ์•Š์€ ๊ฒฝ์šฐ ๋‹ค์Œ์„ ์‚ฌ์šฉํ•˜์—ฌ A ํ•™์ƒ ์„ธํŠธ์—์„œ ์ œ๊ฑฐํ•˜์‹ญ์‹œ์˜ค.remove()
      • ์ด ์‹œ์ ์—์„œ ๊ทธ๋“ค์ด A ํ•™์ƒ์ด ์•„๋‹ˆ์—ˆ๋‹ค๋ฉด ์ด ์ž‘์—…์€ ๋‹จ์ˆœํžˆ ๋ฌด์‹œ๋ฉ๋‹ˆ๋‹ค.
์ด๋Ÿฌํ•œ ์‹œ์Šคํ…œ์„ ์‚ฌ์šฉํ•˜๋ฉด ์ˆ˜์—…์— ํ•ญ์ƒ ์ตœ์‹ ์˜ ๋ชจ๋“  'A' ํ•™์ƒ ์ง‘ํ•ฉ์ด ์žˆ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. Johnny Appleseed๊ฐ€ ์ˆ˜์—…์—์„œ ์ž˜ํ•˜๊ณ  ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๊ณ  ์‹ถ๋‹ค๋ฉด contains(โ€œJohnny Appleseedโ€)์„ธํŠธ์žฅ์— ์ „ํ™”๋ฅผ ๊ฑธ์–ด ์‰ฝ๊ฒŒ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋ฌผ๋ก  ์ด๊ฒƒ์€ ์ง‘ํ•ฉ์— ๋Œ€ํ•œ ์‚ฌ์šฉ ์‚ฌ๋ก€์˜ ํ•œ ์˜ˆ์ผ ๋ฟ์ด๋ฉฐ A ํ•™์ƒ์„ ์ถ”์ ํ•˜๋Š” ํŠน์ • ๋ฌธ์ œ๋Š” ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์œผ๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๊ตฌํ˜„: Java์˜ HashSet ๋ฐ Java TreeSet ์˜ˆ์ œ

HashSetin Java์™€ TreeSetin Java๋Š” ๋ชจ๋‘ java.utils package. ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ฐ€์ ธ์˜ฌ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

// imports everything from Java's util package, including HashSet and TreeSet
import java.util.*;
๋˜๋Š”

import java.util.HashSet; // imports only the Java HashSet
import java.util.TreeSet; // imports only the Java TreeSet
Java HashSet์™€ Java ์˜ ์ฃผ์š” ์ฐจ์ด์ ์€ ์ •๋ ฌ๋˜๋Š” ๋ฐ˜๋ฉด ์ •๋ ฌ๋˜์ง€ ์•Š๋Š”๋‹ค๋Š” TreeSet๊ฒƒ์ž…๋‹ˆ๋‹ค . ์ด๊ฒƒ์ด ์ฃผ์š” ์ž‘์—…์— ๋Œ€ํ•ด O(log n) ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ–๋Š” ๋ฐ˜๋ฉด O(1) ๋˜๋Š” ์ผ์ •ํ•œ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ–๋Š” ์ด์œ ์ž…๋‹ˆ๋‹ค. ํ•ญ์ƒ ์งˆ์„œ๋ฅผ ์œ ์ง€ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค . ์•ž์—์„œ ์–ธ๊ธ‰ํ•œ ํ‚ค ์„ค์ • ์ž‘์—… ์™ธ์—๋„ Java์˜ ๋ฐ ์—๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ช‡ ๊ฐ€์ง€ ์œ ์šฉํ•œ ๊ธฐ๋Šฅ์ด ์žˆ์Šต๋‹ˆ๋‹ค. TreeSetHashSetTreeSetHashSetTreeSetHashSetTreeSet
  • void clear(): ๋ชจ๋“  ๊ฐœ์ฒด ์ง‘ํ•ฉ์„ ์ง€์›๋‹ˆ๋‹ค.
  • int size(): ์ง‘ํ•ฉ์˜ ๊ฐœ์ฒด ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.
  • Object clone(): ์ง‘ํ•ฉ์˜ ๋‹จ์ˆœ ๋ณต์‚ฌ๋ณธ์„ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.
  • Iterator iterator(): ์ฒซ ๋ฒˆ์งธ ๊ฐœ์ฒด์—์„œ ์‹œ์ž‘ํ•˜์—ฌ ์ง‘ํ•ฉ์— ๋Œ€ํ•œ ๋ฐ˜๋ณต์ž๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.
"A ํ•™์ƒ ๋ชฉ๋ก" ์˜ˆ์—์„œ ์ด๋Ÿฌํ•œ ๊ธฐ๋Šฅ์˜ ์šฉ๋„๋ฅผ ์ฐพ๋Š” ๊ฒƒ์„ ์ƒ์ƒํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. size()'A' ํ•™์ƒ์ด ๋ช‡ ๋ช…์ธ์ง€ ํ™•์ธํ•˜๊ณ  ์‹ถ๊ฑฐ๋‚˜ clear()ํ•™๊ธฐ ๋ง์— ๋ชฉ๋ก์„ ์ง€์šฐ๊ณ  ์‹ถ๋‹ค๋ฉด ์ „ํ™”๋ฅผ ๊ฑธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. clone()์ค‘๊ฐ„ ๋ณด๊ณ ์„œ์™€ ๊ฐ™์€ ํŠน์ • ์‹œ์ ์— A ํ•™์ƒ ๋ชฉ๋ก์˜ ๋ณต์ œ๋ณธ์„ ๋งŒ๋“ค๊ณ  ์œ ์ง€ํ•˜๋Š” ๋ฐ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค(์ด๋ ‡๊ฒŒ ํ•˜๋ฉด ๋ณต์ œ๋ณธ์ด ์›๋ณธ๊ณผ ํ•จ๊ป˜ ์ตœ์‹  ์ƒํƒœ๋กœ ์œ ์ง€๋˜์ง€ ์•Š์Œ) .

์ž๋ฐ” ํ•ด์‹œ์…‹ ์˜ˆ์ œ

๋‹ค์Œ์€ Java์—์„œ ์‚ฌ์šฉ๋˜๋Š” a HashSetof s ์˜ ๊ฐ„๋‹จํ•œ ์˜ˆ์ž…๋‹ˆ๋‹ค .String

import java.util.HashSet;
class HashSetDemo {
    public static void main(String[] args)
    {
	  // create a HashSet of Strings
        HashSet<String> hs = new HashSet<String>();
  
        // Add elements using the add() method
        hs.add("Collin");
	  hs.add("Bob");
 	  hs.add("Abigail");
  
        // Duplicates will ignored; this statement is useless
        hs.add("Collin");
  
        
        System.out.println(hs);
	  System.out.println("Bob is in the set (T/F): " + hs.contains("Bob"));
  System.out.println("Max is in the set (T/F): " + hs.contains("Max"));


    }
}
์ถœ๋ ฅ: --------

[Collin, Bob, Abigail]
Bob is in the set (T/F): true
Max is in the set (T/F): false

์ž๋ฐ” ํŠธ๋ฆฌ์…‹ ์˜ˆ์ œ

Java ์„ธํŠธ ์˜ˆ์ œ๋Š” ์ด๋ก ์„ ์ดํ•ดํ•˜๋Š” ๋ฐ ๋„์›€์ด ๋  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋‹ค์Œ์€ Java์—์„œ ์‚ฌ์šฉ๋˜๋Š” a TreeSetof s ์˜ ๊ฐ„๋‹จํ•œ ์˜ˆ์ž…๋‹ˆ๋‹ค .String

import java.util.TreeSet;
class TreeSetDemo {
    public static void main(String[] args)
    {
	  // create a TreeSet of Strings
        TreeSet<String> ts = new TreeSet<String>();
  
        // Add elements using the add() method.
        ts.add("Collin");
	  ts.add("Bob");
 	  ts.add("Abigail");
  
        // Duplicates will ignored; this statement is useless
        ts.add("Collin");
  
        // printing the set prints the names in alphabetical order!
        System.out.println(ts); 
	  
	  System.out.println("Bob is in the set (T/F): " + ts.contains("Bob"));
  System.out.println("Max is in the set (T/F): " + ts.contains("Max"));
  System.out.println("Size of the set: " + ts.size());
 	  ts.clear();
	  System.out.println("Size of the set after clear(): " + ts.size());
        

    }
}
์ถœ๋ ฅ: -------

[Abigail, Bob, Collin]
Bob is in the set (T/F): true
Max is in the set (T/F): false
Size of the set: 3
Size of the set after clear(): 0
๊ทธ๊ฒŒ ๋‹ค์•ผ! ์ด๊ฒƒ์ด ๋„์›€์ด ๋˜์—ˆ๊ธฐ๋ฅผ ๋ฐ”๋ž๋‹ˆ๋‹ค ๐Ÿ˜Š