[프로그래머스 / Level1] 두 개 뽑아서 더하기 (Java)

문제

https://programmers.co.kr/learn/courses/30/lessons/68644?language=java 

코딩테스트 연습 - 두 개 뽑아서 더하기

 

📌 핵심 키워드

• Set 인터페이스
• HashSet 클래스
• TreeSet 클래스
• Collection.sort() 정렬
• Collection을 int 배열로 변환
• Iterator

 

코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        Set<Integer> set = new TreeSet<>();
        
        for(int i=0; i < numbers.length; i++){
            for(int j=i+1; j<numbers.length; j++){
                set.add(numbers[i] + numbers[j]);			//Set은 중복일 경우 추가안됨
            }
        }
        
        int[] arr = set.stream().mapToInt(Integer::intValue).toArray();	//Set<Integer>을 int[]로 변환
        Arrays.sort(arr);						//배열 정렬
        
        return arr;
    }
}

 

학습 내용

Set 인터페이스

• 데이터의 중복을 허용하지 않고, 저장순서가 유지되지 않는다.
  예) 양의 정수집합, 소수의 집합
• 구현 클래스 : HashSet, TreeSet 등

 

HashSet 클래스

• add 메서드, addAll 메서드를 사용해 새로운 요소를 추가할 수 있다.
• 중복을 허용하지 않기 때문에 객체를 추가할 때 HashSet에 이미 같은 객체가 있으면 중복으로 간주하고 저장하지 않는다. → false 반환.
• 추가하려는 요소의 equals(), hashCode() 메서드를 호출하여 중복 요소인지 판별.
• "1" ↔ Integer(1) 과 같이 자료형이 다른 경우 중복으로 간주하지 않음.
• 저장순서를 유지하지 않고 자체적인 방식에 따라 데이터의 순서가 결정되기 때문에 저장시와 순서가 다를 수 있다.
  저장순서를 유지하고 싶다면 LinkedHashSet을 사용하면 된다.

public class Bingo {

	public static void main(String[] args) {
		Set set = new HashSet();
		int[][] board = new int[5][5];
		
		for(int i=0; set.size() < 25; i++) {
			set.add((int)(Math.random() * 50 + 1));						//HashSet 요소로 랜덤 값 추가	
		}
		
		Iterator it = set.iterator();									//HashSet 요소 접근용 Iterator
		
		for(int i =0; i<board.length; i++) {
			for(int j=0; j<board[i].length; j++) {
				board[i][j] = Integer.parseInt(it.next().toString());	//next() 반환 값은 Object
				System.out.print(String.format("%3d", board[i][j]));
//				System.out.print(board[i][j] > 10 ? " " : "  " + board[i][j])E
			}
			System.out.println();
		}
	}
}

 

TreeSet 클래스

• 이진 검색 트리(Binary Search Tree) 자료구조 형태로 데이터를 저장하는 컬렉션 클래스
• 이진 검색 트리의 성능을 향상시킨 '레드-블랙 트리(Red-Black Tree)'로 구현됨.
• 중복 허용 X, 데이터 순서 유지X, 자체적으로 위치 정렬.
• 루트 노드부터 시작해 각 노트에 최대 2개의 노드를 연결하며 확장. (부모-자식 관계)
  하나의 TreeNode = Object 변수(부모 본인의 데이터) + TreeNode(왼쪽 자식 노드) + TreeNode(오른쪽 자식 노드)
• 부모노드의 왼쪽에는 부모노드 값 보다 작은 값의 자식노드를, 오른쪽에는 큰 값의 자식노드를 저장.
  *Set 인터페이스를 상속받아 중복을 허용하지 않기 때문에 새로 추가되는 값은 기존의 값보다 무조건 작거나 크다.
• 객체 정렬기준 : 1. 저장 객체에서 Comparable을 구현 / 2. TreeSet에 Comparator 제공
• 첫번째로 저장되는 값이 루트 노드.
• 단일 값/범위 검색과 정렬 Good, 데이터 추가/삭제 Bad.

import java.util.Set;
import java.util.TreeSet;

//TreeSet 로또
public class TreeSetLotto {
	public static void main(String[] args) {
		TreeSet<Integer> tree = new TreeSet<Integer>();
		
		for(int i=0; tree.size() < 6; i++) {
			int num = (int)(Math.random() * 45) + 1;
			tree.add(num);
		}
		
		System.out.println(tree);
		System.out.println(tree.descendingSet());	//역순 정렬
		System.out.println(tree.first());			//정렬순에서 첫번째 객체
		System.out.println(tree.last());			//정렬순에서 마지막 객체
		System.out.println(tree.headSet(10));		//지정된 객체보다 작은 값의 객체들
		System.out.println(tree.tailSet(10));		//지정된 객체보다 큰 값의 객체들
		System.out.println(tree.pollFirst());		//제일 작은 값의 객체
		System.out.println(tree.pollLast());		//제일 큰 값의 객체
		System.out.println(tree.subSet(10, 30));	//범위 검색 (마지막 값 포함X)
		System.out.println(tree.subSet(10, true, 30, true));	//범위 검색 (첫 값, 마지막 값 포함O)		
	}
}

[5, 21, 26, 30, 38, 45]
[45, 38, 30, 26, 21, 5]
5
45
[5]
[21, 26, 30, 38, 45]
5
45
[21, 26]
[21, 26, 30]

 

*이진 검색 : 가운데 중간값을 기준으로 왼쪽에는 중간값보다 작은 값이, 오른쪽에는 중간값보다 큰 값이 위치하도록 정렬된 데이터에서 가장 먼저 중간값에 접근한 뒤, 접근한 값이 탐색대상보다 작은가? 큰가? 판단해서 순차 검색보다 빠르게 탐색을 수행할 수 있다. (=한번의 탐색에 탐색해야할 범위가 절반씩 줄어듬)

 

Arrays 클래스

• 배열을 다루는 데 유용한 메서드들이 정의되어 있다.
• 모두 static 메서드이기 때문에 클래스명.메서드명() 과 같이 호출한다.

메서드	설명
int[] copyOf(int[] a, int end)	처음부터 end-1까지 배열을 복사하여 반환
int[] copyOfRange(int[] a, int start, int end)	start부터 end-1까지 배열 일부를 복사하여 반환
void fill(int[] a, int val)	배열의 모든 요소를 지정된 값으로 채움
void setAll(int[] a, IntFunction<Integer> getnerator)	함수형 인터페이스를 구현한 객체 또는 람다식을 매개변수로 받아 함수의 반환값으로 요소 값들을 채움.
void sort(int[] a)	배열을 정렬
int binarySearch(int[] a, int key)	배열에서 지정된 값이 저장된 위치(index)를 반환 *반드시 배열이 정렬된 상태에서 탐색해야함.
String toString(int a)	배열의 모든 요소를 문자열로 반환 (1차원 배열)
String deepToString(int[][] a)	배열의 모든 요소를 문자열로 반환 (다차원 배열)
boolean equals(int[] a, int[] b)	두 배열에 저장된 모든 요소를 비교해 같으면 true, 다르면 false (1차원 배열)
boolean equals(int[][] a, int[][] b)	두 배열에 저장된 모든 요소를 비교해 같으면 true, 다르면 false (다차원 배열)
List asList(Object... a)	배열을 List에 담아서 반환 (반환된 List 크기는 변경 불가)
parallelXXX()	여러 스레드가 작업을 나누어 처리하는 메서드들
Spliterator spliterator()	하나의 작업을 여러 작업으로 나누는 Spliterator를 반환
IntStream stream(int[] a)	컬렉션을 Stream으로 변환

*모든 메서드는 int형을 기준으로 표기, Arrays 클래스 내 일부 메서드만을 정리.

 

Collections 클래스

• 컬렉션과 관련된 메서드를 제공
• Collections.sort(List list) 메서드는 인자로 List인터페이스 타입을 필요로 하기 때문에 HashSet과 같이 다른 인터페이스를 구현하는 클래스의 데이터를 정렬하고자 할 때는 LinkedList(Collection c) 생성자를 사용해 HashSet에 저장된 객체들을 LinkedList에 담아서 처리해야 한다.
• fill(), copy(), sort(), binarySearch() 등 메서드는 Arrays 메서드와 동일
• Collections 클래스 메서드

메서드	설명
void rotate(List<?> list, int distance)	리스트의 각 요소를 오른쪽으로 distance만큼 이동
void swap(List<?> list, int i, int j)	리스트의 특정위치에 있는 요소들의 위치를 서로 변경
void shuffle(List<?> list)	리스트에 저장된 요소의 위치를 임의로 변경
void reverse(List<?> list)	리스트에 저장된 요소를 반대로 정렬 = sort(List list, reverseOrder()) 와 동일
void copy(List<? super T> dest, List<? super T> src)	src리스트의 모든 요소를 dest리스트로 복사
boolean replaceAll(List<T> list, T oldVal, T newVal)	리스트의 oldVal을 모두 newVal로 전환
Collection synchronizeCollection(Collection c)	멀티 스레드 프로그래밍 시 객체 일관성 유지를 위한 동기화 기능
Collection unmodifiableCollection(Collection c)	컬렉션을 변경 불가, 읽기전용으로 반환
List singletonList(Object o)	단 하나의 객체만을 저장하는 싱글톤 컬렉션으로 반환
Collection checkedCollection(List list, Class type)	지정된 타입의 객체만을 저장하는 컬렉션 반환

*각 메서드는 Collection, List, Set 등 다양한 버전으로 존재하며, 대표로 하나씩만 기재.

 

컬렉션(Collection) → 배열(Array) 변환

Collection클래스의 toArray() 메서드 반환값은 Object[] 타입이기 때문에 특정 타입으로 형변환이 필요하다.

A. list.toArray() 메서드 사용

다만 list.toArray()가 매개변수로 primitive type(int[])을 받지 못하기 때문에, List<Integer> 타입을 int[] 타입으로 변환하려면 아래 있는 다른 방법들을 이용해야한다.

List<String> list = new ArrayList<>();

for(int i=0; list.size() < 10; i++) {
	list.add("text" + i);
}

String[] arr = list.toArray(new String[list.size()]);
//[text0, text1, text2, text3, text4, text5, text6, text7, text8, text9]

 

B. 반복문

List<Integer> list = new ArrayList<Integer>();

for(int i=0; list.size() < 10; i++) {
	list.add(i);
}

int[] arr = new int[list.size()];
int size = 0;
for(int i : list) {
	arr[size++] = i;
}
//[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

C. Stream방식, list.stream()

List<Integer> list = new ArrayList<Integer>();

for(int i=0; list.size() < 10; i++) {
	list.add(i);
}

int[] arr = list.stream().mapToInt( i -> i ).toArray();
//int[] arr = list.stream().mapToInt(Integer::intValue).toArray();

 

 

배열(Array)→ 컬렉션(Collection) 변환

A. Arrays.asList() 메서드 사용
다만, asList()메서드가 primitive타입(int)을 Wrapper클래스(Integer)로 형변환해주지 않기 때문에 int[] 타입에 Arrays.asList()를 사용해서 ArrayList<Integer>로 변환하는 것은 불가능하다.

String[] arr = new String[10];

for(int i=0; i < 10; i++) {
	arr[i] = "text" + i;
}

List<String> list = new ArrayList<String>(Arrays.asList(arr));
//[text0, text1, text2, text3, text4, text5, text6, text7, text8, text9]

 

B. 반복문으로 요소 추가

int[] arr = new int[10];

for(int i=0; i < 10; i++) {
	arr[i] = i;
}

List<Integer> list = new ArrayList<>();
for(int elem : arr) {
	list.add(elem);
}
//[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

C.  Stream 방식, Arrays.stream()

int[] arr = new int[10];

for(int i=0; i < 10; i++) {
	arr[i] = i;
}
	
List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
//[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

Iterator

• 컬렉션에 저장된 요소에 접근하기 위해 사용.
• 컬렉션에 저장된 요소에 접근하는 기능의 Iterator 인터페이스를 정의한 뒤, 각각의 컬렉션 클래스 들에 Iterator 구현 클래스의 인스턴스를 반환하는 iterator() 메서드를 정의해둔다. (=컬렉션 접근 방식 통일) List, Set 인터페이스는 Collection인터페이스로 부터 이 iterator() 메서드를 상속받아 자신들의 자료구조에 맞게 구현해뒀다.
• Iterable 인터페이스는 공통 메서드인 iterator()를 추출해서 따로 인터페이스로 묶어놔 중복을 제거하기 위한 것.

//Iterator 인터페이스
public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
}

//Iterable 인터페이스
public interface Iterable<T> {
    Iterator<T> iterator();
    ...
}

//Collection 인터페이스
public interface Collection<E> extends Iterable<E> {
    ...
    Iterator<E> itertator();
    ...
}

 

• Iterator 인터페이스 메서드

메서드	설명
boolean hasNext()	읽어올 요소가 남아있는지 확인한다. (있으면 true, 없으면 false)
Object next()	다음 요소를 읽어온다. (hasNext()가 true일 경우 next() 하는 식으로 사용) 반환값이 Object타입이기 때문에 원래의 타입으로 형변환시켜서 사용해야 한다.
void remove()	next()로 읽어온 요소를 삭제. (next() 이후 사용)

import java.util.ArrayList;
import java.util.Iterator;

public class IteratorEx1 {
	public static void main(String[] args) {
		ArrayList<Integer> list = new ArrayList();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		list.add(5);
		
		Iterator it = list.iterator();
		while(it.hasNext()) {
			System.out.println(it.next());
		}
	}
}

1
2
3
4
5

 

참조변수 타입을 인스턴스의 타입이 아니라 상위 인터페이스 타입으로 하는 이유

ex) Set<Integer> set = new TreeSet();  /  List<Integer> list = new ArrayList();

예를 들어 List c = new ArrayList()와 같이 선언해두면, 이후 인스턴스 c를 LinkedList 클래스 타입으로 변환해서 사용할 때 코드에 별다른 수정을 가할 필요가 없다. 참조변수가 List타입인 c는 List인터페이스에 존재하는 메서드만 사용했다는 것이기 때문에 똑같이 List 인터페이스를 구현하는 LinkedList 클래스에도 해당 메서드들이 전부 존재하기 때문이다. 즉, 선언해둔 Collection은 다른 Collection 타입으로 변환하는 경우를 산정해서 선언해 둔 것.

물론 ArrayList에만 존재하는 메서드를 사용하려 한다면 참조변수도 이와 같은 ArrayList 타입으로 선언해줘야 한다. 하위 클래스는 상위 클래스/인터페이스의 메서드를 반드시 갖고 있지만, 상위 클래스/인터페이스는 하위 클래스의 메서드를 갖고있지 않을 수도 있기 때문이다.

 

j = i +1 인 이유

• i가 2일 때
  i=2 ) numbers[2] + numbers[0]
  i=2 ) numbers[2] + numbers[1] 
  합 계산은
• 이미 앞서 i가 0, 1일 때
  i=0 ) numbers[0] + numbers[2]
  i=1 ) nubmers[1] + numbers[2]
  를 통해 계산되었기 때문에 자신보다 앞에 있는 요소와는 합 계산을 수행할 필요가 없음.

 

---

[참고]

• Java의 정석 3rd / 남궁 성 / 도우출판
• How to convert List<Integer> to int[] in Java, https://stackoverflow.com/a/23945015