자바로 코딩테스트 부시기

 

1. 특정 배열에 값들을 넣을 때, 중복 없이 넣는 방법

ArrayList를 선언하고 특정 값이 value라고 할 때

if (arrayList.indexOf(value) < 0)
	ArrayList.add(value);

ArrayList에 indexOf 함수는 특정 value가 없으면 -1을 리턴하기 때문에

위 예제는 어레이 리스트에 이 값이 없을 때만 add 하겠다는 뜻입니다.

 

2. 어레이리스트의 값을 하나씩 가져와서 배열에 넣을 때

String 형태면 for문을 돌리면서 arr[i] = list.get(i) 하면 되는데,

int 형태라면 arr[i] = list.get(i).intValue(); 라고 해줘야 합니다.

 

3. 특정 정수를 잘라서 사용하고 싶을 때

123이라는 정수를 1, 2, 3으로 나눠 생각하고 싶을 때

3을 뽑고 싶으면 123 % 10 을 하면 됩니다. 그리고 123 / 10을 한 것, 즉 12가 다음 숫자가 됩니다.

그다음 12 % 10 -> 2 -> 12 / 10 -> 1입니다.

while(value != 0) {
	remain = value % 10;
    value /= 10;
}

 

4. 문자열(String)을 자르는 방식

첫 번째는 String[] arr = str.split(" ");

두 번째는 str.substring();

세 번째는 charAt();

 

5. 배열을 자르려면 어떻게?

스트링은 str.substring(3, 5) 이런 식으로 원하는 부분만 뽑아낼 수 있는데, 배열은 substring이 불가능합니다.

대신 Arrays.copyOfRange() 메서드를 통해 복사합니다.

Arrays.copyOfRange(원본배열, 시작, 끝) 이렇게 사용 가능합니다.

 

6. 배열 특정 값의 index 리턴 받기 혹은 배열 항목 검색

Arrays.sort() 메서드로 정렬을 한 후에,

Arrays.binarySearch() 메소드로 원하는 항목의 인덱스 값을 찾을 수 있습니다.

정렬을 하지 않은 후에 binarySearch() 메서드를 사용하거나, 없는 항목을 찾으면 음수 값이 리턴됩니다.

Member[] members = {"aa", "bb", "cc"}; // 일 때

Arrays.sort(members);
int idx = Arrays.binarySearch(members, "bb");

 

7. 배열을 어레이 리스트로 변환할 때

ArrayList list = Arrays.asList(arr);

 

8. Dynamic Programming (DP) 문제 해결방법

1. 보통 누적되어 최댓값이 되는 문제는 DP라고 의심해봐야 합니다.
2. 먼저 특정 지점 i번째 에서의 식을 생각해봅니다.
3. 점화식의 형태로 간단하게 특정 지점에서의 식을 완성해봅니다.
4. 이때 예를 들어 DP[i] = max(DP[i - 1], DP[i - 2] + arr[i]) 이런 점화식을 완성했다면 DP는 첫 번째 값부터 for문 돌리면서 누적 값을 구하는 형태인 경우가 많기에 가장 초기값 DP[0]을 지정해줘야 합니다. 그리고 for문의 i는 1부터 도는 경우가 많습니다.

9. DFS, BFS 문제 유형 파악하기

1. DFS, BFS의 개념적인 의미
   • DFS - 스택이나 재귀 함수로 풀 수 있습니다.
     
     • 한 노드에서 갈 수 있는 노드 중 하나를 선택합니다.
     • 선택한 노드에서 갈 수 있는 노드 중 하나를 선택합니다. 이때 이미 방문한 노드는 제외하고 선택합니다.
     • 갈 수 있는 노드가 존재하지 않으면 이전 노드로 돌아와서 갈 수 있는 노드 중 하나를 선택합니다.
       • 위의 시퀀스가 반복되며 경로를 탐색한다.
   • BFS - 큐로 풀 수 있습니다.
     • 한 노드에서 갈 수 있는 노드를 큐에 추가합니다.
     • 큐에서 노드를 하나 꺼내어 꺼낸 노드에서 갈 수 있는 노드를 큐에 추가합니다.
     • 큐에 노드가 존재하지 않으면 break 합니다.
       • 위의 시퀀스가 반복되며 경로를 탐색합니다.
   • 기본적으로 최소 거리는 BFS를 사용합니다. 목적지를 찾은 순간 최소거리라는 것이 보장되는 알고리즘이기 때문입니다.
   • DFS는 가능한 모든 경로를 탐색하여 경로를 찾을 때 씁니다.
   • DFS는 한 노드에서 끝까지 꼬리를 물고 탐색하지만 BFS는 점진적으로 물의 파장처럼 탐색합니다.
2. DFS 간단 구현 코드
   • 방문 배열을 만들고 이미 true 라면 패스, false 일 땐 true로 바꾸고 다음 노드로 다시 재귀 함수를 호출합니다.

   • public static void DFS(int node, boolean[] visited) {
     	if (visited[node]) return;
         
         visited[node] = true;
         
         for (int nextNode : nodeList[node]) {
         	DFS(nextNode, visited, sb);
         }
     }

3. BFS 간단 구현 코드
   • 큐에 시작 노드의 자식 노드를 넣는다. 특정 노드를 꺼낼 때 그 자식 노드를 큐에 넣는다고 생각하면 됩니다.

   • public static void BFS(int node, boolean[] visited) {
     	Queue<Integer> queue = new LinkedList<Integer>();
         
         queue.offer(node);
         
         while(!queue.isEmpty()) {
         	node = queue.poll();
             
             if (visited[node]) continue;
             
             visited[node] = true;
             
             for (int nextNode : nodeList[node]) {
             	queue.add(nextNode);
             }
         }
     }

4. Node 클래스를 사용하여 좌표를 따라가는 BFS 최단거리 응용문제
   • 예를 들어 특정 경로의 정보가 담긴 2차원 배열을 주고 최단거리를 찾는 유형의 문제는 BFS로 풀어야 합니다.
   • 기본 맵에 대한 정보를 이차원 배열에 담고 방문 여부를 따지는 이차원 배열도 선언합니다.

   • static class Node {
     	int x, y, depth;
         Node(int x, int y, int depth) {
         	this.x = x;
             this.y = y;
             this.depth = depth;
         }
     }

   • Depth는 문제마다 필요하면 쓰고 아님 안 씁니다.

   • static void BFS(int a, int b) {
     	Queue<Node> q = new LinkedList<>();
         q.offer(new Node(a, b, 1));
         
         while(!q.isEmpty()) {
         	Node node = q.poll();
             visited[node.x][node.y] = true;
             
             for (int i = 0; i < 4; i++) {
             	int nx = node.x + dx[i];
                 int ny = node.y + dy[i];
                 
                 if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
                 	if (map[nx][ny] == 1 && !visited[nx][ny])
                     	q.add(new Node(nx, ny, node.depth+1));
                 }
             }
             if (visited[row-1][col-1] {
             	System.our.println(node.depth);
                 break;
             }
         }
     }​

10. 정렬

Arrays.sort

Arrays.sort는 int나 char 같은 Primitive type 배열에서 정렬을 지원합니다. (String은 예외로 가능합니다)

이 함수의 정렬 알고리즘은 Dual Pivot Quick sort라고 합니다. Quick sort가 정렬되어있는 상태에서는 O(n^2)의 시간 복잡도를 가진다는 문제점을 보완하고 속도도 더 빠르다고 합니다.

변수에 새로 선언하는 것이 아니라 현재 저장되어 있는 변수를 그대로 사용하고 내부적으로 정렬을 수행합니다.

import java.util.Arrays;
int[] numbers = {5, 2, 8, 10, 6, 9};
Arrays.sort(numbers);

 

내림차순 성렬

내림차순 정렬을 위해서는 Primitive type이 아니라 Wrapper 클래스로 선언해야 합니다.

그 이유는 Collections에 도움을 받아야 하기 때문입니다.

Collections.reverseOrder()을 추가 인자로 넣으면 됩니다.

import java.util.Arrays;
import java.util.Collections;

// Wrapper 클래스를 활용하여 선언
Integer[] numbers = {5, 2, 8, 10, 6, 9};

Arrays.sort(numbers, Collections.reverseOrder());

 

Collections.sort

Collections.sort는 ArrayList, LinkedList와 같은 Collection 타입의 정렬을 지원합니다.

이 함수의 정렬 알고리즘은 merge sort입니다.

그 이유는 quick sort와 달리 merge sort는 stable 한 정렬이기 때문입니다.

Stable한 정렬은 같은 Key 값을 가진 Node가 정렬 전과 정렬 후의 위치가 달라지지 않는다는 의미라고 합니다.

int 같은 경우, 같은 값이 여러 개 있을 때 해당 숫자는 서로 위치가 달라져도 문제 될 것이 없기에 Quick sort를 사용하면 됩니다.

내림차순 정렬은 Arrays.sort 대신 Collections.sort만 사용하면 됩니다.

import java.util.Collections;
import java.util.ArrayList;

ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(5); nums.add(2); nums.add(8);
nums.add(10); nums.add(6); nums.add(9);

Collections.sort(nums);
// Collections.sort(nums, Collections.reverseOrder());

 

11. 해시와 링크드 해시 

HashMap<String, Integer> hm = new HashMap<>();

이렇게 선언합니다.

값 추가는 hm.put("영범", 10);

값 변경은 hm.put("영범", 20);  // Key 기준이라 그냥 그대로 put 하면 값이 변경됩니다.

값 삭제는 hm.remove("영범");

 

Key, Value 값 for 문으로 뽑아내기

for (String ket : hm.keySet()) {
	System.out.println(key);		// Key 값
    System.out.println(hm.get(key);	// Value 값
}

그런데 이렇게 for문으로 뽑으면 순서가 랜덤으로 나옵니다.

만약 put 한 순서대로 뽑고 싶다면 LinkedHashMap으로 선언하면 됩니다.

LinkedHashMap과 TreeMap
Map의 가장 큰 특징은 순서에 의존하지 않고 Key로 Value를 가져오는데 있습니다.
하지만 가끔은 Map에 입력된 순서대로 데이터를 가져오고 싶은 경우도 있고 때로는 입력된 Key에 의해 정렬된 데이터를 가져오고 싶을 수도 있습니다.
이런 경우에는 LinkedHashMap과 TreeMap을 사용하는 것이 유리합니다.

- LinkedHashMap은 입력된 순서대로 데이터가 출력되는 특징을 가지고 있습니다.
- TreeMap은 입력된 Key의 정렬순으로 데이터가 출력되는 특징을 가지고 있습니다.

// 배열에 있는 스트링을 해시맵에 넣는데 Key가 없으면 1로, 있으면 그 벨류 +1로 넣는다
for (String par : participant)
	hm.put(par, hm.getOrDefault(par, 0) + 1);

배열에 담겨있는 스트링을 차례로 담으면서 getOrDefault 쓰는 예제

HashMap의 경우 같은 Key에 해당되면 값이 그대로 덮어쓰기가 되어버립니다.

근데 같은 Key값이면 Value를 하나씩 늘리거나 빼고 싶은 경우가 생깁니다.

동일한 이름의 Key를 가지고 있다면 인원수 value를 1씩 증가 시키는 등등

이런 경우에는 getOrDefault(key, defaultValue)라는 메소드를 씁니다.

Object getOrDefault(Object key, Object defaultValue)

지정된 키의 값을 반환한다. 키가 없을 경우, default value로 지정된 데이터를 반환한다.

for (String key : hm.keySet())
	hm.put(key, getOrDefault(key, 0) + 1);

keySet() 에서 Key를 받아와서 해시맵에 해당 키가 있으면 value 값 가져와서 1 추가해주고, 없으면 기본값 설정해둔 0을 반환합니다.

 

entrySet() : 엔트리 객체로 이루어진 Set을 리턴

keySet을 가져오는 것보다 내부의 entrySet 자체를 가져오는게 더 빠릅니다.

 

12. StringBuffer 클래스 이용하기

그냥 String 클래스는 공간, 시간 낭비도 심한데 StringBuffer 클래스를 활용하면 낭비도 줄이고 다음과 같은 메소드도 코테에서 유용하게 사용이 가능합니다.

delete 메서드

delete 메서드는 전달된 인덱스에 해당하는 부분 문자열을 해당 문자열에서 제거합니다.

또한, deleteCharAt 메서드를 사용하면 특정 위치의 문자 한 개 만을 제거할 수도 있습니다.

StringBuffer str = new StringBuffer("java Oracle");
System.out.println("원본 문자열: " + str);

System.out.println(str.delete(4, 8));
System.out.println(str.deleteCharAt(1));
System.out.println("delete(), CharAt() 메소드 호출 후 원본 문자열 : " + str);

 

insert 메서드

insert 메서드는 인수로 전달된 값을 문자열로 변환한 후, 해당 문자열의 지정된 인덱스 위치에 추가합니다.

이 때 전달된 인덱스가 해당 문자열의 길이와 같으면, append() 메소드와 같은 결과를 반환합니다.

StringBuffer str = new StringBuffer("Java 만세!");
System.out.println("원본 문자열 : " + str);

System.out.println(str.insert(4, "Script"));
System.out.println("insert 메소드 호출 후 원본 문자열 : " + str);

 

append 메서드

StringBuffer sb = new Stringbuffer();
sb.append("Hello");
sb.append(" ");
sb.append("Java");
System.out.println(sb.toString());

 

13. Comparator를 이용한 Arrays.sort() 커스터마이징

Arrays.sort(arr, new Comparator<String>() {
	@Override
    public int compare(String s1, String s2) {
    	// 단어 길이가 같을 경우
        if (s1.length() == s2.length()) {
        	return s1.compareTo(s2); // 사전 순 정렬
        } 
        else {
        	return s1.length() - s2.length();
        }
    }
});

// 절댓값 우선순위 큐
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
	@Override
    public int compare(Integer a, Integer b) {
    	if (Math.abs(a) < Math.abs(b))
        	return -1;
        else if (Math.abs(a) > Math.abs(b))
        	return 1;
        else return a - b;
    }
});

 

14. 순열 Permutation 사용하기

먼저 순열이란 중복을 허락하지 않는 것이기 때문에 중요한 건 visited[] 를 이용해서 방문했는지 여부를 체크하는 것입니다.

1. 순열을 담을 배열 arr[], 반문채크 할 visited[]를 전역으로 처리합니다.

   • public static int[] arr;
     public static boolean[] visited;

2. 두개의 정수를 받는다. (N개 중에서 M개를 중복없이 뽑느다.)
3. 방문 배열을 false 로 초기화하고 permutation(0)을 호출한다.
4. permutation(int depth)로 구성되는데 depth가 M이 되면 종료한다.
5. depth가 아직 M이 아니라면 총 N개의 경우만큼 for문을 돌리면서 현재 idx에서 방문 배열이 false라면 true로 바꾸면서 값을 채워줍니다. 그 다음 재귀함수를 depth + 1로 호출합니다. 이때 depth++로 하면 depth--를 해줘야 하므로 depth + 1로 하는 것이 편합니다. 재귀 호출하면 다시 visited 방문 배열을 false로 바꿔줘야 합니다.

   • for(int i = 0; i < N; i++) {
     	if (!visited[i]) {
         	visited[i] = true;
             arr[depth] = i + 1;
             permutation(N, M, depth + 1);
             
             // 재귀 호출 하고 다시 원상태로 돌려놔야 한다! 중요하다!
             visited[i] = false;
         }
     }

 

15. 조합 combination 사용하기

조합은 순열 중에서 순서 상관없이 같은 숫자가 포함되어 있으면 다 똑같은 것으로 생각합니다.

근본적으로 순열과 구조는 거의 동일한데, 사실상 오름차순으로 뽑는 것과 유사합니다.

1. 먼저 조합을 담을 배열 arr[], 방문 체크할 visited[], 그리고 숫자 N, M을 전역으로 선언하여 함수 넘길 때 간결하게 합니다. 또한 arr의 크기는 M, visited의 크기는 N으로 해야합니다.
2. 두개의 정수를 받고 방문 배열을 초기화 합니다.
3. Combination(0, 0)을 호출합니다.
4. Combination(int depth, int position)에서 depth는 M이 되면 출력할 때 쓰이고 Position은 이미 뽑은 놈은 다시 안뽑기 위해 위치를 지정해줍니다.
5. 출력하는 부분이 조금 다릅니다. 오름차순이 아닌건 거르고 출력합니다.
   • 거를 때 return 으로 없애버리는게 핵심 

   • if (depth == M) {
     	for (int i = 0; i < arr.length - 1; i++) {
         	if (arr[i] > arr[i + 1]) return;
         }
         for (int i = 0; i < arr.length; i++) {
         	System.out.println(arr[i]);
         }
         System.out.ptintln();
         return;
     }

6. for 문 돌릴 때 i = position으로 돌리는 것이 핵심입니다.

   • for (int i = position; i < N; i++) {
     	if (!visited[i]) {
         	visited[i] = true;
             arr[depth] = i + 1;
             combination(depth + 1, position + 1);
             visited[i] = false;
         }
     }

16. 행렬의 곱

N M 행렬, M K 행렬을 곱하면 결과는 N K 크기의 행렬이 만들어 집니다.

for (int i = 0; i < N; i++) {
	for (int j = 0; j < K; j++) {
    	for (int k = 0; k < M; k++) {
        	result[i][j] += (A[i][k] * B[k][j]);
        }
    }
}

---

레퍼런스

https://velog.io/@alstjdwo1601/Java-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EA%B4%80%EB%A0%A8-%ED%8C%81

https://pangsblog.tistory.com/56

https://freestrokes.tistory.com/87

https://codechacha.com/ko/java-map-hashmap/

https://codevang.tistory.com/289

https://st-lab.tistory.com/112

 

[백준] 1181번 : 단어 정렬 - JAVA [자바]

프로그래머스_해시_완주하지 못한 선수 (JAVA)

Java - HashMap 사용 방법 및 예제

Java 인접행렬과 인접리스트를 이용하여 그래프 구현하기

[백준 1260] - [DFS BFS] DFS와 BFS (JAVA)

Java 코딩테스트 관련 팁