[인프런 자바 알고리즘 문제풀이] 5. 특정 문자 뒤집기(toCharArray())

설명

영어 알파벳과 특수문자로 구성된 문자열이 주어지면 영어 알파벳만 뒤집고,

특수문자는 자기 자리에 그대로 있는 문자열을 만들어 출력하는 프로그램을 작성하세요.

입력

첫 줄에 길이가 100을 넘지 않는 문자열이 주어집니다.

출력

첫 줄에 알파벳만 뒤집힌 문자열을 출력합니다.

입력 예시

a#b!GE*T@S

출력 예시

S#T!EG*b@a

---

My Answer - 정규식을 이용

import java.util.Scanner;

public class Main {
    public String solution(String str) {
        String  pureStr = str.replaceAll("[^a-zA-z]","");       //특수문자 제거
        StringBuilder pureStrReverse = new StringBuilder().append(pureStr).reverse();

        for(int i = 0; i < str.length(); i++) {
            if(!str.substring(i,i+1).matches("[a-zA-z]")) {
                pureStrReverse.insert(i, str.charAt(i));
            }
        }
        return pureStrReverse.toString();
    }

    public static void main(String[] args) {
        Main C = new Main();
        Scanner sc = new Scanner(System.in);
        String str = sc.next();

        System.out.println(C.solution(str));
    }
}

시간 복잡도(Big-O)

import java.util.Scanner;

public class Main {
    public String solution(String str) {
        String  pureStr = str.replaceAll("[^a-zA-z]","");       // +1
        StringBuilder pureStrReverse = new StringBuilder().append(pureStr).reverse();	// +1

        for(int i = 0; i < str.length(); i++) {			// +1, n번 반복
            if(!str.substring(i, i+1).matches("[a-zA-z]")) {		// n번 반복
                pureStrReverse.insert(i, str.charAt(i));		
            } 			
        }
        return pureStrReverse.toString();
    }

    public static void main(String[] args) {
        Main C = new Main();	
        Scanner sc = new Scanner(System.in);
        String str = sc.next(); 		// +1

        System.out.println(C.solution(str));
    }
}

(이게 new로 객체 생성되는 것도 +1로 치는걸까요...? Big-O표기법에선 상수는 없애버리지만 그래도 궁금합니다...ㅠ)

-> 2n + 4로 예상....Big-O표기법으로 => O(n)

8 ms 차이 정도는 상관없는건가요...? 궁금합니다....

---

Lecture Answer

왼쪽, 오른쪽 인덱스를 통해 변경

import java.util.Scanner;

public class Main {
    public String solution(String str) {
        String answer = "";
        char[] chArray = str.toCharArray();
        int leftIndex = 0;
        int rightIndex = str.length() - 1;
        while(leftIndex < rightIndex) {
            if(!isAlphabet(chArray, leftIndex)) {
                leftIndex++;
            } else if(!isAlphabet(chArray, rightIndex)) {
                rightIndex--;
            } else {
                char tmp = chArray[leftIndex];
                //오른쪽 왼쪽 문자 변경
                chArray[leftIndex] = chArray[rightIndex];
                chArray[rightIndex] = tmp;
                leftIndex++;
                rightIndex--;
            }
        }
        answer = String.valueOf(chArray);
        return answer;
    }

    private boolean isAlphabet(char[] chArray, int index) {
        boolean result = Character.isAlphabetic((chArray[index]));
        return result;
    }

    public static void main(String[] args) {
        Main C = new Main();
        Scanner sc = new Scanner(System.in);
        String str = sc.next();

        System.out.println(C.solution(str));
    }
}

-> O(n)