나는 9명의 키의 다 더해서 총합을 구하고 arraylist의 값 중 2개의 값을 삭제하는 방식으로 문제를 풀었다.
- 코드
import java.util.*;
import java.io.*;
import java.util.stream.IntStream;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int[] arr = new int[9];
for(int i=0;i<9;i++){
arr[i] = Integer.parseInt(bf.readLine());
}
ArrayList<Integer> list = new ArrayList<>();
int tot = IntStream.of(arr).sum();//난쟁이의 키의 합을 더한다.
for(int a : arr){
list.add(a);
}
int target= tot-100;//100을 빼서 타겟 넘버를 저장
for(int i=0;i<arr.length;i++){
int now = arr[i];
int want= target-now;
list.remove(Integer.valueOf(now));
if(list.contains(want)) {//리스트에 찾는 값이 있는지 검사
list.remove(Integer.valueOf(want));//있으면 삭제하고
break;//반복문 탈출
}
list.add(now);
}
Collections.sort(list);//오름차순으로 정렬
for(int a: list){
System.out.println(a);
}
}
}
- 설명
1) IntStream.of(arr).sum()
arr배열의 값을 모두 더함.
2) list.remove(Integer.valueOf(now))
list.remove(20); 이라고 쓸 경우, 20이 값인 게 아니라 리스트 인덱스 20인 값이 삭제되게 된다.
그보다 좀 더 빠르고 효율적인 O(n logn)의복잡도를 갖는 알고리즘(병합정렬, 퀵정렬, 트리정렬)이 있다.
1. Bubble Sort(버블 정렬)
바로 그 다음 노드와 비교해가면서 가장 큰 값을 하나씩 뒤로 보내면서 뒤쪽부터 정렬한다.
버블 정렬은 정렬 방식이 마치 물 속에서 올라오는 물방울과 같다고 하여 버블 정렬이라는 이름이 붙여졌다.
버블 정렬
- 장점
구현이 간단하다.
데이터를 하나씩 비교하기 때문에 정밀한 비교가 가능하다.
- 단점
데이터를 하나씩 비교하기 때문에 비교 횟수가 많아지므로 시간이 오래 걸린다.
- 소스코드
public class BubbleSort {
public int[] sol(int[] arr){
int k= arr.length;//배열의 길이
for(int i=0;i<k-1;i++){
for(int j=0;j<k-1-i;j++){
int temp;
if(arr[j]>arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
return arr;
}
}
2. 선택 정렬
선택정렬은 앞쪽부터 정렬하는 방식이다.
주어진 배열에서 가장 작은 최소값을 찾고 배열의 맨 앞의 값과 위치를 바꾸면서 정렬한다.
배열에서 최소값을 찾아야 하기 때문에 비교 횟수는 많지만 실제로 값을 바꾸는 교환횟수가 적다는 것이 특징이다.
선택 정렬
- 장점
구현이 간단하다
비교하는 횟수에 비해 교환하는 횟수가 적다.
-단점
데이터를 하나씩 비교하기때문에 시간이 오래 걸린다.
정렬된 상태에서 새로운 데이터가 추가되면 정렬 효율이 좋지 않다.
- 소스코드
public class SelectionSort {
public int[] sol(int[] arr){
int k= arr.length;//배열의 길이
for(int i=0;i<k-1;i++){
int temp, minIdx = i;
for(int j=i+1;j<k;j++){
if(arr[minIdx]>arr[j]){
minIdx = j;
}
}
temp=arr[i];
arr[i]=arr[minIdx];
arr[minIdx]=temp;
}
return arr;
}
}
3. 삽입 정렬
삽입 정렬은 버블 정렬의 비효율성을 개선하기 위해 등장한 방법이다.
두번째 인덱스부터 시작해서 자신의 앞에 있는 값들과 비교하여 적절한 위치를 찾아 넣어주는 형식으로 진행된다.
정렬을 위해 비교하는 범위 자체가 훨씩 적고, 이미정렬되어 있는 경우 앞에 노드보다 큰지 한번씩 밖에 비교를 하지 않아
시간 복잡도는 O(n)까지 줄어든다.
삽입 정렬
- 장점
입력으로 들어오는 배열의 원소가 정렬되어 있을수록 속도가 빠르다.
정렬된 값은 교환이 일어나지 않는다.
- 단점
삽입을 구현해야하므로 속도가 자료구조의 영향을 많이 받는다.
입력으로 들어오는 배열이 역순으로 정렬된 경우 성능이 굉장히 좋지 않다.
public class InsertSort {
public int[] sol(int[] arr){
int k=arr.length;
for(int i=1;i<k;i++){
int temp;
for(int j=i;j>0;j--){
if(arr[j-1]>arr[j]){
temp=arr[j-1];
arr[j-1]=arr[j];
arr[j]=temp;
}
}
}
return arr;
}
}
*위의 세 정렬에 대한 성능표
반복문을 도는 횟수는 Bubble=Selection>=Insert
정렬 알고리즘
최적의 경우(오메가)
평균적인 경우(델타)
최악의 경우(빅오)
Bubble sort
n^2
n^2
n^2
Selection Sort
n^2
n^2
n^2
Insertion Sort
n
n^2
n^2
- 정리
버블정렬과 선택정렬은 단순하고 직관적이며, 구현이 쉽지만, 비효율적이므로 잘 사용하지 않는다.
삽입정렬은 정렬이 어느정도 되어있는 경우에 최소한의 비교와 연산이 이루어지므로, 성능이 좋아 사용된다.
import java.util.PriorityQueue; //import
//int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
//String형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>();
//String형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
2) Priority Queue 값 추가
priorityQueue.add(1); // priorityQueue 값 1 추가
priorityQueue.add(2); // priorityQueue 값 2 추가
priorityQueue.offer(3); // priorityQueue 값 3 추가
자바의 우선순위 큐에 값을 추가하고 싶다면 add(value) 또는 offer(value)라는 메서드를 활용하면 된다.
add() : 삽입에 성공하면 true를 반환, 큐가 꽉 찬 경우 IllegalStateException을 발생
offer() : 값 추가 성공 시에 true를 반환, 값 추가 실패 시 false를 반환
3) Priority Queue 값 삭제
priorityQueue.poll(); // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.remove(); // priorityQueue에 첫번째 값 제거
priorityQueue.clear(); // priorityQueue에 초기화
poll() : 큐가 비어 있을 경우 null 반환
remove() : 큐가 비어 있는 경우 NoSuchElementException 에러 발생
clear() : 큐 비우기
4) Priority Queue에서 우선순위가 가장 높은 값 출력
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();//int형 priorityQueue 선언
priorityQueue.offer(2); // priorityQueue에 값 2 추가
priorityQueue.offer(1); // priorityQueue에 값 1 추가
priorityQueue.offer(3); // priorityQueue에 값 3 추가
priorityQueue.peek(); // priorityQueue에 첫번째 값 참조 = 1
배열은 내부 인덱스를 이용하여 자료의 검색이 한번에 이루어지기 때문에 빠른 검색 속도를 보이는 반면
데이터의 삽입, 삭제 시 많은 데이터가 밀리거나 빈자리를 채우기 위해 이동해야하기 때문에 많은 시간이 소요된다. 반면에 연결리스트는 삽입, 삭제 시 인근 노드들의 참조값만 수정해줌으로써 빠른 처리가 가능했었다. 단, 처음 노드 마지막 노드 이외의 위치에서 데이터를 삽입, 삭제할 경우나 데이터를 검색할 경우에는 해당 노드를 찾기 위하여 처음부터 순회 검색을 해야하기 때문에 데이터의 수가 많아질수록 효율이 떨어질 수 밖에 없는 구조다. 이러한 한계를 극복하기 위하여 제시된 방법이 바로 해시(Hash)이다.
2. 해시란?
해시는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 가진다. 그리고 데이터의 삽입과 삭제 시 기존 데이터를 밀어내거나 채우는 작업이 필요없도록 특별한 알고리즘을 이용하여
데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다.
특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기때문에 삽입 시 다른 데이터의 사이에 끼어들거나 삭제 시 다른 데이터로 채울 필요가 없으므로 삽입과 삭제 시 데이터의 이동이 없도록 만들어진 구조이다.
* 해시의 특징
해시는 검색과 저장에서 아주 우수한 성능을 보인다
해시의 핵심은 KEY, VALUE를 함께 저장하는 자료구조이다.
3. 해시의 충돌
key를 해시함수를 통해서 해시코드로 변환시키고 이 해시코드를 인덱스로 사용하여 value를 저장하는데,
이때 충돌(Collision)이 발생할 수 있다. 다음의 예시를 보자.
해시 충돌
John Smith와 Sandra Dee라는 key가 해시함수를 통해 해시코드로 변환되었는데 우연히 같은 코드로 변환된 것이다. 해시충돌은 완벽히 피할수는 없지만 개선방법은 2가지 존재한다.
1) 충돌해결 - Separate Chaining 기법
Chaining 기법
John Smith가 들어가 있는데 그 공간에 또 Sandra Dee가 들어갈 때 Collision이 발생한다. 이 때 Sandra의 value를 기존 John의 뒤에 연결리스트를 이용해 체인처럼 이어 붙혀준다. 152번지에 John과 Sandra의 정보가 함께 존재하도록 한것이다.
* 장점
한정된 저장공간을 효율적으로 사용할 수 있다.
해시함수에 대한 의존성이 상대적으로 적다.
메모리 공간을 미리 잡아 놓을 필요가 없다.(그때그때 이어붙이기 때문)
* 단점
한 Hash에만 자료가 계속들어간다면(쏠린다면) 검색 효율이 떨어진다.(최악의 경우 O(n))
외부 저장공간을 사용한다.
2) 충돌해결 - Open Addressing(개방주소법) 개방주소법은 데이터의 해시(hash)가 변경되지 않았던 Chaining과는 달리 비어있는 해시를 찾아 데이터를 저장하는 기법이다. 즉, 해시 충돌이 일어나면 다른 버킷에 데이터를 삽입한다.
따라서 개방주소법에서의 해시테이블은 1개의 해시와 1개의 값이 매칭되어 있는 형태로 유지된다.
Open Addressing 기법 중 선형 탐색
* 장점
추가 저장공간이 필요없다.
저장할 데이터가 적을 때 더 유리하다.
* 단점
해시 함수의 성능에 전체 해시테이블의 성능이 좌지우지 된다.
데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해 두어야한다.
* 개방주소법 3가지 방법 ① 선형 탐색(Linear Probing) : 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다. ② 제곱 탐색(Quadratic Probing) : 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4, 9.16...) ③ 이중 해시(Double Hashing) : 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.
4. HashMap vs HashTable(파이썬에서는 Dictionary)
1) HashMap
null을 key, value로 사용할 수 있다.
동기화를 지원하지 않는다.(멀티스레드가 동시에 사용할 때 문제가 발생할 수 있다) => 대신 실행속도가 빠르다.
2) HashTalbe
key가 null이 될 수 없다.
value가 null이 될 수 없다.
동기화를 지원
=>HashMap은 HashTalbe의 신버전
5. HashMap vs HashSet
1) 정의 HashMap은 Map 인터페이스의 구현체로, HashTable과 유사한 자료구조로 데이터를 저장한다. HashSet은 Set 인터페이스의 구현체로, 내부적으로 HashMap을 사용하기 때문에 HashTable과 유사한 자료구조로 데이터를 저장한다.
2) 데이터 저장 형태 HashMap은 Key-Value 쌍 형태로 데이터를 저장하며, Key와 Value의 mapping을 유지하고 있다. HashSet은 객체 그 자체를 저장한다. 위에서 HashMap을 내부적으로 사용한다고 했는데, Key 값으로는 삽입되는 객체 그 자체를, Value 값으로는 HashSet 내부 구현 코드에서 미리 선언해둔 dummy 객체를 사용한다.
3) 중복 허용 여부 HashMap은 중복 key 값을 허용하지 않지만, Value값은 허용한다. HashSet은 객체 자체를 데이터로 저장하기 때문에 중복을 허용하지 않는다.
4) 기본적인 사용법
- HashMap
HashMap<Integer,String> map = new HashMap<>();//new에서 타입 파라미터 생략가능
map.put(1,"사과"); //값 추가
map.put(2,"바나나");
map.remove(1); //key값 1 제거
map.clear(); //모든 값 제거
//반복문을 이용한 출력
//entrySet() 활용
for (Entry<Integer, String> entry : map.entrySet()) {
System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:바나나
//[Key]:3 [Value]:포도
//KeySet() 활용
for(Integer i : map.keySet()){ //저장된 key값 확인
System.out.println("[Key]:" + i + " [Value]:" + map.get(i));
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:바나나
//[Key]:3 [Value]:포도
//keySet().iterator()
Iterator<Integer> keys = map.keySet().iterator();
while(keys.hasNext()){
int key = keys.next();
System.out.println("[Key]:" + key + " [Value]:" + map.get(key));
}
- HashSet
HashSet<Integer> set = new HashSet<Integer>();//HashSet생성
set.add(1); //값 추가
set.add(2);
set.remove(1);//값 1 제거
set.clear();//모든 값 제거
//출력
Iterator iter = set.iterator(); // Iterator 사용
while(iter.hasNext()) {//값이 있으면 true 없으면 false
System.out.println(iter.next());
}
//검색
System.out.println(set.contains(1)); //set내부에 값 1이 있는지 check : true
