반응형
이번 글에서는 백준 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가지
생성자 설명
StringTokenizer(String str) 문자열(str)을 기본 구분자를 제외하고 문자열을 반환한다.
기본 구분자 : 공백( ), 탭(\t), 줄바꿈(\n), 캐리지 리턴(\r), 폼 피드(\f)
StringTokenizer(String str, String delim) 문자열(str)을 구분자(delim)를 제외하고 문자열을 반환한다.
StringTokenizer(String str, String delim, boolean returnDelims) 문자열(str)을 구분자(delim)을 제외할 것 인지(returnDelims)에 따라 true면 반환한다.
  • 주요 메서드
메서드 설명
hasMoreTokens() 더 읽을 토큰이 있는지 확인, true/flase 반환
nextToken() 다음 토큰 반환 및 포인터 이동
nextToken(String delim) 구분자를 새로 지정하여 다음 토큰 반환
countTokens() 남아있는 토큰 개수를 반환
hasMoreElements() hasMoreToken()와 동일
nextElement() nextToken()과 동일, 반환값이 Object 타입

 


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의 차이는 다음과 같다.

 

특징 String.split() StringTokenizer
구분자 정규식 지원 ( 복잡한 패턴 가능 ) 단순한 문자 집합( 정규식 미지원 ) 
결과 형태 String [] 배열  각 토큰으로 개별 반
구분자 반환 지원하지 않음 returenDelims 설정을 통한 반환 옵션 제공 
동작 방식 정규식으로 문자열 분리
빠른 최적화 코드 포함
빈 문자열도 인식
구분자 위치계산
내부 위치 포인터로 하나씩 반환
빈 문자열은 인식하지 않음
유연성 졍규식으로 높은 유연성 제한적
사용성 결과를 한 번에 반환 각 토큰으로 분리하여 하나씩 처리

 

둘 중 누가 성능이 좋은가?

정규식이나 복잡한 패턴이 아닌 두 메서드 모두 가능한 구분자로 진행하였을 때, 어느 때 어떤 메서드가 성능이 좋은지 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

 

[ 알고리즘 ] 선택 정렬

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

p-coding.tistory.com

 

문제 핵심

  • 선택 정렬 알고리즘을 사용하여 주어진 배열을 정렬한다.
  • 이 과정에서 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);

    }
}

 

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

+ Recent posts