문자열 역순 처리 알고리즘

문자열을 효율적으로 역순으로 처리하는 기본 알고리즘은 두 개의 포인터를 사용하여 문자열의 양쪽 끝에서 중앙으로 이동하며 요소를 교환하는 방식입니다. 이 방법은 공간 복잡도 O(1)로 문자열을 역순으로 만들 수 있어 매우 효율적입니다.

문제 1: 문자열 전체 역순

이 문제에서는 문자 배열을 입력으로 받아 해당 배열의 내용을 역순으로 재배열해야 합니다. 자바의 내장 라이브러리 함수를 사용하지 않고 직접 구현하는 것이 핵심 과제입니다.

문자열을 역순으로 만드는 두 가지 주요 방법이 있습니다:

1. 임시 변수를 사용한 교환 방식
2. 비트 연산(XOR)을 이용한 교환 방식

XOR 연산의 특성을 활용한 교환 방식은 다음과 같은 원리를 따릅니다:

• a ^ a = 0 (같은 수를 XOR하면 0이 됨)
• a ^ 0 = a (임의의 수와 0을 XOR하면 그 수가 유지됨)
• XOR 연산은 교환법칙과 결합법칙을 만족: a ^ b = b ^ a, (a ^ b) ^ c = a ^ (b ^ c)

주의할 점은 두 포인터가 같은 위치를 가리킬 때 교연산을 수행하면 해당 위치의 값이 0이 되므로, 이 경우 교환을 수행하지 않아야 합니다.

해결 코드

class 문자열반전 {
    public void 문자열반전(char[] s) {
        int 왼쪽 = 0;
        int 오른쪽 = s.length - 1;
        
        while (왼쪽 < 오른쪽) {
            // XOR 연산을 이용한 교환
            s[왼쪽] ^= s[오른쪽];
            s[오른쪽] ^= s[왼쪽];
            s[왼쪽] ^= s[오른쪽];
            
            왼쪽++;
            오른쪽--;
        }
    }
}

// 임시 변수를 사용하는 더 직관적인 방법
class 문자열반전 {
    public void 문자열반전(char[] s) {
        int 시작 = 0;
        int 끝 = s.length - 1;
        
        while(시작 < 끝) {
            char 임시 = s[시작];
            s[시작] = s[끝];
            s[끝] = 임시;
            
            시작++;
            끝--;
        }
    }
}

문제 2: 문자열 부분 역순

이 문제는 문자열을 특정 간격(k)으로 나누어 각 구간의 앞부분 k개 문자만 역순으로 만드는 문제입니다. 전체 문자열을 2k 단위로 나누어 각 구간에서 앞의 k개 문자만 역순으로 처리합니다.

핵심 알고리즘:

1. 문자열을 2k 단위로 순회합니다.
2. 각 구간에서 시작 위치부터 min(문자열 끝, 시작 위치 + k - 1)까지의 문자를 역순으로 만듭니다.
3. 남은 문자가 k개 미만일 경우 모두 역순으로 만듭니다.

해결 코드

class 문자열부분반전 {
    public String 문자열부분반전(String s, int k) {
        char[] 문자배열 = s.toCharArray();
        
        for(int i = 0; i < 문자배열.length; i += 2 * k){
            int 시작위치 = i;
            // 남은 문자가 k개 이상인지 확인하여 끝위치 결정
            int 끝위치 = Math.min(문자배열.length - 1, 시작위치 + k - 1);
            
            while(시작위치 < 끝위치){
                char 임시 = 문자배열[시작위치];
                문자배열[시작위치] = 문자배열[끝위치];
                문자배열[끝위치] = 임시;
                
                시작위치++;
                끝위치--;
            }
        }
        return new String(문자배열);
    }
}

문제 3: 숫자 문자열 변환

이 문제는 문자열 내의 모든 숫자를 "number"라는 단어로 변환하는 작업입니다. 효율적인 해결을 위해 배열을 먼저 확장한 후, 끝에서부터 문자를 처리하는 방식을 사용합니다.

알고리즘 접근 방식:

1. 원본 문자열의 숫자 개수를 세어 새 배열의 크기를 계산합니다.
2. 원본 문자열을 새 배열로 복사합니다.
3. 끝에서부터 문자를 확인하며 숫자를 발견하면 "number"로 변환합니다.
4. 숫자가 아닌 문자는 그대로 유지합니다.

이 방식은 앞에서부터 처리할 경우 발생할 수 있는 데이터 이동을 방지하여 시간 복잡도를 효율적으로 만듭니다.

해결 코드

import java.util.*;

public class 숫자변환 {
    public static void main(String[] args) {
        Scanner 입력 = new Scanner(System.in);
        String 원본문자열 = 입력.next();
        int 원본길이 = 원본문자열.length();
        
        // 숫자 개수 세기
        for (int i = 0; i < 원본문자열.length(); i++) {
            if (Character.isDigit(원본문자열.charAt(i))) {
                원본길이 += 5; // "number"는 6글자이지만 기존 숫자 1개를 대체하므로 +5
            }
        }
        
        char[] 결과배열 = new char[원본길이];
        // 원본 문자열을 새 배열로 복사
        for (int i = 0; i < 원본문자열.length(); i++) {
            결과배열[i] = 원본문자열.charAt(i);
        }
        
        // 끝에서부터 처리
        for (int i = 원본문자열.length() - 1, j = 원본길이 - 1; i >= 0; i--) {
            if (Character.isDigit(결과배열[i])) {
                // "number" 역순으로 삽입
                결과배열[j--] = 'r';
                결과배열[j--] = 'e';
                결과배열[j--] = 'b';
                결과배열[j--] = 'm';
                결과배열[j--] = 'u';
                결과배열[j--] = 'n';
            } else {
                결과배열[j--] = 결과배열[i];
            }
        }
        System.out.println(결과배열);
    }
}