지난 글 : [알고리즘/Do it 알고리즘] - 도수 정렬
문자열 검색 알아보기
문자열 검색이란 어떤 문자열 안에 특정 문자열이 있는지 조사하고, 들어 있다면 그 위치를 찾는 것을 말한다. 예로 문자열 "String", "King"에서 "in"을 검색하면 문자열 검색에 성공한다. 하지만 문자열 "Queen"에서 "in"을 검색하면 문자열 검색에 실패한다. 지금부터 이해를 돕기 위해 검색할 문자열을 패턴(pattern), 문자열 원본을 텍스트(text)라 하자.
브루트 - 포스법 알아보기
텍스트 "ABACDEFGHA"에서 패턴 "ABC"를 브루트 - 포스법(brute force method)을 사용해 검색하는 과정을 간략히 살펴보자.
a
텍스트의 첫 문자 'A'부터 시작하는 3개의 문자와 "ABC"가 일치하는지 검사한다. 첫 번째 A는 'B'까지 일치하지만,
'C'는 다르다.b
패턴을 1칸 뒤로 옮긴다. 텍스트의 2번째 문자부터 3개의 문자가 일치하는지 조사한다. 'A'와 'B'가 다르다.c
패턴을 다시 1칸 뒤로 옮긴다. 'A', 'B', 'C' 모두 일치하므로 검색 성공이다.브루트 - 포스법은 선형 검색을 확장한 단순한 알고리즘이므로 단순법, 소박법이라고도 한다. 하지만 브루트 - 포스법은 이미 검사를 한 위치라도 다시 뒤로 물러나 같은 위치를 검사할 수 있기에 효율이 좋지 않다.
bfMatch 메서드는 텍스트(txt)에서 패턴(pat)을 검색해 검색에 성공하면 그 위치의 텍스트 쪽 인덱스를 반환한다. 텍스트에 패턴이 여러 개 있으면 가장 앞쪽에 위치한 텍스트 쪽 인덱스를, 검색에 실패하면 -1을 반환한다. 텍스트를 스캔하기 위한 변수로 pt를 사용하고, 패턴을 스캔하기 위한 변수로 pp를 사용한다. 두 변수를 처음에 0으로 초기화하고 스캔하거나 패턴을 옮길 때마다 업데이트한다.
문자열과 String 클래스
String s = "ABC";위처럼 String 클래스형 변수를 선언하면 초기자로 주어진 "ABC"는 문자열 리터럴이다. 문자열 리터럴은 단순히 문자가 늘어서 있는 것이 아니라 String형 인스턴스다. String 클래스는 문자열을 넣어 두기 위한 '문자 배열'을 비공개 필드로 갖고 있다.
변수 이름.length()위 메서드는 문자열의 길이를 int형 값으로 반환한다. 배열의 요솟수를 구하는 식인 '배열 이름.length'와는 전혀 다르다.
변수 이름.charAt(i)charAt 메서드는 문자열 안에서 특정 위치에 있는 문자를 가져온다. 인덱스가 i인 문자를 갖고 오며, 반환하는 문자의 형은 char형이다.
변수 이름.substring(begin)
변수 이름.substring(begin, end)substring 메서드는 문자열에서 부분 문자열을 꺼낸다. 전달받은 인수가 1개인 것과 2개인 것을 다중으로 오버로드한다. 첫 번째 메서드가 반환하는 것은 인덱스가 begin인 문자로부터 맨 끝까지의 문자열, 두 번째 메서드가 반환하는 것은 인덱스가 begin인 문자부터 end 바로 앞 문자까지의 문자열이다. 두 메서드 모두 새로 생성한 문자열 인스턴스를 반환한다.
변수 이름.equals(s)2개의 문자열을 등가 연산자(== 또는 !=)로 비교하는 경우 등가성을 판단하는 대상은 문자열의 내용이 아니라 참조하는 곳(인스턴스를 넣어 둔 곳)이다. 문자열 안에 있는 내용의 등가성을 판단하는 것이 equals 메서드다. 문자열이 s와 같으면 true를, 다르면 false를 반환한다. 이 메서드는 Object 클래스의 equals 메서드를 다중 정의한다.
변수 이름.compareTo(s)문자열과 s의 대소 관계를 '사전의 순서'에 따라 판단하고 아래처럼 값을 반환한다.
- 문자열이 s보다 작으면 음의 정숫값
- 문자열이 s보다 크면 양의 정숫값
- 문자열이 s와 같으면 0첫 번째 문자부터 순서대로 문자 코드를 비교해, 둘이 같으면 다음 문자를 비교하는 과정을 반복함으로써 문자열의 대소 관계를 판단한다. 어느 한쪽의 문자 코드가 크면 그쪽의 문자열이 더 큰것으로 판단한다.
String.indexOf 메서드로 문자열 검색하기
java.lang.String 클래스는 문자열을 검색하는 indexOf 메서드와 lastIndexOf 메서드를 제공한다.
1. int indexOf(String str)
2. int indexOf(String str, int fromIndex)
3. int lastIndexOf(String str)
4. int lastIndexOf(String str, int fromIndex)위 메서드는 모두 지정한 특정 문자열(str)이 포함되어 있는지 검색한다. 검색에 성공하면 찾은 문자열의 인덱스를, 실패하면 -1을 반환한다. 1, 3 번 메서드는 전체 문자열을 검색하고, 2, 4번 메서드는 fromIndex부터 문자열을 검색한다. 이때, 3, 4번 메더스는 같은 문자열에 대해 가장 뒤쪽에 위치한 문자열을 검색한다.
아래처럼 텍스트가 "AB개발초보DEF개발초보12"이고, 패턴이 "개발초보"라면 indexOf 메서드는 2를 반환한다. 한 행에 문자열 "AB개발초보DEF개발초보12"를 표시하고 다음 행에 반각, 곧 1바이트인 공백 문자 2개와 문자열 "개발초보"를 표시하면 아래처럼 된다. '*'는 반각 공백 문자를 의미한다.
AB개발초보DEF개발초보12
**개발초보
아래는 1, 3번 메서드를 사용해 작성한 프로그램이다.
위 프로그램을 실행하면 반각 문자는 1바이트의 바이트 배열로, 전각 문자는 2바이트의 바이트 배열로 변환된다. 따라서 바뀐 배열의 길이를 length 메서드로 구하면 검색 대상의 문자가 1바이트인지 2바이트인지 알 수 있가. 이렇게 얻은 값을 for문으로 반복해 누적하고, 그 누적한 값에 문자열 s2의 길이를 더한 것이 len1이다. 문자열 s2를 문자의 너비로 표시하면 아래처럼 정리할 수 있다.
AB개발초보DEF개발초보12
**개발초보
- 반각 공백 문자(*) 2개와 전각 문자(한글) 4개가 출력된다.
참고 서적 :
