P-coding

오늘은 자료구조의 기본 구조 중 하나인 스택에 대해서 알아보고자 한다.
가장 기본적인 구조로 후입선출 ( LIFO, Last In First Out ) 방식을 가진다.
접시를 쌓아올린다고 생각하면 된다.

스택 ( Stack )

• 후입 선출 ( LIFO, Last In First Out )
• 한쪽 끝에서만 데이터 삽입( push )과 삭제( pop )가 이루어짐
• 재귀 호출, 백트래킹, 수식 계산 등 다양한 알고리즘에서 활용됨

    private int[] stack;
    private int top;

    public TestStack(int size){
        stack = new int[size];
        top = -1;
    }

스택의 기본 연산

1. push(value): 데이터 삽입

• 스택의 맨 위(top)에 데이터를 추가하는 연산

    public void push(int value){
        if(top == stack.length -1 ) {
            System.out.println("스택이 가득 찼습니다.");
            return;
        }

        stack[++top] = value;
    }

2. pop(): 데이터 제거

• 스택의 맨 위(top)에 있는 데이터를 제거하고 반환하는 연산
• 만약 스택이 비어 있다면 언더플로우(Underflow, 데이터 부족 에러) 발생

    public int pop() {
        if (isEmpty()){
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top--];
    }

3. peek() (또는 top()): 최상단 데이터 확인

• 스택의 맨 위(top)에 있는 데이터를 반환하지만, 제거하지 않음

    public int peek() {
        if (isEmpty()) {
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top];
    }

4. isEmpty(): 스택이 비어 있는지 확인

• 스택이 비어 있으면 true, 아니면 false 반환

    public boolean isEmpty() {
        return top == -1;
    }

로직 예시)

왼쪽 위부터 오른쪽으로 진행된다

1. 빈 스택이다

2. push를 통해 값 ( 1 ) 을 넣었다. 이 때 top은 1을 가리킨다

3. push를 통해 값 ( 2 ) 을 넣었다. 이 때 top은 2를 가리킨다.

4. peek를 통해 값 ( 2 ) 을 받았다.

5. pop을 통해 값 ( 2 ) 를 꺼냈다. 이 때 top은 1을 가리킨다.

6. pop을 통해 값 ( 1 ) 를 꺼냈다. 이 때 top은 아무것도 가리키지 않는다. ( -1 상태 )

배열을 활용하여 스택에 대해 설명했지만, 
List 클래스 ( 하위 클래스 포함 ArrayList 등 ) 으로도 구현 가능하다.
 개념을 이해하고 상황에 맞게 사용하면 된다.

전체 구현 코드

package org.example;


public class TestStack {
    private int[] stack;
    private int top;

    public TestStack(int size){
        stack = new int[size];
        top = -1;
    }

    public void push(int value){
        if(top == stack.length -1 ) {
            System.out.println("스택이 가득 찼습니다.");
            return;
        }

        stack[++top] = value;
    }

    public int pop() {
        if (isEmpty()){
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top--];
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }
}

Integer와 Int 같은 정수형을 나타내는 자료형으로 볼 수 있다.
하지만 이는 객체와 기본형으로 다르게 같지만서도 다르다.
이번에는 그 차이를 알아보자.

1. primitive type ( 기본형 )

• 값 자체를 스택 메모리에 직접 저장하는 Primitive 즉, 원시적인 자료형이다. 
• 별도의 정의가 필요없이 사용할 수 있으며 고정된 크기를 차지한다.
• 메소드를 사용할 수 없으며 값을 직접 저장하기 때문에 null 을 저장할 수 없습니다.

2. Wrapper Class ( 객체형 )

• 값은 힙 메모리에 객체에 저장되고, 스택 메모리는 그 객체를 가리키는 주소값을 저장한다.
• 참조형 데이터이기 때문에 추가적인 메모리가 소모된다.
• 기본 상태는 null로 초기화 된다.

3. 메모리 구조 예시 ( 정수 )

다음과 같은 코드를 적용할 때 그림과 같이 메모리에 할당된다.

int num = 10;
Integer num = Integer.valueOf(num);

차이점 요약

Wrapper Class는 제네릭 형태로 자주 사용되며,
특히 List<Integer> 와 같은 컬렉션 프레임워크에서 흔히 활용된다.
간단한 코드에서는 당연하게 사용하지만,
방대한 코드 작성 시에는 메모리나 성능, 기능적 요소를 고려해야 한다.
이러한 상황에 닥쳤을 때 비로소 이유를 고민하기보다, 미리 원리를 이해하고 사용하면 더 효율적일 것이다.

이번 글에서는 백준 17103번 문제를 통해 소수 찾기 알고리즘인 에라토스테네스의 체를 활용,
이를 통해 소수를 찾고 짝수를 소수의 합으로 나타내보자.

---

문제 핵심

• N : 짝수
  • 2 < N <= 1,000,000
• 두 개의 소수의 합이다.
• 순서만 다른 것은 같은 파티션이다.

풀이 과정

다음 문제는 소수를 먼저 찾아서 합을 구하면된다.

즉, 에라토스테네스의 체를 활용 소수를 효율적으로 구할 수 있다.

1. 소수 찾기

먼저 소수를 분별한다. ( max값을 찾아서 할 수 있지만 최대값 1,000,000인 점을 감안 미리 1,000,000까지 소수를 찾는다. )

    private static void sieveOfEratosthenes(int num) {
        isPrime = new boolean[num + 1];

        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (!isPrime[i]) continue;
            for (int j = i + i; j <= num; j += i) {
                isPrime[j] = false;
            }
        }
    }

2. 골드 바흐 파티션 구성

1. 양쪽에서 숫자를 줄여가며 소수 체크를 한다. ( 이 때 양쪽에서 검사하기 때문에 절반만 사용한다. )

2. 둘 다 소수일 때 count를 증가시킨다.

3. count를 반환한다.

    private static int findGBPartitions(int evenNum) {
        if(evenNum < 4 || evenNum % 2 != 0) {
            throw new IllegalArgumentException(" 4이상의 짝수만 입력 가능합니다. ");
        }

        int count = 0;

        for (int i = 2; i <= evenNum / 2; i++) {
            if(isPrime[i] && isPrime[evenNum - i]) {
                count++;
            }
        }
        return count;
    }

미리 찾아둔 소수를 활용하고 반복문을 효율적으로 사용하면 비교적 쉬운 문제이다.
1,000,000 이하의 소수는 미리 생성해도 처리 가능하지만,
숫자가 매우 커질 경우에는 입력값의 최대값을 기준으로 소수를 구하는 것이 더 효율적이다.

이번 문제는 두 수의 합이 N이 되어야 하므로, 다음과 같은 방식이 적합하다.다만, 이전에 선택 정렬 문제에서 사용한 인덱스를 활용한 방식으로 데이터를 저장하는 방법도 고려할 수 있다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    private static boolean[] isPrime;

    public static void main(String[] args) throws IOException {
        solve();
    }

    private static void solve() throws IOException {

        sieveOfEratosthenes(1000000);

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        int N = Integer.parseInt(bufferedReader.readLine());

        for(int i = 0;i<N;i++){
            int num = Integer.parseInt(bufferedReader.readLine());
            String result = String.valueOf(findGBPartitions(num));
            stringBuilder.append(result)
                    .append("\n");
        }

        System.out.println(stringBuilder);
    }


    private static void sieveOfEratosthenes(int num) {
        isPrime = new boolean[num + 1];

        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (!isPrime[i]) continue;
            for (int j = i + i; j <= num; j += i) {
                isPrime[j] = false;
            }
        }
    }

    private static int findGBPartitions(int evenNum) {
        if(evenNum < 4 || evenNum % 2 != 0) {
            throw new IllegalArgumentException(" 4이상의 짝수만 입력 가능합니다. ");
        }

        int count = 0;

        for (int i = 2; i <= evenNum / 2; i++) {
            if(isPrime[i] && isPrime[evenNum - i]) {
                count++;
            }
        }
        return count;
    }
}

maven, Spring, Junit 등 IntelliJ를 사용하면 편하다.
하지만 대부분 VS Code를 대부분 처음에 사용한다고 보는데
그 때 항상 써왔던 코드 정리를 찾아 보고 한다.

키보드를 하나만 더 추가해 4개만 누르면 된다
Ctrl + Alt + Shift + L
이후 다음과 같은 창이 뜬다

그럼 다음과 같이 정리된다.

코드 정리 전

코드 정리 후

개발시 가독성은 매우 중요한 요소 중 하나이다.
코드 작성시 정리는 기본적인 요소이므로 해야한다. 

이번 글에서는 백준 28116번 문제를 통해 선택 정렬 알고리즘을 활용하고,
이를 통해 성능 최적화 방안을 탐구해보려 한다.
선택 정렬의 기본 개념을 바탕으로 문제 해결 과정과 효율성을 높이는 방법을 단계별로 살펴보자.

문제 핵심

• 이 배열은 N까지의 정수가 정확히 한 번씩 등장한다. 즉 중간에 빠진 정수나 중복된 수가 존재하지 않는다.
• 선택 정렬 알고리즘을 사용하여 주어진 배열을 정렬한다
• 이 과정에서 교환이 이루어질 때 이동한 거리를 각각 저장한다.
• N : 배열의 길이

풀이 과정

이전의 선택정렬의 문제와 같이 2중 반복을 통해 풀었다. 하지만 이번의 N의 최대길이가 다르다.

지난 번 23881번 문제에서는 N이 10,000 즉, O(N^2)의 시간 복잡도를 가지더라도 10,000,000의 연산을 한다.

하지만 이번 문제는 N이 500,000으로 어마 어마한 숫자다. 특히 자바로 문제는 푸는 나에게는 더욱 더 좋지 않은 상황이다. 

    private static void solve() {

        int minIndex;
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                 if(arr[j] < arr[minIndex]) {
                     minIndex = j;
                 }
            }

            if(minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;

                int distance = minIndex - i;
                arrSwapCount[arr[minIndex] - 1] += distance;
                arrSwapCount[arr[i] - 1] += distance;
            }
        }
    }

[ 문제 ] 시간 초과

그렇다면 위 코드는 아무리 줄여나가도 2중 반복이라는 한계로 시간초과의 문제를 해결할 수 없다. 어떻게 해야 할까?

한 개의 반복문에 모두 녹여내야 한다. 코드 몇 줄 최적화 시킨다고 해서 나아질 문제가 아닌 것이다. 

문제 해결

문제를 고민하던 중, 제한 조건에 있던 "각 정수는 N까지 정확히 한 번씩 등장한다"는 점이 눈에 들어왔다. 이 조건을 활용하면 인덱스를 이용한 접근이 가능하다고 판단했다. 이를 바탕으로, "위치를 저장하는 배열과 기존의 정렬 대상 배열을 비교하며 값을 처리할 수 있을 것"이라는 아이디어를 떠올렸다. 그 후, 이 규칙을 기반으로 점차 로직을 구체화하며 코드를 작성했다.

과정은 다음과 같다. ( 백준 두 번째 예시값 )

1. 초기화 단계

먼저 주어진 배열이 다음과 같이 저장되고, 값의 위치를 저장하는 배열로 두개를 선언한다.

0부터 시작하는 특성으로 num - 1을 선언하였으나

헷갈리지 않게 사용하려면 배열을 N + 1 만큼 사용하고 0 인덱스를 제외하여 사용하면 된다.

아래 그림에 실제 가르키는 값은 다음과 같다. 제외하고 봐도 무방하다.

    private static int[] arr;
    private static int[] numLocations;

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(stringTokenizer.nextToken());
            arr[i] = num - 1;
            numLocations[num - 1] = i;
        }

그림과 같이 저장된다.

2. 알고리즘 단계

위 그림을 보면 감이 올지도 모른다.

한 개의 반복문에서 index를 활용하여 매치 시키고, 위치에 있어야 할 값과 맞지 않는다면

해당 위치에 있는 값과 원래 있어야 하는(순서에 맞는) 값을 찾고 거리값을 구한다. 

    private static void solve() {
        for (int i = 0; i < numLocations.length; i++) {
            if (arr[i] != i) {
                int distance = numLocations[numLocations[arr[i]]] - i;

                moveCounts[i] += distance;
                moveCounts[arr[i]] += distance;

                arr[numLocations[i]] = arr[i];
                numLocations[arr[i]] = numLocations[i];
            }
        }
    }

i = 0 일때

0 = 0 ( 실제로는 1 = 1 ) 이므로 위치에 맞게 존재한다.

i = 1 일때 ( num - 1 인 것을 감안해야 한다 )

위 그림과 같이 i = 1 ( 두 번째 위치) 에 1 (2) 이 있어야 한다.

그렇다면 numLocation[1] 을 통해 원래 있어야 하는 값의 위치를 찾는다.

왼쪽부터 정렬하며 오기 때문에 i값은 항상 작다. 때문에 numLocation[i] - i를 통해 거리를 계산 할 수 있다.

또한, 값의 교환이 할 필요는 없고, i 값에 해당하는 상태는 이제 필요없기 때문에 이 후 계산할 곳에만 값을 넣어준다.

이 후 distance의 값을  moveCount 배열에 더해주면 정수마다 이동한 거리 값이 계산된다.

나머지도 위를 통해 문제를 해결할 수 있다.

선택 정렬이라고 해서 무조건 2중 반복문을 사용하는게 아닌
그 틀은 그대로 유지하며 다르게 풀어나갈 수 있다는 것
활용하는 것이 가장 중요하다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int[] arr;
    private static int[] numLocations;
    private static int[] moveCounts;

    public static void main(String[] args) throws IOException {
        prepre();
        solve();
        Arrays.stream(moveCounts).forEach(num -> System.out.print(num + " "));
    }

    private static void prepre() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        arr = new int[N];
        numLocations = new int[N];
        moveCounts = new int[N];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(stringTokenizer.nextToken());
            arr[i] = num - 1;
            numLocations[num - 1] = i;
        }
    }

    private static void solve() {
        for (int i = 0; i < numLocations.length; i++) {
            if (arr[i] != i) {
                int distance = numLocations[i] - i;

                moveCounts[i] += distance;
                moveCounts[arr[i]] += distance;

                arr[numLocations[i]] = arr[i];
                numLocations[arr[i]] = numLocations[i];
            }
        }
    }
}

문자열을 특정 구분자로 분리할 수 있는 StringTokenizer와 Splite을 사용하던 중
구체적인 차이점이 무엇인지 궁금하여 조사하게 되었다.
메모리에서 장점을 가진다고 하지만 정확히 어떤구조로 작용하는지 알아보자

StringTokenizer

StringTokenizer 클래스 내부를 살펴보면 다음과 같은 내용을 볼 수 있습니다.

    public StringTokenizer(String str, String delim, boolean returnDelims) {
        currentPosition = 0;
        newPosition = -1;
        delimsChanged = false;
        this.str = str;
        maxPosition = str.length();
        delimiters = delim;
        retDelims = returnDelims;
        setMaxDelimCodePoint();
    }

• 생성자 3가지

• 주요 메서드

1. StringTokenizer(String str)

public StringTokenizer(String str) {
        this(str, " \t\n\r\f", false);
}


StringTokenizer stringtokenizer = new StringTokenizer("Hello World\tJAVA");
	while (tokenizer.hasMoreTokens()) {
    		System.out.println(tokenizer.nextToken();
    	}

Hello
world
JAVA

• 기본 구분자 : 공백( ), 탭(\t), 줄바꿈(\n), 캐리지 리턴(\r), 폼 피드(\f)
• returnDelims는 기본적으로 false

2. StringTokenizer(String str, String delim)

  public StringTokenizer(String str, String delim) {
        this(str, delim, false);
 }

StringTokenizer stringTokenizer = new StringTokenizer("A,B|C", ",|");

while (stringTokenizer.hasMoreTokens()) {
	System.out.println(stringTokenizer.nextToken());
}

A
,
B
|
C

3. StringTokenizer(String str, String delim, boolean returnDelims)

public StringTokenizer(String str, String delim, boolean returnDelims) {
        currentPosition = 0;
        newPosition = -1;
        delimsChanged = false;
        this.str = str;
        maxPosition = str.length();
        delimiters = delim;
        retDelims = returnDelims;
        setMaxDelimCodePoint();
}

StringTokenizer stringTokenizer = new StringTokenizer("A,B|C", ",|", true);

while (stringTokenizer.hasMoreTokens()) {
    System.out.println(stringTokenizer.nextToken());
}

A
,
B
| C

다음과 같은 생성자를 가지고 있는데 코드를 살펴보면 단 하나의 구분자로만 사용되는 것으로 보인다.

즉, 구분자 문자가 개별로 작용하여 하지만 String 클래스의 split은 ,| 를 하나의 구분자로 사용할 수 있다.

Split

split 메드는 문자열을 특정 정규식(regex)을 기준으로 나눈다.

다음은 String 클래스에 있는 split 메서드이다.

    public String[] split(String regex) {
        return split(regex, 0);
    }
    
    
    public String[] split(String regex, int limit) {
        char ch = 0;
        if (((regex.length() == 1 &&
             ".$|()[{^?*+\\".indexOf(ch = regex.charAt(0)) == -1) ||
             (regex.length() == 2 &&
              regex.charAt(0) == '\\' &&
              (((ch = regex.charAt(1))-'0')|('9'-ch)) < 0 &&
              ((ch-'a')|('z'-ch)) < 0 &&
              ((ch-'A')|('Z'-ch)) < 0)) &&
            (ch < Character.MIN_HIGH_SURROGATE ||
             ch > Character.MAX_LOW_SURROGATE))
        {
            int off = 0;
            int next = 0;
            boolean limited = limit > 0;
            ArrayList<String> list = new ArrayList<>();
            while ((next = indexOf(ch, off)) != -1) {
                if (!limited || list.size() < limit - 1) {
                    list.add(substring(off, next));
                    off = next + 1;
                } else {    // last one
                    //assert (list.size() == limit - 1);
                    int last = length();
                    list.add(substring(off, last));
                    off = last;
                    break;
                }
            }
            // If no match was found, return this
            if (off == 0)
                return new String[]{this};

            // Add remaining segment
            if (!limited || list.size() < limit)
                list.add(substring(off, length()));

            // Construct result
            int resultSize = list.size();
            if (limit == 0) {
                while (resultSize > 0 && list.get(resultSize - 1).isEmpty()) {
                    resultSize--;
                }
            }
            String[] result = new String[resultSize];
            return list.subList(0, resultSize).toArray(result);
        }
        return Pattern.compile(regex).split(this, limit);
    }

위를 보면 limit을 통해 배열의 길이를 조절할 수 있다.

로직을 보기 전까지는 사실 어떻게 작동하는 지 헷갈릴 수 있다.

A, B, C와 2를 대입하여 사용한다면 A와 B인지 A와 B,C 인지...

그것을 보여주는 코드예시이다.

public class SplitExample {
    public static void main(String[] args) {
        String str = "apple,banana,cherry,orange,grape";

        String[] result = str.split(",", 3);

        for (String token : result) {
            System.out.println(token);
        }
    }
}

apple
banana
cherry,orange,grape

split은 구분자를 찾아 subString으로 분리반복하고 결과 배열을 생성하는 것을 볼 수 있다.

그리고 빈 문자열, 구분자 사이에 문자가 없는 경우

,,

StringTokenizer는 이를 무시하지만 split은 빈 문자열로 간주한다.

StringTokenizer와 split의 차이는 다음과 같다.

둘 중 누가 성능이 좋은가?

정규식이나 복잡한 패턴이 아닌 두 메서드 모두 가능한 구분자로 진행하였을 때, 어느 때 어떤 메서드가 성능이 좋은지 4가지 기준으로 분류했다. 4가지 기준은 다음과 같다

• 유니코드를 사용한 경우
• 긴 문자열과 한 가지 구분자를 사용한 경우
• 짧은 문자열과 한 가지 구분자를 사용한 경우
• 짧은 문자열과 여러 구분자를 동시에 사용한 경우

StringTokenizer 한 가지 구분자로 이루어진 문자열을 사용한 경우는 문자열이 길든 짧든 항상 빨랐다.

split()은 여러 구분자와 유니코드를 사용한 경우에 빨랐다. 

StringTokenizer

StringTokenizer 클래스의 내부를 살펴보면 구분자에 따라 성능이 좌우된다.

StringTokenizer 클래스 scanToken 메서드

    private int scanToken(int startPos) {
        int position = startPos;
        while (position < maxPosition) {
            if (!hasSurrogates) {
                char c = str.charAt(position);
                if ((c <= maxDelimCodePoint) && (delimiters.indexOf(c) >= 0))
                    break;
                position++;
            } else {
                int c = str.codePointAt(position);
                if ((c <= maxDelimCodePoint) && isDelimiter(c))
                    break;
                position += Character.charCount(c);
            }
        }
        if (retDelims && (startPos == position)) {
            if (!hasSurrogates) {
                char c = str.charAt(position);
                if ((c <= maxDelimCodePoint) && (delimiters.indexOf(c) >= 0))
                    position++;
            } else {
                int c = str.codePointAt(position);
                if ((c <= maxDelimCodePoint) && isDelimiter(c))
                    position += Character.charCount(c);
            }
        }
        return position;
    }

( hasSurrogates는 유니코드인지 확인하는 것이고 indexOf와 isDelimiter 메서드는 같은 로직이다. )

여기서 성능에 영향을 끼치는 것은 indexOf() 메서드 이다. 이는 순차탐색으로 최악의 경우 O(|delimiter|)의 시간이 걸린다.

모든 문자에 이 코드를 작동된다고 생각한다면 성능은 구분자의 개 수에 따라 달라진다. 다음 예시를 보자

아스키 코드 값

@ : 64

, : 44

< : 60

{ : 123

@ 찾는 경우

< 찾는 경우

} ( 없는 구분자 ) 를 찾는 경우

}  는 아스키 코드 값이 125이기 때문에 maxDelimCodePoint ( 123 ) 보다 크다.

때문에 탐색되지 않는다.

구분자가 아닌 문자 A인 경우

A( 65 ) < maxDelimCodePoint (125)

때문에 모두 탐색해본다.

이처럼 단순 문자일 경우도 모두 탐색한다. 그래서 구분자가 많으면 많을수록 괴랄하게 탐색시간이 늘어난다.

유니코드라면 두 개의 char 를 쓰기 때문에 더욱 더 심각해진다.

split()

• split 메서드는 정규식을 사용하여 구분자를 기준으로 문자열을 나눈다.
• Pattern 클래스(정규 표현식 엔진)를 활용해 문장열을 순회, 구분자를 매칭한다.
• 그 구분자 자리를 기억하고 문자열을 자른다.

다음과 같이 표현할 수 있다.

String input = "apple,banana,grape";
String[] result = input.split(",");

매칭 과정

1. 구분자 ,를 문자열에서 찾기 시작.
   • 첫 번째 ,의 위치: 5.
   • 두 번째 ,의 위치: 12.
2. 매칭된 위치: [5, 12].

자르는 위치 계산

구분자의 위치를 기반으로 문자열을 나눕니다:

• 첫 번째 구분자의 앞부분 → 0~5 ("apple").
• 첫 번째 구분자와 두 번째 구분자의 사이 → 6~12 ("banana").
• 마지막 구분자 이후 → 13~끝 ("grape").

때문에  StringTokenizer가 많은 구분자나 유니코드를 문자마다 확인하는 경우에 정규 표현식 엔진으로 보다 빠르게 비교할 수 있고 문자열을 자르기 때문에 split() 성능이 좋지만, 정규 표현식 엔진의 기본 처리 시간이 StringTokenizer가 한 개의 구분자를 비교하는 것보다는 느린 경우가 많다. 또한 긴 문자열일 때 종종 같은 구분자라도 split() 빠른 경우가 있는데.. 같은 문자열을 길게 복사한 것이라서 모든 문자가 구분자의 코드 포인트보다 낮아 코드를 끝까지 읽어서 느린 경우가 아닌 찾아보니 split()은 JVM 메모리 관리 측면에서 같은 문자를 나누는 기준은 캐싱되어 성능이 최적화될 수 있다고 한다.

그렇다면 무엇을 사용해야 할까?
자바에서는 다음과 같이 설명하고 있다.

사실  StringTokenizer는 레거시 클래스이다?

StringTokenizer is a legacy class that is retained for compatibility reasons although its use is discouraged in new code. It is recommended that anyone seeking this functionality use the split method of String or the java.util.regex package instead.

호환성 이유로 유지되는 레거시 클래스이며 새로운 코드에서는 사용이 권장되지 않음. 대신 Split이나 java.util.regex 패키지를 사용하는 것이 좋다.

출처 : JAVA StringTokenizer

StringTokenizer는 사용하면 안될까?

결론적으로는 그렇다고 생각한다. JDK가 업데이트 됨에 따라 레거시 클래스는 삭제될 수도 있다.

JDK가 업데이트 되었다고 해서 사용하던 JDK를 바로 당장 전부 업데이트하지 않겠지만,

미래 지향적으로 본다면 그렇다고 생각한다.

이번 글에서는 백준 23881번 문제를 통해 선택 정렬 동작 원리를 확인, 활용해 보겠습니다.
선택 정렬에 대한 정리는 다음 게시글에 있습니다.

https://p-coding.tistory.com/100

문제 핵심

• 선택 정렬 알고리즘을 사용하여 주어진 배열을 정렬한다.
• 이 과정에서 K 번째 교환이 이루어질 때 교환되는 두 수를 반환하며, K번 미만일 때 특정 결과인 -1을 반환한다.
• N : 배열의 길이
• K : 목표 교환 횟수

풀이과정

먼저 BufferedReader를 통해 값을 받습니다. Scanner를 사용할 수 있으나 하나씩 처리하는 방식은 시간 제한에 걸릴 수 있으므로 Buffer를 활용한 클래스를 사용하는 것을 추천드립니다.

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        swapCount = Integer.parseInt(stringTokenizer.nextToken());

        arr = new int[N];

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

• N과 K(swapCount) 값을 저장
• 배열의 원소들을 받고, tokenizer를 통해 받은 값을 분리하여 저장

        int count = -1;
        if (arr.length < 2) {
            System.out.println(count);
        }

        int maxIndex;
        for (int i = arr.length - 1; i > 0; i--) {
            maxIndex = i;

            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }

            if (maxIndex != i) {
                count++;
                if (swapCount == (count + 1)) {
                    System.out.println(arr[i] + " " + arr[maxIndex]);
                    return;
                }
                int temp = arr[maxIndex];
                arr[maxIndex] = arr[i];
                arr[i] = temp;

            }
        }

        System.out.println(-1);

• count는 -1로 시작 ( 0으로 시작할 때와 값이 1차이 )
• 교환이 이루어지지 않는다면 -1 출력
• 기준점을 마지막 원소로 잡고 maxIndex에 저장한다
• j ( 마지막 원소 - 1 ) 부터 1씩 감소하여 비교 후 높은 값이 있다면 위치를 기억해 둔다.
• maxIndex와 i 값이 다르다면 위치 변경과 변경 횟수를 1 증가한다.
• 반복하며 K(교환 횟수)에 도달했는지 체크한다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static int[] arr;
    private static int swapCount;

    public static void main(String[] args) {
        try {
            prepare();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }

        selection_sort();

    }

    private static void prepare() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        swapCount = Integer.parseInt(stringTokenizer.nextToken());

        arr = new int[N];

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

    }

    private static void selection_sort() {
        int count = -1;
        if (arr.length < 2) {
            System.out.println(count);
        }

        int maxIndex;
        for (int i = arr.length - 1; i > 0; i--) {
            maxIndex = i;

            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }

            if (maxIndex != i) {
                count++;
                if (swapCount == (count + 1)) {
                    System.out.println(arr[i] + " " + arr[maxIndex]);
                    return;
                }
                int temp = arr[maxIndex];
                arr[maxIndex] = arr[i];
                arr[i] = temp;

            }
        }

        System.out.println(-1);

    }
}

선택 정렬 활용의 기초단계로 시험해보기 좋은 문제이다.

요즘 다시 알고리즘 공부를 시작하려고 하여
백준에서 문제를 풀어나가며 알고리즘을 따로 정리, 기술하는 방향으로 계획하고 있다.
그 중 정렬 알고리즘을 먼저 살펴보려고 하며,
오늘은 기본 중 하나인 선택 정렬를 알아보고자 한다.

선택 정렬 ( Selection Sort )

선택 정렬은 간단하지만 비효율적인 정렬 알고리즘 중 하나로, 배열에서 가장 큰 or 가장 작은 값을 찾아 현재 위치에 배치하는 과정을 반복하여 정렬된다.

순서는 다음과 같다.

1. 정렬되지 않은 부분에서 최솟값 or 최댓값 찾기

2. 현재 위치와 최솟 값 or 최대 값 교환

3. 다음 위치로 이동하며 반복

다음 그림과 같이 예시로 알아보자

5개의 정수 값을 가진 배열 Array가 존재한다.

이를 오름차순으로 왼쪽부터 최솟값을 찾아 정렬하고자 한다.

기본 형태

1회차

첫번 째 위치인 4를 기준

차례로 5, 3, 1, 2 와 비교

최솟값을 찾아 위치를 교환

1회차 완료

2회차

두번 째 위치인 5를 기준

차례로 3, 4, 2 와 비교

최솟값을 찾아 위치를 교환

2회차 완료

2회차만에 정렬되어 정렬된 배열은 다음과 같다.

전체 코드

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int [] arr = {6,4,2,1,3,5};
        selectionSort(arr);
        Arrays.stream(arr).forEach(System.out::println);
    }

    private static void selectionSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }

        int minIndex;
        for(int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for(int j = i + 1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            if(minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }
}

구현은 쉽고 직관적이긴 하나,  선택 정렬은 앞서 말했듯 입력 배열에 관계없이(2회차에 정렬이 되었더라도)
외부 반복문에서 n -1 회, 내부 루프에서 n - 1, n - 2, ..., 1번 비교함으로
시간복잡도는 항상 O(n^2) 으로 비효율적이다. 

새로운 개발 환경에서 시작하는 일이 잦다 보니
개발 필수 도구들을 설치하는 것에 대한 가이드라인을 작성해보려고 한다.
간단한 설치와 환경 변수 설정까지 단계별로 다루겠다.

1. JAVA 다운로드 및 설치 준비

1-1. 설치 파일 다운로드

• 오라클 홈페이지에서 JDK(JAVA Development Kit) 버전과 운영체제에 맞는 파일을 다운로드 해줍니다.
• 윈도우 11부터는 32비트 지원을 제공하지 않기 때문에 윈도우 최신 자바 버전도 64비트만 존재합니다.

어떤 것을 다운로드 해도 상관없으나

Windows 환경 기준으로 MSI 설치파일을 사용하면 환경변수까지 자동으로 설정해주기 때문에 MSI Installer를 추천한다.

+

기본적으로 Installer, MSI Installer는 C:\Program\Files\Java 파일경로에 설치되고

Compressed Archive는 직접 파일 경로를 설정하고 설치한다.

1-2. 설치 완료 후 확인

• 아래 작업표시줄 검색에 명령 터미널, 프롬포트나 cmd를 검색해 실행한다.
• 다음 명령어를 통해 자바가 설치되었는지 확인한다.

java -version

다음과 같이 버전 정보가 표시되면 설치가 성공적으로 완료되었다. 

하지만 version이 확인 되지 않는다면 환경 변수가 설정되지 않았기 때문이다. 

다음 환경 변수 설정을 보자

2. 환경 변수 설정 (Windows 기준)

2 - 1. 작업 표시줄 검색창에 "환경 변수 편집"을 입력하고 선택

2 - 2. "환경 변수" 클릭

2 - 3. 새로 만들기 클릭하고 다음과 같이 입력 ( 파일 위치에 맞게 되어있는지 검토하셔야 합니다. )

C:\Program Files\Java\jdk-23

2 - 4. "Path" 찾아서 더블 클릭

새로만들기를 통해 다음과 같은 항목을 추가해 준다.

%JAVA_HOME%\bin

3. VS Code 설치

3 - 1. Visual Code 설치

다음 사이트를 통해 VS Code를 다운 받아준다.

3 - 2. 유용한 Extensions (확장 프로그램) 추가

다음과 같은 확장 프로그램을 검색을 통해 추가해 주면 좋다.

필수 확장 프로그램

1. Language Support for Java(TM) by Red Hat

• 기본 Java 언어 지원 (코드 완성, 오류 탐지, 문법 강조 등).

2. Debugger for Java

• Java 애플리케이션 디버깅 지원

3. Java Extension Pack

• Red Hat Java 확장과 관련된 모든 패키지 한번에 설치 가능

Java 개발에 유용한 확장 프로그램은 다양하지만,
중복되거나 너무 많은 확장 프로그램을 설치하면 혼란을 야기할 수 있다.
따라서 본인의 개발 환경과 필요에 따라 적절한 확장 프로그램을 선택하고 사용하는 것이 중요하다

필수적인 도구만 설치하여 효율적이고 깔끔한 개발 환경을 유지하는 것을 추천한다.

JAVA 에서는 System.out과 System.err는 출력 스트림(Output Stream)으로 각각 특정 목적과 동작 방식에 맞게 사용됩니다. 그 두가지에는 무슨 차이점이 있는지 알아보겠습니다.

---

System.out 특징

• 일반 출력용 스트림으로, 프로그램의 정상적인 실행 결과를 출력
• 출력 내용을 버퍼(buffer)에 임시 저장 후 특정 조건에 한 번에 출력
• 이로 인해 출력 순서가 보장되지 않을 수 있습니다.

System.err 특징

• 에러 출력용 스트림으로 에러나 크리티컬한 상황에 대한 기록
• 중요한 메시지를 즉각적으로 보여주기 위해 자동으로 출력
• 따라서 실행 중 바로 확인 가능하며, 디버깅 시 유용하게 사용될 수 있습니다.

예시

코드

System.out.println("3 x 3 = ");
System.out.err("9");

출력 예시

9
3 x 3 =