(썸네일은 백준 1854 K번째 최단경로 찾기 풀이의 일부이다 http://boj.kr/499d133a83384b8c803ee0b7d085f9a7)
코테 문제를 풀어본 지 너무 오래되어 재활을 위해 자바로 코테를 풀 때 필요한 함수 등을 정리하고자 한다.
1. 입출력과 형변환
(1) 빠른 입출력
기본 입출력과 빠른 입출력이 있는데, 항상 빠른 입출력을 쓰면 입출력으로 인한 시간초과를 고민할 필요가 없다.
빠른 입력으로는 BufferedReader()를 사용한다. 유의해야 할 점은 다음과 같다.
import java.io.*;로 클래스를 임포트해주어야 한다.- 해당 클래스를 사용하는 메서드에 예외처리(
throws IOException)을 추가해주어야 한다. - 입력을 항상 문자열 형태로 받기 때문에 형변환은 따로 수행해야 한다.
이를 활용해 입력을 수행하는 예시는 다음과 같다.
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 선언
String str = br.readLine(); // 한 줄 입력 받기
}다만 입력을 받을 때 줄바꿈이 아니라 공백으로 구분된 값들을 받아야하는 경우가 있다. 이럴 때는 StringTokenizer()를 사용하면 된다. 해당 클래스를 사용하기 위해서는 import java.util.*;를 추가해주어야 한다. 예시는 다음과 같다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 선언
StringTokenizer st = new StringTokenizer(br.readLine()); // 한 줄 입력 받기
str1 = st.nextToken(); // 첫번째 공백 이전까지의 문자열
str2 = st.nextToken(); // 첫번째 공백 이후의 문자열
}빠른 출력으로는 BufferedWriter()가 있긴 한데, 별로 직관적으로 느껴지지 않아서 StringBuilder()로 출력 형식을 만들어주고, 이를 출력하는 방법을 택했다. 예시는 다음과 같다.
public class Main {
public static void main(String[] args) {
StringBuilder sb = new StringBuilder(); // 선언
sb.append("출력\n"); // 출력 내용 추가
System.out.println(sb); // 출력
}
}빠른 입출력도 그렇고, 뒤에 나올 자료구조도 고려하면 문제 풀기 전에 임포트는 그냥 다 해놓자.
(2) 자료형과 형변환
기본적으로 알아야 할 자료형은 다음과 같다.
int: 일반적으로 정수를 나타낼 때 사용double: 소수를 나타낼 때 사용long:int의 범위를 벗어나는 경우 사용 (-21억~21억을 넘어가는 경우)char: 문자 하나를 나타낼 때 사용String: 문자열을 나타낼 때 사용boolean: 참 또는 거짓을 나타낼 때 사용
int a = 10;
double b = 12.345;
long c = 10000000000L; // int 범위를 벗어나는 경우, 뒤에 L를 적어주어야 함
char d = "D";
String e = "Hello, World!";
boolean f = true;형변환은 크게 문자열을 숫자형 자료로 바꾸는 경우와 그 반대의 경우가 존재한다.
문자열을 숫자로 바꿀 때는 Integer.parseInt()와 같은 해당 자료형 객체의 parse류 메서드를 사용하면 된다.
String num = "10";
int intNum = Integer.parseInt(num); // String to int
long longNum = Long.parseLong(num) // String to long
double doubleNum = Double.parseDouble(num) // String to double숫자 자료형을 문자열로 바꿀 때는 각 자료형 객체의 toString() 메서드를 사용하면 된다.
int intNum = 10;
double doubleNum = 10.123;
String intToString = Integer.toString(intNum); // int to String
String doubleToString = Double.toString(doubleNum); // double to String문자열을 제외한 숫자 자료형과 문자 자료형끼리는 함수를 사용하지 않고 명시적인 형변환을 수행하면 된다.
int num = 65;
char ch = (char) num; // int to char
double (double) num; // int to double2. 자료구조
각 자료구조는 어떤 클래스로 구성할 수 있을지 정도로 간단하게 이야기할 예정이다. 문제를 풀 때 유용하게 사용하는 메서드들이 있는데, 어차피 보통 공식 문서를 볼 수 있으니까 그런건 그때그때 찾아서 사용하자.
(1) 배열, 리스트
배열과 리스트는 선형 자료구조라는 공통점이 있지만, 배열은 최초 선언 시에 설정한 크기를 변경할 수 없는 반면 리스트는 정해진 크기 없이 값을 추가 및 제거할 수 있다.
배열을 선언 및 초기화하는 예시는 다음과 같다.
int[] numArray1 = {1, 2, 3}; // 선언 및 초기화
int[] numArray2 = new int[3]; // 선언
for(int i = 0; i < 3; i++) {
numArray2[i] = i; // 초기화
}리스트로는 기본적으로 ArrayList<>()를 사용한다. 예시는 다음과 같다.
ArrayList<Integer> numList = new ArrayList<>(); // 선언
numList.add(1); // 삽입
numList.get(0); // 해당 인덱스 값 얻기
numList.set(0, 10); // 해당 인덱스 값 변경
numList.remove(0); // 해당 인덱스 값 삭제 (객체로 넣어 해당 값을 삭제하는 방식도 가능)
numList.size(); // 현재 크기 얻기
numList.equals(numList2) // 다른 리스트와 같은지 비교
numList.sort(); // 오름차순 정렬
numList.sort(Comparator.reverseOrder()); // 내림차순 정렬(2) 스택, 큐, 덱
스택은 한 쪽에서 삽입과 삭제가 일어나는 FILO 방식의 자료구조이며, 큐는 한 쪽에서는 삽입, 다른 한 쪽에서는 삭제만 일어나는 FIFO 방식의 자료구조이다. 덱은 양방향에서 삽입 및 삭제가 가능한 자료구조이다.
자바에서는 각각의 자료구조를 제공하고 있지만, 문제를 풀 때는 그냥 ArrayDeque<>()을 선언하고 필요한 방식으로 사용하면 된다.
ArrayDeque<Integer> deq = new ArrayDeque<>(); // 선언
deq.add(1); // 맨 뒤에 값 추가
deq.addFirst(0); // 맨 앞에 값 추가
deq.addLast(2); // 맨 뒤에 값 추기(add와 동일)
deq.pollFirst(); // 맨 앞의 값을 꺼내기
deq.pollLast(); // 맨 뒤의 값을 꺼내기
deq.peekFirst(); // 맨 앞의 값을 확인(덱에서 제거하지 않음)
deq.peekLast(); // 맨 뒤의 값을 확인(덱에서 제거하지 않음)
deq.size(); // 현재 크기 얻기
// 큐처럼 사용하기
deq.add(); // 삽입
deq.poll(); // 꺼내기
deq.peek(); // 확인
// 스택처럼 사용하기
deq.push(); // 삽입
deq.pop(); // 꺼내기(3) 우선순위 큐(힙)
우선순위 큐는 정해진 우선순위(기본은 오름차순; 작은 숫자가 먼저 나옴)에 따라 내부에서 값을 정렬하여 값을 얻게 해주는 자료구조이다. PriorityQueue<>()로 사용하면 된다.
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 선언
pq.add(5); // 삽입
pq.poll(); // 꺼내기
pq.peek(); // 확인
pq.size(); // 현재 크기 확인
pq.isEmpty(); // 크기가 0인지 확인복잡한 자료구조를 넣는 등의 이유로 우선순위를 변경하고 싶다면, PriorityQueue를 선언할 때 Comparator의 compare 함수를 오버라이드하면 된다.
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[1], o2[1]); // 오름차순; 작은 값이 우선
}
});이때 각 자료형 클래스의 compare 메서드를 사용하면 오름차순과 내림차순을 직관적으로 나타낼 수 있다.
(4) 셋, 맵(딕셔너리)
셋과 맵은 중복을 허용하지 않는 자료구조라는 공통점이 있다. 다만 맵은 key와 value라는 쌍으로 구성되며, key의 중복만 허용하지 않는다.
셋은 HashSet<>()을 이용하여 구성한다.
HashSet<Integer> numSet = new HashSet<>(); // 선언
numSet.add(1); // 삽입
numSet.remove(1); // 삭제
numSet.contains(1); // 해당 값 보유 여부 확인
numSet.size(); // 현재 크기 확인
numSet.clear(); // 빈 집합으로 초기화
numSet.isEmpty(); // 크기가 0인지 확인맵은 HashMap<>()을 이용하여 구성한다.
HashMap<String, Integer> numMap = new HashMap<>(); // 선언
numMap.put("First", 1); // 삽입 또는 해당 key의 값 수정
numMap.get("First"); // 해당 key의 value 얻기
numMap.getOrDefault("First", 0) // 해당 key의 value를 얻기, 만약 해당 key가 없다면 default값을 얻음
numMap.remove("First"); // 해당 key의 값 쌍 삭제
numMap.containsKey("First"); // 해당 key 보유 여부 확인
numMap.size(); // 현재 크기 확인
numMap.clear(); // 빈 집합으로 초기화
numMap.isEmpty(); // 크기가 0인지 확인3. 각종 메서드 및 활용법
(1) 리스트 배열
각종 알고리즘 문제를 풀다 보면 2차원의 숫자 배열에서 한 차원으로는 크기가 정해져있고, 다른 차원은 크기가 변하는 구조가 필요한 경우가 있다. 이는 그래프의 전체 노드 개수는 정해져 있고, 각 노드에 연결된 다른 노드를 기록하는 경우에서 많이 나타난다. 이럴 때는 배열 내에 리스트가 존재하는 자료구조를 사용하면 된다. 예시는 다음과 같다.
int n = 10;
ArrayList<Integer>[] graph = new ArrayList[n+1]; // 선언
for (int i = 0; i < n+1; i++) {
graph[i] = new ArrayList<>(); // 각 인덱스의 리스트 선언
}위의 예시처럼 각 인덱스마다 리스트를 선언해주어야 에러가 발생하지 않는다.
여기서는 리스트를 배열에 넣어 사용했지만, HashSet이나 HashMap 등의 다른 자료구조도 배열에 넣어서 사용할 수 있다.
(2) 해시맵에 향상된 for문 사용
배열, ArrayList, HashSet은 단순히 자료형만 맞춘 변수로 향상된 for문을 사용할 수 있지만, HashMap에 향상된 for문을 사용하려면 메서드를 활용해야 한다.
이는 key와 value가 모두 필요한 경우, key만 필요한 경우, value만 필요한 경우라는 세 가지 상황으로 나눌 수 있다.
<key, value> 쌍이 필요한 경우에는 entrySet() 메서드, key가 필요한 경우 keySet() 메서드, 그리고 value가 필요한 경우에는 values() 메서드를 사용한다.
다만 key, value 쌍을 받는 entrySet() 메서드는 Map.Entry<key, value> 형태로 리턴하기 때문에 받는 변수의 자료형을 해당 형태로 설정해야 한다.
예시는 다음과 같다.
HashMap<Integer, Integer> map = new HashMap<>();
// <key, value>가 필요한 경우
for (Map.Entry<Integer, Integer> nowPair : map.entrySet()) {
System.out.println(nowPair.getKey()); // key
System.out.println(nowPair.getValue()); // value
}
// key가 필요한 경우
for (int nowKey : map.keySet()) {
System.out.println(nowKey);
}
// value가 필요한 경우
for (int nowValue : map.values()) {
System.out.println(nowValue);
}(코테 풀다가 이거다 싶으면 추가 예정)
