[알고리즘] 자바 알고리즘 기본 세팅

원래 파이썬과 C++로 알고리즘 문제들을 풀었었는데, 최근에 알고리즘 언어를 자바로 갈아타면서, 자바로 알고리즘 문제를 풀려면 알아야 하는 것들을 정리한 글입니다.

환경 세팅

자바 설치

자바를 설치해야 한다. 버전 별로 사용 가능한 문법이 다르다.
Stream API가 나온 Java 8 로 준비하면 별 문제 없다.

Code Editor

프로젝트들을 IntelliJ로 진행하는 관계로, 알고리즘 문제풀이를 위한 설정과 분리하기 위해 알고리즘을 풀 때는 Visual Studio Code 를 메인으로 사용하려고 한다.

(가끔 클래스 파일을 여러개 생성해야 하는 알고리즘 문제를 풀때는 Eclipse를 사용하고 있다. 단일 파일일 경우만 VSCode 사용)

VSCode Extension

Code runner, Extension Pack for Java 를 사용한다.

백준

기본적으로 백준에 문제를 정상적으로 제출하려면, 패키지가 없어야 하고, 클래스 이름은 Main 이어야 한다.

public class Main {
    public static void main(String args[]) {
		//..
    }
}

자바는 클래스명과 파일명이 일치해야하므로 Main 클래스 파일에 코드를 작성해서 제출해야한다. 매번 문제를 풀때마다 Main.class 파일을 다시 작성해야 한다.

크롬 확장 프로그램: 백준허브

Main.class 파일을 계속 사용하려면 이전 코드를 지워야 한다. 따라서 파일 관리를 위해서 추가로 Chrome 확장 프로그램으로 백준허브를 사용해서 백준에 제출시 자동 커밋되도록 설정했다.

입력

Scanner

1 2 3 4 5 같은 입력을 받아 정수 리스트로 변환하는 함수로 예시를 들었다.

import java.util.*;

public class Main{
    public static List<Integer> parseInputSplitToList(String splitRegex) throws IOException {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(splitRegex);
        sc.close() // 입력 스트림 닫기. 필수는 아니다
        
        return Arrays.stream(input)
                .map(Integer::parseInt)
                .collect(Collectors.toList());
    }
    //..
}

nextLine(), nextInt(), nextFloat() 등 여러 입력 형식을 지원하고 간편하지만 입출력이 대량이라면 꽤 느리다. 백준 입력 속도 비교

BufferedReader

import java.io.*;
import java.util.*;

public class Main {
    public static List<Integer> parseInputSplitToList(String splitRegex) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] tokens = br.readLine().split(splitRegex);
        br.close() // 스트림 닫기. 필수는 아니다
        
        return Arrays.stream(tokens)
                .map(Integer::parseInt)
                .collect(Collectors.toList());
    }
    //..
}

BufferedReader 는 readLine() 으로 문자열 입력만 받을 수 있다.

백준 11023번에 위 메소드를 적용해서 측정한 실행 시간 차이는

• Scanner: 180ms
• BufferedReader: 112ms

으로 꽤 유의미 하다.

따라서 입력이 많은 문제에는 BufferedReader 을 사용하면 좋다.

StringTokenizer

입력이 1 8 3 2 9 와 같이 한줄에 여러 입력이 왔을때 보통 String.split(" ") 을 사용할텐데, 그것보다 빠른게 있다.

StringTokenizer st = new StringTokenizer(bf.readLine());
int a = Integer.valueOf(st.nextToken());
int b = Integer.valueOf(st.nextToken());
int c = Integer.valueOf(st.nextToken());

Scanner -> BufferedReader 만큼은 아니지만 저런 입력이 많은 문제에서는 유의미한 작동 시간 감소가 나타난다. split 기능을 N번 이상 사용하는 문제라면 차라리 이걸 쓰는게 낫다.

출력

System.out.print();
정수, 실수, 문자열 등 값을 출력한다. 줄바꿈 문자가 들어가지 않는다.

System.out.print("Hello, ");
System.out.print("world!");
// 출력 결과
// Hello, world!

System.out.println();
줄바꿈 문자를 마지막에 추가한다.

System.out.println("Hello, ");
System.out.println("world!");
// 출력 결과
// Hello, 
// world!

System.out.printf();
C언의의 printf() 처럼 형식 지정자를 사용하여 출력한다. 문자열을 특정 형식으로 포맷하여 출력할때 유용하다.

System.out.printf("이름: %s, 나이: %d, 키: %.1fcm%n", "홍길동", 25, 175.5);
// 출력: 이름: 홍길동, 나이: 25, 키: 175.5cm

System.out.printf("%10s%n", "Hello"); // 10칸 확보하고 우측 정렬
System.out.printf("%-10s%n", "Hello"); // 10칸 확보하고 좌측 정렬
// 출력:
//      Hello
// Hello     

• %n 은 \n 처럼 줄바꿈을 의미한다.

더 빠른 출력 방식도 있지만, 출력을 매우 많이 하는 알고리즘 문제는 드물어서 넘어가겠다.

배열

자바는 C++에서 배열을 다루기 위해 기본 배열과 Vector 두가지를 사용하는 것과 마찬가지로 두가지 방식으로 배열을 다룰 수 있다.

array

int[] a = new Int[6]; // { 0, 0, 0, 0, 0, 0 }

배열 크기 변경이 불가하므로 동적으로 배열의 크기를 변경할 일 없을 경우 사용한다.
코테 문제에서는 대부분 테스트 케이스마다 크기가 주어지므로 주로 이걸 사용하게 된다.

ArrayList

List<Integer> a = new ArrayList<>(6);

.add(), .remove() 등 배열의 크기를 변경하는 여러 메소드를 사용 가능하다.
하지만, 동적할당이나 필요한 기능을 사용해야 하는 것이 아니라면 일반 배열을 쓴다.

*List는 인터페이스이고, ArrayList는 그 구현체 중 하나이다. 자바 Collection 참고

정렬

Array

// 오름차순
int[] a = { 1, 5, 3, 2, 4 };
Arrays.sort(a); // a -> { 1, 2, 3, 4, 5 }

// 내림차순
Integer[] b = { 1, 5, 3, 2, 4 };
Arrays.sort(b, Collections.reverseOrder()); // a -> { 5, 4, 3, 2, 1 }

Collections.reverseOrder() 가 원시 타입(int) 에는 사용 불가능하므로 Warpper 타입(Integer) 배열만 가능하다.

Array- 커스텀 정렬

import java.util.Arrays;

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

//..

Node[] nodes = new Node[N];

// x^2 + y^2 오름차순 정렬
Arrays.sort(nodes, (n1, n2) ->
	Integer.compare(n1.x * n1.x + n1.y * n1.y, n2.x * n2.x + n2.y * n2.y)
);

람다 형식으로 Comparator 를 구현할 수 있다.
문제에 따라 sort 할 때 람다식을 넘기는것 말고, Node 클래스 자체에 comparable 를 상속하고, compare 메소드를 구현해서 쓰기도 한다.

import java.util.Arrays;

class Node implements Comparable<Node> {
    int x;
    int y;

    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.x * this.x + this.y * this.y, other.x * other.x + other.y * other.y);
    }
}

//..

Node[] nodes = new Node[N];

// x^2 + y^2 오름차순 정렬
Arrays.sort(nodes);

List

// 오름차순
List<Integer> a = new ArrayList<>(Arrays.asList(1, 5, 3, 2, 4)); // 자바 8이면 List.of 대신 Arrays.asList 사용
a.sort(null) // a -> { 1, 2, 3, 4, 5 }

// 내림차순 (둘 다 가능)
a.sort(Collections.reverseOrder()); // a -> { 5, 4, 3, 2, 1 }
a.sort((x, y) -> Integer.compare(y, x)); // a -> { 5, 4, 3, 2, 1 }

배열 값 포함 검사

Array

int[] a = { 1, 2, 3, 4, 5 };
boolean isContain1 = Arrays.stream(a).anyMatch(v -> v == 3); // true
boolean isContain2 = Arrays.stream(a).anyMatch(v -> v == 9); // false

List

List<Integer> a = new ArrayList<>(List.of(1, 2, 3, 4, 5));
boolean isContain1 = a.contains(3); // true
boolean isContain2 = a.contains(9); // false

boolean isContain3 = a.stream().anyMatch(v -> v == 3); // 물론 스트림으로도 가능하다

문자열

문자열도 배열처럼 불변일 경우와 가변일 경우 다루는 방식이 다르다.

String

불변이므로 문자열을 조작하면 새로운 객체가 생성된다. 문자열 변경 작업이 적다면 사용하면 된다.

String str = "Hello, World!";
int len = str.length(); // 길이 결과: 13
char c = str.charAt(0); // 문자 추출 결과: 'H'
String result = str.concat(" Java!"); // 연결 결과: "Hello, World! Java!"
String sub = str.substring(7); // 문자열 추출 결과: "World!"
String sub2 = str.substring(7, 12); // 문자열 추출 결과: "World"
String upper = str.toUpperCase(); // 대문자 변환 결과: "HELLO, WORLD!"
String lower = str.toLowerCase(); // 소문자 변환 결과: "hello, world!"
boolean isEqual = str.equals("Hello, World!"); // 비교 결과: true (참조 주소 비교가 아닌 문자열 내용 비교)
boolean isEqualIgnoreCase = str.equalsIgnoreCase("hello, world!"); // 대소문자 무시 비교 결과: true
boolean contains = str.contains("World"); // 포함 여부 결과: true
String trimmed = "   Hello!   ".trim(); // 공백 제거 결과: "Hello!"
String[] parts = str.split(", "); // 문자열 분리 결과: ["Hello", "World!"]
String replaced = str.replace("World", "Java"); // 문자열 치환 결과: "Hello, Java!"
StringBuilder sb = new StringBuilder(str); // StringBuilder 로 변환

c++ 에서 처럼 char[] 을 문자열처럼 사용할 수 있다.
주의할 것은 String 으로 변환할 경우 char[] 은 고정 크기이므로 실제 문자열 크기와 char 크기가 다를경우 빈 공간에 '\0' 이 들어가있을 수 있다. trim() 을 사용해서 이를 제거해줘야 올바른 값만 String 으로 변환된다.

void foo(char[] charAry) {
	String str = String.valueOf(charAry).trim();
}

StringBuilder

가변이므로 문자열 변경 작업이 많을때 사용한다.

이것을 안쓰고 그냥 "Hello" + 7 + "world" 이런 식으로 하면, 매 번 + 연산을 할때마다 "Hello", "Hello7", "Hello7world" 문자열을 모두 메모리에 생성하므로 비효율적이다.

StringBuilder sb = new StringBuilder("Hello, ");
sb.append("World!"); // 추가 결과: "Hello, World!"
sb.insert(7, "Java "); // 삽입 결과: "Hello, Java World!"
sb.delete(6, 11); // 삭제 결과: "Hello, World!"
sb.reverse(); // 반전 결과: "!dlroW ,olleH"
int len = sb.length(); // 길이 결과: 13
sb.setLength(5); // 결과: "!dlro"
String str = sb.toString(); // String 타입으로 변환