Reference
문자열을 뒤집는 문제를 풀던 중
어떤게 가장 좋은 방법인지 궁금했다..
그래서 최대한 다양하게 알아보았다
Stack 사용
import java.util.*;
class Main {
public static void main(String[] args) {
String input = "abcde";
System.out.println(reverseUseStack(input.toCharArray()));
}
private static String reverseUseStack(char [] stringToCharArray) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < stringToCharArray.length; i++) {
stack.push(stringToCharArray[i]);
}
for (int i = 0; i < stringToCharArray.length; i++) {
stringToCharArray[i] = stack.pop();
}
return stringToCharArray.toString();
}- stack에 모든 character를 push()
- 그럼 stack의 element들을 pop()
- 초기화된 문자열에 시작 인덱스부터 저장
- 스택이 lifo인 이유로 문자열이 뒤집히는 원리
- 시간복잡도: O(n), 공간복잡도: O(n)
포인터 사용
import java.io.*;
class Main {
public static void main(String[] args) {
}
String input = "abcde";
reverseString(input);
}
private static void reverseString(String string) {
int size = string.length();
char []ch = string.toCharArray();
char temp;
for (int i = 0; j = n-1; i<j; i++; j--) {
temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}
System.out.println(ch);
}
}- String 시작과 끝에 각각 왼쪽 / 오른쪽 포인터 배치
- 왼쪽 포인터가 앞으로 1칸, 오른쪽 포인터가 뒤로 1칸 이동한 다음
- 왼쪽과 오른쪽 포인터의 character 위치 변경하는 실행을
- 오른쪽 포인터가 왼쪽 포인터 바로 앞에 도달할 때까지 반복
- 시간 복잡도: O(n), 공간 복잡도: O(1)
재귀 사용
import java.io.*;
class Main {
public static void main(String[] args) {
char[] input = "abcde".toCharArray();
recursiveReverse(input, 0);
System.out.println(input.toString());
}
private static void recursiveReverse(char[] string, int index) {
int size = string.length;
if (index == size / 2) return;
swap(string, index, size-index-1);
recursiveReverse(string, index+1);
}
private static void swap(char []arr, int index, int next) {
char temp = arr[index];
arr[index] = arr[next];
arr[next] = temp;
}
}- 문자열 중간에 도달할 때까지
- 문자열 처음과 마지막을 교환하는 동작이 작동되는 원리
- 재귀호출을 통해 수행됨
- 각 호출에서 위치 i와 n-i-1이 교환되고 i가 증가됨
- i가 n/2에 도달할 때까지 반복
- 문자열이 완전히 뒤집힘
- 시간 복잡도: O(n), 공간 복잡도: O(n)
📌 n은 문자열의 길이
API 내장함수 사용
import java.util.*;
import java.io.*;
class Main {
public static void main(String[] args) {
String string = "abcde";
StringBuffer stringBuffer = new StringBuffer(string);
stringBuffer.reverse();
System.out.println(stringBuffer.toString());
}
}왜 안되지
회문 문자열
설명
앞에서 읽을 때나 뒤에서 읽을 때나 같은 문자열을 회문 문자열이라고 합니다.
문자열이 입력되면 해당 문자열이 회문 문자열이면 "YES", 회문 문자열이 아니면 “NO"를 출력하는 프로그램을 작성하세요.
단 회문을 검사할 때 대소문자를 구분하지 않습니다.
입력
첫 줄에 길이 100을 넘지 않는 공백이 없는 문자열이 주어집니다.
출력
첫 번째 줄에 회문 문자열인지의 결과를 YES 또는 NO로 출력합니다.
예시 입력 1
gooG
예시 출력 1
YES
import java.util.*;
import java.io.*;
// 기존 문자열 == 뒤집은 문자열 검사
//
// 일치할 경우 'yes', 아닌 경우 'no' 출력
// 대소문자 구분 없이 equals() 기능 작성
// toUpperCase || toLowerCase 일치 여부도 검사하는 것으로 기능 작성
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine();
StringBuffer stringBuffer = new StringBuffer(input);
stringBuffer.reverse();
// char[] readLine = input.toCharArray();
//recursiveReverse(readLine, 0);
String reverse = stringBuffer.toString();
if (input.equalsIgnoreCase(reverse)) {
System.out.println("YES");
}
System.out.println("NO");
return ;
}
private static void recursiveReverse(char[] readLine, int index) {
int size = readLine.length;
if (index == size / 2) {
return;
}
swap(readLine, index, size-index-1);
recursiveReverse(readLine, index+1);
}
private static void swap(char []readLine, int index, int next) {
char temp = readLine[index];
readLine[index] = readLine[next];
readLine[next] = temp;
}
}내장함수로 해결
import java.util.*;
// 기존 문자열 == 뒤집은 문자열 검사
//
// 일치할 경우 'yes' 출력, 아닌 경우 'no' 출력 후 종료
// 대소문자 구분 없이 equals() 기능 작성
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine();
StringBuilder stringBuilder = new StringBuilder(input);
String reverse = stringBuilder.reverse()
.toString();
if (!isValid(input, reverse)) {
System.out.println("NO");
return;
}
System.out.println("YES");
return ;
}
private static boolean isValid(String input, String reverse) {
return input.equalsIgnoreCase(reverse);
}
}
근면성실