1. Stack, Queue, List

A. Stack

FILO

import java.util.Stack;

Stack<Integer> st = new Stack<>();
st.push(1);
st.push(2);
st.push(3);
st.pop(); // 가장 마지막에 들어온 값 추출 3
st.peek(); // 가장 윗값 출력: 2
st.clear(); // 스택 전체 비우기
st.size(); // 스택의 크기 출력
st.empty(); // 스택 비었는지 확인(비었으면 true)
st.contains(1); // 스택에 1이라는 값이 있는지 확인

B. Queue

Queue

FIFO
BFS에서 자주 사용
stack에서는 링크드리스트를 불러올 필요가 없지만 Queue를 사용할 땐 필요하다.

import java.util.LinkedList;
import java.util.Queue;

Queue<Integer> q = new LinkedList<>();
Queue<String> q = new LinkedList<>();

q.offer(1);
q.offer(2);
q.offer(3);
q.add(4); // add, offer 모두 큐에 값을 집어넣을 수 있음
q.poll(); // q에 제일 처음 들어간 값 반환 후 삭제 -> 1
q.remove(); // queue의 제일 아랫값 제거
q.peek(); // 제일 아랫값 return, 삭제하진 않음
q.clear(); // 큐 전체 비우기
q.size(); // 큐 사이즈 리턴

PriorityQueue

import java.util.PriorityQueue;
import java.util.Collections;

//작은 숫자순 정렬 [1, 3, 7, 8, 15]
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

//큰 숫자순 정렬 [15, 8, 7, 3, 1]
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

priorityQueueLowest.add(10); // 큐에 넣기
priorityQueueHighest.offer(100);


// 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueueLowest.poll();

// 첫번째 값 제거 비어있다면 예외 발생
priorityQueueLowest.remove(); 

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 null을 반환
priorityQueueLowest.peek();

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 예외 발생
priorityQueueLowest.element();
// 큐 비우기
priorityQueueLowest.clear(); 

// 리스트가 원소인 우선순위 큐 정렬하기 (Comparator를 오버라이딩 하는 방법)
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
	@Override
		public int compare(int[] o1, int[] o2) {
			// 만일 2차원 배열의 첫 번째 원소가 같다면, 2번째 원소를 기준으로 내림차순 정렬한다.
			if(o1[0] == o2[0]) {
				return Integer.compare(o2[1], o1[1]);
			}
			// 2차원 배열의 첫 번째 원소를 기준으로 오름차순 정렬한다.
			return Integer.compare(o1[0], o2[0]);
		}
	});
pq.offer(new int[] {5, 2});
pq.offer(new int[] {3, 3});
pq.offer(new int[] {1, 4});
pq.offer(new int[] {1, 5});
pq.offer(new int[] {7, 5});

while(!pq.isEmpty()) {
	System.out.println(Arrays.toString(pq.poll())); // [1, 5], [1, 3], [3, 3], [5, 2], [7, 5]
}

https://sskl660.tistory.com/93

C. List

list는 메모리의 크기가 고정되어있지만, arraylist는 파이썬의 리스트처럼 크기가 고정되어 있지 않다.

리스트 정렬 (sort) 오름차순, 내림차순으로 정렬하기

import java.util.;

Integer[] arr = {4, 3, 0, 2, 1};

// 오름차순 정렬
Arrays.sort(arr); // [0, 1, 2, 3, 4]
Arrays.sort(arr, (s1, s2)->s1-s2;);
// 내림차순 정렬
Arrays.sort(sortNumArr1, Comparator.reverseOrder());

list 출력

System.out.println(Arrays.toString(arr));

D. ArrayList

List<String> list = new ArrayList<>();
list.add("apple");
list.add("nvidia");
list.add("tesla");
list.add("samsung");

Collections.sort(list);
System.out.println(list);  // ["apple", "nvidia", "samsung", "tesla"]
Collections.sort(list, Collections.reverseOrder());
System.out.println(list); // ["tesla", "samsung", "nvidia", "apple"]

E. HashMap

https://crazykim2.tistory.com/587
https://www.notion.so/9-230619-1-3-cc7a93cac29c4cf9b3719ba2a7db3f7d
java iterator

import java.util.HashMap;

Map<String, Integer> map = new HashMap<>();

map.put("apple", 1);
map.put("banana", 3); // 원소 넣기
map.containsKey("apple"); // true
map.get("banana"); // 3

for (String key: map.keySet()) {
	
}

Collection<String> values = new Collection<>();

F. 중복 제거 테크닉

https://hianna.tistory.com/582

set 이용

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

List<String> li = Arrays.asList("a", "b", "c", "a");

// 리스트를 해시셋으로 변환
Set<String> set = new HashSet<String>(li);

// 해시셋을 다시 리스트로 변환
List<String> hl = new ArrayList<String>(set);
System.out.println(newList); // ["a", "b", "c"]

Stream distinct() 이용

자바 8부터 가능하다

2. get Input/Output

A. input

2. 알고리즘 정리

A. bfs/dfs

bfs

import java.util.LinkedList;
import java.util.Queue;


public class Main
{
	public static void main(String[] args) {
		int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
		boolean[] visited = new boolean[9];
		System.out.println(bfs(1, graph, visited));
	}
	
	public static String bfs(int start, int[][] graph, boolean[] visited) {
	    StringBuilder sb =new StringBuilder();
	    Queue<Integer> q = new LinkedList<Integer>();
	    q.offer(start);
	    
	    visited[start] = true;
	    while (!q.isEmpty()) {
	        int newnode = q.poll();
	        sb.append(newnode+" -> ");
	        for (int i=0; i<graph[newnode].length; i++) {
	            int tmp = graph[newnode][i];
	            if (!visited[tmp]) {
	                visited[tmp] = true;
	                q.offer(tmp);
	            }
	        }
	    }
	    return sb.toString();
	}
}

dfs

public class Main
{
    static boolean[] visited = new boolean[9];
    static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
    
	public static void main(String[] args) {
		dfs(1);
	}
	
	static void dfs(int index) {
	    visited[index]=true;
	    System.out.println(index+" -> ");
	    
	    for (int node: graph[index]) {
	        if (!visited[node]) {dfs(node);}
	    }
	}
}

B.