[262가지 문제로 정복하는 코딩 인터뷰 간단요약] 6장 문자열

문자열 라이브러리 이해하기

- Java 문자열 String은 암묵적으로 불변이므로, StringBuilder를 활용하여 가변적으로 다루도록한다.

 

- 가변 문자열을 앞에서 부터 갱신해 나가는 방법은 느리므로 가능한 뒤에서부터 쓰는 것이 좋다.

 

+ String 핵심 메서드  

charAt()
compareTo()
contains()
endWith()
indexOf()
indexOff()
lastIndexOf
length()
replace()
split()
startsWith()
substring()	시작인덱스는 포함하지만 마지막인덱스 포함하지 않음 주의
toCharArray()
toLowerCase()
trim()

 

+ StringBuilder 핵심메서드

append()
charAt()
delete()
deleteCharAt()
insert()
replace()
toString()

 

---

6.1 문자열과 정수 상호 전환하기

문자열로 주어진 정수형 숫자(음의 정수 포함) <-> 정수형 숫자 바꾸기
(라이브러리 사용하지 않기)

* 자릿수 이용

- 정수를 문자열로 : 양의 정수 x의 최하위 숫자는 x mod 10로 표현되고, 나머지 숫자는 x / 10으로 표현된다.

한글자씩 떼서 char로 변환('0'을 더해서) 후 Stringbuilder로 붙인다. 이 경우 역순이 되므로 마지막에 한번 뒤집어 준다(reverse())

- 문자열을 정수로 : 가장 오른쪽 숫자부터 10^i * d_i 를 반복적으로 더해주기

또는 왼쪽부터 시작하여 10곱하고 더하기 반복("314" => 3 *10 + 1 (31) => 31 * 10 + 4 = 314)

음수의 경우는 부호를 기억한뒤 마지막에 붙여주면 됨

 

6.2 밑수 바꾸기

문자열 하나와 두개의 정수 b1, b2가 주어졌을 때, 정수의 밑수 바꾸기

10진수 시스템을 밑수가 b인 숫자 시스템으로 일반화 할 수 있다.

 

6.3 스프레드시트 열 인코딩 계산하기

스프레드시트의 열값이 문자열로 주어졌을 때, 정수값으로 변환하기(단 "A"는 1을 나타낸다. )

힌트 : ["A" , "Z"]에는 26개의 문자가 존재하고, 각 문자는 어떤 숫자로 대응된다.

- 무식하게 주어진 문자열이 나올 때까지 나열해보기(시간복잡도 O(26^n))

- 자릿수 쪼개서 result * 26 + c - 'A' + 1 반복(시간복잡도 O(n))

 

6.4 문자열 바꾸고 삭제하기

 

6.5 회문 확인하기

회문 : 알파벳이 아닌 문자들을 모두 제거했을 때 앞뒤로 읽은 결과가 같은 경우를 말함

문자열 s가 주어졌을 때 이 문자열이 회문인지 확인하는 함수구하기

- 간단한 방법은 s를 역순 나열 후 알파벳만 비교

- 변수 두개 사용하여 하나는 앞에서부터, 하나는 뒤에서 부터 읽으며 같은지 비교

 

6.6 문장의 모든 단어 뒤집기

문자열 s의 단어를 모두 뒤집는 함수 구하기

예) Alice likes Bob -> Bob likes Alices

- 전체 뒤집기 후 문자열의 각 단어 뒤집기

 

6.7 문자열 전화번호로 단어 조합하기

 

 

6.8 개미수열 문제

개미수열(look and say) : 1부터 시작, 다음 수열은 이전 수열에서 나타난 숫자와 해당 숫자가 연속으로 쓰인 갯수를 함께 씀

정수 n이 주어졌을 때 n개의 개미수열을 문자열로 출력하는 프로그램 작성하기

예) 8 => 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211

힌트 : 정수가 아닌 문자열로 출력하면 된다.

- 위의 규칙을 n-1번 적용하면 n번째 수열을 쉽게 구할 수 있다.

- i+1번째 수열을 만들 때는 i번째 수열의 최상위 숫자부터 시작해서 연속된 숫자의 개수와 해당 숫자를 같이 적어주면 된다.

 

6.9 로마 숫자를 10진수로 바꾸기

유효한 로마숫자가 문자열로 주어졌을 때, 이에 상응하는 정수 반환하기

I는 V 혹은 X 바로 전에 올 수 있다.

X는 L 혹은 C 바로 전에 올 수 있다.

C는 D 혹은 M 바로 전에 올 수 있다.

또한 IXC 혹은 CDM 처럼 예외가 연달아 나오는 경우엔 불가능(예외처리 필요)

 

(로마 숫자는 각 문자에 대응하는 숫자 더하면 되는데, 위의 예외상황에서는 큰 수에서 작은 수를 뺀 결과를 더해주면 된다.)

- 무식하게 문자열 왼쪽에서 읽으면서 해당문자에 대응하는 숫자 더해주고 예외상황 처리하기

- 문자열 오른쪽에서 거꾸로 읽으면서 전보다 숫자가 작은 경우 전체결과에서 빼주고, 아니면 더해준다.(시간복잡도 O(n))

 

6.10 유효한 IP주소 구하기

IP주소 특징 : 네 개의 10진수 숫자를 세 개의 마침표로 구분

문자열로 주어진 IP 주소에 마침표를 추가할 경우 가능한 모든 IP 주소를 출력하라. 유효한 IP 주소가 한 개 이상이라면 전부 출력

힌트 : 중첩 반복문 사용

- 문자열에서 모든 위치에 마침표 찍어본 뒤 나누어진 숫자 네 개가 0과 255사이에 있는지 확인

(가능한 IP 주소는 정확히 2^32개이므로 상수 시간 복잡도는 O(1)이 된다.)

 

6.11 사인 곡선 형태로 문자열 작성하기

문자열 s를 사인 곡선 형태(sine curve)로 작성해보기 

힌트 : 규칙 찾기

- 무식하게 3 * n 크기 2차원 배열을 초기화 후 우선순서로 읽기(시간복잡도 O(n))

예) HELLO WORLD -> 첫번째 줄 : s[1], s[5], s[9] 출력 / 두번째 줄 : s[0], s[2], s[4] 출력 / 세번째줄 : s[3], s[7], s[11] 출력

 

6.12 반복 길이 부호화로 문자열을 압축,해제하기

반복 길이 부호화(RLE, Run-lenght encoding) : 압축 및 해제를 실시간으로 수행할 수 있는 효과적 압축 방법

(실제 문자열 대신 문자와 해당 문자의 연속 등장 횟수를 함께 써주면 된다.)

반복 길이 부호화를 사용해서 문자열의 압축 해제를 구현하라

힌트 : 2진수 문자열 형태 혹은 그 반대로 바꾸는 방법과 비슷하게 풀기

- 숫자가 나오면 정수로 바꾼 후 숫자만큼 문자열을 출력하기(압축 해제)

- 같은 문자열의 개수 센 뒤 숫자를 문자열로 바꿔 달아주기(압축)

 

6.13 부분 문자열이 첫 번째로 등장한 위치 찾기

검색할 문자열 s와 텍스트 t가 주어졌을 때, t에서 s가 처음 나타나는 위치를 찾아보라

힌트 : 문자열의 해시값 사용

- 무식하게 두 개의 중첩 반복문 사용(첫번째는 텍스트 t의 시작 인덱스 가리키고, 두번째는 s가 t의 부분 문자열과 같은지 확인)

- KMP, Boyer-Moore, Rabin-karp 알고리즘( 두번째 반복문을 줄여준다)