1. Array
- 여러개의 데이터를 한 번에 다룰 수 있다.
- Object는 아니지만 Reference Value로 취급된다.
- 메모리상에 연달아 공간을 확보한다.
- 미리 공간을 확보해 놓고 써야한다. - 단점
- 한 번 만들어진 공간은 크기가 고정된다. - 단점
- 첫 번째 위치만 알면 index로 상대적 위치를 빠르게 찾을 수 있다.
-> array의 단점을 보완하기 위해 list가 등장
- System.out.println(Arrays.toString(배열명))을 이용해야 배열의 내용 출력 가능
2. List
- 데이터를 추가: link를 늘린다.
- LinkedList: 데이터를 서로 Link로 연결한다.
- 데이터 삭제: link를 없앤다.
- 양쪽으로 연결: double linked list
- 메모리상에 연속되지 않아도 된다. - 장점
- 미리 공간을 확보하지 않아도 된다. - 장점
- 필요에 따라 데이터가 늘어나거나 줄어든다. - 장점
- 첫 번쨰 위치로부터 index로 목표 위치를 알려면 한 칸씩 이동하면서 찾아야한다... (느리다)- 단점
3. List interface
- LinkedList, ArrayList(not syncronize), Stack, Vector(syncronize) - thread safe ...는 list를 상속한다.
Ex) List<MyData> list = new Vector<>(); 벡터 타입인데 리스트형으로도 표현 가능 - "다형성"
Ex) List<MyData> list = new ArrayList<>(initial capacity);
-> initial capacity를 처음에 정할 수 있다. add로 원소를 추가하면 자동으로 capacity가 늘어난다.
-> 인덱스로 값을 빠르게 불러올 수 있다. => list.get(index)
Ex) list 만들기
- List에 들어갈 요소를 제너릭으로 지정한다. (제너릭은 기본형 사용 불가) => Integer
List<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(1, 5); // index 1번 자리에 원소'5'를 추가한다. [ 1 5 2 3 ]
list.remove(2); // index 2번에 있는 3 삭제 => [ 1 5 2 ]
System.out.println(list.get(2)); // index 2번에 있는 값을 가져온다.
System.out.println(list.contains(5)); // Integer.valueOf(5) 로 자동 박싱되어 true출력
Ex) 배열로 List 만들기
- 리스트의 데이터 타입과 배열의 데이터 타입이 같아야 만들 수 있다.
Integer[] arr = new Integer[]{1, 2, 3, 4, 5};
List<Integer> list = Arrays.asList(arr);
Ex) List로 List만들기
List<Integer> list1 = Arrays.asList(1, 2, 3, 4, 5);
List<Integer> list2 = new LinkedList<>(list1);- 기존 리스트를 이용해서 동일한 값 가진 새로운 리스트를 만들 수 있다.
Ex) 배열처럼 고정된 크기의 리스트 만들기
- 값을 변경할 수는 있으나 추가나 삭제는 불가능하다.
<hide/>
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
System.out.println(list);
list.set(0, 6);
// list.add(6); // 에러
// list.remove(0); // 에러
System.out.println(list);
}
}Note) 실행 결과
Ex) list 사용방법
- 서로 다른 object끼리 비교한 거라 false출력
- 내용물이 같은지 확인하기 위해 equals를 오버라이딩 해줘야한다.
<hide/>
package first;
import java.util.LinkedList;
import java.util.Objects;
class MyData{
int value;
public MyData(int value) {
this.value = value;
}
static MyData create(int v) {
return new MyData(v);
}
public String toString() {
return "" + value;
}
public boolean equals(Object o) {
if(this == o) return true;
if(o == null || getClass() != o.getClass()) return false;
MyData mydata = (MyData) o;
return value == mydata.value;
}
public int hashCode() {
return Objects.hash(value);
}
}
public class Main {
public static void main(String[] args) {
LinkedList<MyData> list = new LinkedList<>();
list.add(MyData.create(1));
list.add(MyData.create(2));
list.add(MyData.create(3));
System.out.println(list);
System.out.println(list.contains(MyData.create(3)));
// contains는 object의 속성으로 비교하기 때문에 오버라이딩 하지 않으면 false출력
// equals를 오버라이딩하면 true
}
}Note) 실행 결과
Ex) Stream 사용하기
List<String> list = Arrays.asList("A", "B", "C", "D", "E");
String[] arr = list.stream().toArray(String[]::new);
Ex) Immutable List
- 리스트를 함수의 인자로 전달할 때, call by reference로 전달한다.
- 인자를 final로 선언하더라도 리스트 인스턴스의 내용을 변결할 수 있다.
- side-effect를 방지하기 위해 Collections.unmodifiableList를 사용하면 리스트의 내용 자체를 변경하기 못하도록 설정됨.
Ex) 최댓값 인덱스 구하기 (배열)
- 주어진 입력 중, 최댓값을 구하고 최댓값이 위치하는 index구하기
<hide/>
public int [] solution(int[] arr) {
int max = 0;
for(int a : arr) { // 최댓값 구하기
if(a > max) {
max = a;
}
}
int count = 0;
for(int a : arr) { // 최댓값의 개수 count
if(a == max) {
count++;
}
}
int[] answer = new int[count]; // 카운트 크기의 배열 만들기
int index = 0;
for(int i = 0; i < arr.length; ++i) {
if(arr[i] == max) {
answer[index++] = i;
}
}
return answer;
}Ex) 최댓값 인덱스 구하기 (list)
<hide/>
public int [] solution(int[] arr) {
int max = 0;
for(int a : arr) { // 최댓값 구하기
if(a > max) {
max = a;
}
}
List<Integer> list = new LinkedList<>(); // 리스트 만들기
for(int i = 0; i < arr.length; ++i) { // 배열에 인덱스 추가하기
if(arr[i] == max) {
list.add(i);
}
}
// 리스트를 배열로 변환 (배열에 복사)
int [] answer = new int[list.size()];
for(int i = 0; i< list.size(); ++i) {
answer[i] = list.get(i);
}
return answer;
}
Ex) 최댓값 인덱스 구하기 - stream 이욯
<hide/>
import java.util.*;
class Solution{
public int [] solution(int[] arr) {
int max = 0;
for(int a : arr) { // 최댓값 구하기
if(a > max) max = a;
}
List<Integer> list = new LinkedList<>();
for(int i = 0; i < arr.length; i++){
if(arr[i] == max) list.add(i);
}
return list.stream().mapToInt(Integer::intValue).toArray();
// 스트림 이용해서 구하기
// mapToInt를 통해 기본형 int로 바꾼다.
}
}
- 가장 간결한 버전
<hide/>
import java.util.*;
import java.util.stream.*;
class Solution{
public int [] solution(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
// Arrays.stream(arr)를 통해 배열을 스트림으로 만든다.
// max()함수 -> Optional int값이 반환된다.
// getAsInt()로 int값을 구할 수 있다.
return IntStream.range(0, arr.length).filter(i -> arr[i] == max).toArray();
//스트림을 생성하여
// arr[i] == max 인 경우만 꺼내오고
// toArray() 배열을 만든다.
}
}
Ex) 순열 검사: 함수 solution를 통해 길이가 n인 배열에 대해 1~n까지 중복없이 한 번씩 들어가는지 확인
<hide/>
import java.util.*;
public class MaxIndex {
// 프로그램의 시간 복잡도: O( nlog(n) )
public static boolean solution(int[] arr) {
int[] answer = new int[arr.length];
for(int i = 0; i < arr.length; ++i) {
answer[i] = i + 1; // O(n)
}
Arrays.sort(arr); // 배열을 오름차순 정렬 // O( nlog(n) )
return Arrays.equals(answer, arr); // O(n)
}
}
Ex) 자연수 뒤집어서 배열로 만들기
<hide/>
import java.util.*;
class Solution {
public int[] solution(long n) {
List<Integer> list = new LinkedList<>();
while(n > 0){
list.add((int) (n % 10));
n /= 10;
}
return list.stream().mapToInt(Integer::intValue).toArray();
// mapToInt: 스트림을 IntStream으로 변환한다.
}
}- n은 long 타입이기 때문에 나머지도 long이 나온다.
- 따라서, n % 10 을 int형으로 바꾼 다음 add로 추가해야한다.
- 배열의 자릿수가 얼마인지 알 수 없기 때문에 list를 사용한다.
'자료구조와 알고리듬 With Java > [프로그래머스] Algorithm' 카테고리의 다른 글
| Part 04 집합 (Set) (0) | 2022.03.22 |
|---|---|
| Part 03 Map (0) | 2022.03.22 |
| Part 01 시작하기 (0) | 2022.03.21 |
| 동적 계획법, 그리고 알고리즘 (0) | 2022.03.20 |
| 깊이 우선 탐색(DFS, Depth-First Search) (0) | 2022.03.18 |