[자바 알고리즘 ch.1] 문자열(2)

회문 문자열, 팰린드롬

GOOG, POOP 과 같이 거울처럼 생긴 문자

• 앞에서 말한 것처럼 lt와 rt가 문자열 길이의 1/2만큼 반복할 때까지 같아야 함
• 반복문은 for(int i=0; i< len/2 ; i++)
• lt = i;
• rt = len -i -1;

str = str.toUpperCase();   // 대소문자 구분 안하기로 했을 때
int len = str.length();
for(int i=0; i< len/2 ; i++){
    if(str.charAt(i) != str.charAt(len -i -1) ) return "NO";
}

• StringBuilder을 이용하기 .equalsIgnoreCase()

String tmp = new StringBuilder(str).reverse().toString();  //원래 문자열, 뒤집은 문자열 비교
if(str.equalsIgnoreCase(tmp)) answer="YES";

팰린드롬 = 앞에서 읽을 때나 뒤에서 읽을 때나 같은 문자열

• 이번 문제의 조건은 알파벳만 검사함. 특수문자나 숫자는 상관없음
• replaceAll()에 사용한 정규식. ^는 부정 [A-Z]는 대문자 -> 합쳐서 "영어대문자가 아니면"

str = str.toUpperCase().replaceAll("^[A-Z]", "");
String tmp = new StringBuilder(str).reverse().toString();
if( str.equals(tmp) ) answer = "YES";

숫자만 추출

문자와 숫자가 섞여있는 문자열로 자연수 만들기

• 문자와 숫자가 섞여있는 문자열이 주어지면 숫자만 추출해서 그 순서대로 구성된 자연수 만들기
• 예시 tge0a1h205er -> 01205 ->1205
• 아스키문자 '0'=48, '9'=57
• answer = answer *10 + (x - 48)
• *10을 하는 이유: 자릿수를 늘리기 위해서... 1 -> 10 + 2 -> 120 + 0 -> 1200 + 5
• 아.. 이런걸 외우라는 거구나

int answer=0;
for( char x : str.toCharArray() ){
    if( x>=48 && x<==57 ) answer = answer*10 + (x-48);
}
return answer;

• 또 다른 방법 Character.isDigit(x) -> 이것이 숫자인지 판별
• String answer = ""; for( char x : str.toCharArray() ){ if( Character.isDigit(x) ) answer += x; } return Integer.parseInt(answer);

가장 짧은 문자 거리

문자열str의 각 문자가 타겟문자 target와 떨어진 거리를 순서대로 출력하기

• teachermode e
• 각각의 문자가 e로 부터 떨어진 거리를 순서대로 출력하기
• 배열 왼쪽부터 임의의 숫자 P를 제시하고 타겟 숫자와 같으면 0 , 아니면 1 증가시키면서 옆으로 이동하기
• P의 초기화는 터무니 없는 숫자로
• [1001][0][1][2][3][0][1][2][3][4][0] -> 타겟 문자 자신은 0, 아니면 옆으로 1 증가. 다시 자신이면 0
• 최소 거리를 구해야 하므로 오른쪽에서 for문이 한 번 더 돌아야 함.
• 이미 구한 값과 비교하면서 새로 구한 값이 더 작으면 수정

int[] answer = new int[str.length()];
int p = 1000;
for(int i=0; i<str.length(); i++){
    if(s.charAt(i)==target){
        p=0;
        answer[i]=p;
    } else {
        p++;
        answer[i]=p;
    }
}
p=1000; //p 다시 초기화. 오른쪽부터 다시 반복문 돌아야 하기 때문
for(int i=str.length(); i>0 i--){
    if(s.charAt(i)==target){
        p=0;
    } else {
        p++;
        answer[i]=Math.min( answer[i], p);  //양방향 비교로 얻은 값 중에서 작은 것을 대입하기
    }
}