2. 문자열 다루어 보기
1) 문자열 응용하기
String 클래스에서 많이 사용되는 메서드
| 메서드 | 반환형 | 내용 |
| equals(String other) | boolean | 문자열이 other와 같은 문자열을 담고 있는지 반환 |
| length() | int | 문자열 길이를 반환 |
| substring(int beginIndex, int endIndex) | String | 문자열의 beginIndex부터 endIndex까지 잘라서 반환 |
| toUpperCase() | String | 모든 알파벳이 대문자로 반환된 문자열을 반환 |
| toLowerCase() | String | 모든 알파벳이 소문자로 반환된 문자열 |
문제 8) 문자열 압축
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
● 문제 풀이
- 이 문제의 핵심은 문자열을 정해진 길이만큼 잘라 내는 것
- 압축했을 때 가장 짧은 문자열의 길이를 구해야 하는데, 이는 모든 길이에 대해 압축을 시도한 후 그중 가장 짧은 길이를 선택하면 된다.
문제 풀이 흐름
1. 1부터 입력 문자열 s의 길이만큼 자를 문자열의 길이를 설정하여 반복
2. 설정된 길이만큼 문자열을 잘라 낸 token의 배열 생성
3. 문자열을 비교하며 token의 배열을 하나의 문자열로 압축
4. 1~3 과정으로 압축된 문자열 중 가장 짧은 길이 반환
코드 작성
1. 1부터 입력 문자열 s의 길이만큼 자를 문자열의 길이를 설정하며 반복
- 먼저 자를 문자열의 길이를 반복문을 이용하여 설정하고, 가장 짧은 압축 문자열의 길이를 담을 min 변수를 선언하고 반환한다.
- 자를 문자열의 길이는 최소 1부터 시작하여 문자열 전체 길이를 포함하도록 반복한다.
int min = Integer.MAX_VALUE;
for(int len=1;len<=s.length; len++) {
//문자열 압축 후 가장 짧은 길이 선택
}
return min;
- 문자열을 압축하고, 압축된 문자열의 길이를 반환하는 compress() 메서드를 선언
private int compress(String source, int len) {
//압축한 문자열의 길이 반환
}
2. 설정된 길이만큼 문자열을 잘라 낸 token의 배열 생성
- 압축하려면 우선 len 길이씩 문자열을 잘라야 한다. 다음과 같이 문자열을 len 길이씩 잘라 리스트에 담아 주는 split() 메서드를 선언한다.
private List<String> split(String source, int len) {
List<String> tokens = new ArrayList<>();
//source를 len만큼씩 잘라 tokens 리스트에 추가
return tokens;
}
- 문자열을 자르는 시작 인덱스는 0부터 시작하여 len만큼씩 증가한다. 따라서 다음 반복문으로 모든 startIndex를 순회할 수 있다.
for(int startIndex = 0; startIndex < source.length(); startIndex+=len) {
//문자열을 startIndex부터 잘라 tokens 리스트에 추가
}
- 이때 endIndex는 startIndex+len이지만, 이것이 문자열 범위 밖이라면 문자열의 끝까지 정상적으로 잘릴 수 있도록 다음과 같이 작성한다.
for(int startIndex = 0; startIndex < source.length(); startIndex+=len) {
int endIndex = startIndex+len;
if(endIndex>source.length()) endIndex = source.length();
//문자열을 startIndex부터 잘라 tokens 리스트에 추가
}
- 이제 실제로 문자열을 잘라 tokens 리스트에 추가한다.
for(int startIndex = 0; startIndex < source.length(); startIndex+=len) {
int endIndex = startIndex+len;
if(endIndex>source.length()) endIndex = source.length();
tokens.add(source.substring(startIndex, endIndex));
}
- 완성된 split() 메서드를 사용하여 compress() 메서드에서는 tokens 리스트를 만들고, 문자열을 구성할 StringBuilder 객체를 생성한다.
private int compress(String source, int len) {
StringBuilder sb = new StringBuilder();
for(String token : split(source,len)) {
//압축 문자열 구성
}
return sb.length();
}
3. 문자열을 비교하며 token의 배열을 하나의 문자열로 압축
- 연속으로 중복된 문자열을 검사해야 하므로 직전에 등장한 문자열을 담는 last 변수와 그 등장 횟수를 담는 count 변수를 선언한다.
String last = ""; //직전에 등장한 문자열을 담음
int count = 0; //등장 횟수
for(String token : split(source,len)) {
//압축 문자열 구성
}
- 현재 검사하는 문자열 token이 직전에 등장한 문자열과 같다면 등장 횟수만 증가해주면 된다.
for(String token : split(source,len)) {
if(token.equals(last)) {
count++;
}else {
//새로운 토큰 등장 처리
}
}
- 새로운 토큰이 등장했다면 직전까지 등장한 문자열을 이용하여 압축 문자열을 구성해준다. 이때 등장 횟수 count는 2 이상일 때만 압축 문자열에 포함되고, 압축 문자열을 구성한후에는 현재 검사한 token부터 다시 셀 수 있도록 last와 count를 업데이트 해야 한다.
for(String token : split(source,len)) {
if(token.equals(last)) {
count++;
}else {
if(count>1) sb.append(count);
sb.append(last);
last = token;
count = 1;
}
}
- 이렇게 for 문을 나오면 아직 마지막 토큰은 last에 담긴 채로 압축 문자열에 포함되지 않은 상태이다. 따라서 압축 문자열을 구성하는 로직을 for문 이후에 1회 더 추가해야 한다.
for(String token : split(source,len)) {
if(token.equals(last)) {
count++;
}else {
if(count>1) sb.append(count);
sb.append(last);
last = token;
count = 1;
}
}
if(count>1) sb.append(count);
sb.append(last);
4. 1~3 과정으로 압축된 문자열 중 가장 짧은 길이 반환
- solution() 메서드에서는 이를 사용하여 각 토큰 길이별로 압축 문자열의 길이를 구하고, 가장 짧은 길이를 반환하면 된다.
int min = Integer.MAX_VALUE;
for(int len=1;len<=s.length(); len++) {
int compressed = compress(s, len);
if(compressed < min) {
min = compressed;
}
}
return min
}
전체 코드
import java.util.ArrayList;
import java.util.List;
class Solution {
private List<String> split(String source, int len) {
List<String> tokens = new ArrayList<>();
//source를 len만큼씩 잘라 tokens 리스트에 추가
for(int startIndex = 0; startIndex < source.length(); startIndex+=len) {
int endIndex = startIndex+len;
if(endIndex>source.length()) endIndex = source.length();
//문자열을 startIndex부터 잘라 tokens 리스트에 추가
tokens.add(source.substring(startIndex, endIndex));
}
return tokens;
}
private int compress(String source, int len) {
StringBuilder sb = new StringBuilder();
String last = ""; //직전에 등장한 문자열을 담음
int count = 0; //등장 횟수
for(String token : split(source,len)) {
if(token.equals(last)) {
count++;
}else {
if(count>1) sb.append(count);
sb.append(last);
last = token;
count = 1;
}
}
if(count>1) sb.append(count);
sb.append(last);
return sb.length();
}
public int solution(String s) {
int min = Integer.MAX_VALUE;
for(int len=1;len<=s.length(); len++) {
int compressed = compress(s, len);
if(compressed < min) {
min = compressed;
}
}
return min;
}
}
2) 진법 바꾸기
- 문자열을 이용하면 특정 진법으로 숫자를 나타낼 수 있다. 또 각 진법별로 아주 쉽게 변환할 수 있다.
문자열과 정수를 진법에 따라 변환하는 메서드
| 메서드 | 반환형 | 내용 |
| Integer.parseInt(String s, int radix) | int | radix 진법으로 숫자를 표현하는 문자열 s를 정수로 변환 |
| Integer.toString(int v, int radix) | String | 정수 v를 radix 진법의 문자열로 변환 |
| Long.parseLong(String s, int radix) | long | radix 진법으로 숫자를 표현하는 문자열 s를 정수로 변환 |
| Long.toString(long v, int radix) | String | 정수 v를 radix 진법의 문자열로 변환 |
ex) 2진수로 표현된 문자열을 16진수로 변경
String binary = "1010";
int value = Integer.parseInt(binary, 2);
String hex = Integer.toString(value, 16);
문제 9) 3진법 뒤집기
코딩테스트 연습 - 3진법 뒤집기 | 프로그래머스 스쿨
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
● 문제 풀이
문제 풀이 흐름
1. 정수를 3진법으로 변환
2. 변환된 문자열 뒤집기
3. 뒤집은 문자열을 정수로 변환
전체 코드
class Solution {
public int solution(int n) {
StringBuilder sb = new StringBuilder();
//10진수 -> 3진수
String str = Integer.toString(n,3);
//문자열 뒤집기
String reversed = new StringBuilder(str).reverse().toString();
//reversed 문자열 10진수로 변환
int answer = Integer.parseInt(reversed,3);
return answer;
}
}
문제 10) 이진 변환 반복하기
코딩테스트 연습 - 이진 변환 반복하기 | 프로그래머스 스쿨
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
● 문제 풀이
문제 풀이 흐름
1. 검사하는 문자열이 "1"이 될 때까지 반복
A. 문자열에 포함된 0의 개수 세기
1) 0의 개수와 제거 횟수 누적
B. 나머지 1의 개수를 사용해서 2진법으로 변환하여 1부터 반복
2. 누적된 제거 횟수와 0의 개수를 배열로 반환
코드 작성
- 반환해야 하는 값인 변환 횟수와 제거된 0의 개수를 담는 변수를 선언하고, 배열의 형태로 반환
public int[] solution(String s) {
int loop = 0;
int removed = 0;
//s가 "1"이 될 때까지 반복하며 loop, removed 누적
return new int[]{loop,removed
}
1. 검사하는 문자열이 "1"이 될때까지 반복
- s가 "1"이 될 때까진 반복하는 것은 문자열 비교 메서드 equals()를 사용하여 다음과 같이 작성할 수 있다.
while(!s.equals("1")){
//s 변환하여 loop, removed 누적
}
1-A. 문자열에 포함된 0의 개수 세기
- 문자열 변환의 첫 번째 단계는 문자열에 포함된 0의 개수를 세는 것이다.
- 0의 개수를 세기 위해 문자열을 전달받아 0의 개수를 세는 countZeros() 메서드를 정의한다.
//0의 개수 세기
private int countZeors(String s) {
int zeros = 0;
for(char c : s.toCharArray()) {
if(c=='0') zeros++;
}
return zeros;
}
1-A-(1). 0의 개수와 제거 횟수 누적
- 이 메서드를 사용하여 변환할 때 변환 횟수와 제거된 0의 개수를 누적해줄 수 있다.
while(!s.equals("1")){
int zeros = countZeros(s);
loop+=1;
removed+=zeros;
//문자열 s 반환
}
1-B. 나머지 1의 개수를 사용해서 2진법으로 변환하여 1부터 반복
- 0의 개수를 알고 있으므로 1의 개수도 구할 수 있다. 또 구한 1의 개수를 2진법으로 변환하여 s를 변환할 수 있다.
while(!s.equals("1")){
int zeros = countZeors(s);
loop+=1;
removed+=zeros;
int ones = s.length() - zeros;
s = Integer.toString(ones,2);
}
2. 누적된 제거 횟수와 0의 개수를 배열로 반환
- 앞서 작성한 solution() 메서드에서 배열을 반환한다.
전체 코드
class Solution {
//0의 개수 세기
private int countZeors(String s) {
int zeros = 0;
for(char c : s.toCharArray()) {
if(c=='0') zeros++;
}
return zeros;
}
public int[] solution(String s) {
int loop = 0;
int removed = 0;
while(!s.equals("1")){
int zeros = countZeors(s);
loop+=1;
removed+=zeros;
int ones = s.length() - zeros;
s = Integer.toString(ones,2);
}
return new int[]{loop,removed};
}
}
3) 찾기와 바꾸기
포함여부를 검사하는 메서드
| 메서드 | 반환형 | 내용 |
| contains(CharSequence s) | boolean | 전달받은 문자열이 원본 문자열에 있는지 검사 |
| startsWith(String prefix) | boolean | 원본 문자열이 전달받은 문자열로 시작하는지 검사 |
| endsWith(String suffix) | boolean | 원본 문자열이 전달받은 문자열로 끝나는지 검사 |
| indexOf(String str) | int | 전달받은 문자열이 원본 문자열에서 몇 번째 인덱스에 있는지 검사 |
문자열 치환 메서드
| 메서드 | 반환형 | 내용 |
| replace(char oldChar, char newChar) | String | 원본 문자열의 oldChar 문자들을 newChar 문자로 치환한 문자열을 반환 |
| replace(CharSequence target, CharSequence replacement) | String | 원본 문자열에서 등장하는 target 문자열을 replacement 문자열로 치환해서 반환 |
문제 11) 문자열 내 p와 y의 개수
코딩테스트 연습 - 문자열 내 p와 y의 개수 | 프로그래머스 스쿨
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
● 문제 풀이
문제 풀이 흐름
1. 문자열을 모두 소문자로 변환
2. "p"의 개수 세기
A. 문자열에 등장하는 모든 "p"를 빈 문자열 " "로 치환
B. 원본 문자열과 변환된 문자열의 길이 차이가 p의 개수
3. 2와 같은 방식으로 y의 개수 세기
4. 구한 p의 개수와 y의 개수 비교
전체 코드
class Solution {
boolean solution(String s) {
s = s.toLowerCase(); //소문자로 변경
int ps = s.length() - s.replace("p","").length();
int ys = s.length() - s.replace("y","").length();
return ps==ys;
}
}
문제 12) 숫자 문자열과 영단어
코딩테스트 연습 - 숫자 문자열과 영단어 | 프로그래머스 스쿨
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
● 문제 풀이
문제 풀이 흐름
1. 각 인덱스 값에 해당하는 영단어가 저장되어 있는 영단어 문자열 배열을 구성
2. 영단어 배열을 순회하며 입력 문자열에 등장하는 모든 영단어를 치환한 문자열 생성
3. 변환된 문자열을 정수로 변환한 후 반환
전체 코드
public class Solution {
//각 인덱스 값에 해당하는 영단어가 저장되어 있는 영단어 문자열 배열
private static final String[] words = {
"zero","one","two","three","four",
"five","six","seven","eight","nine",
};
public int solution(String s) {
//영단어 배열을 순회하면서 입력 문자열에 등장하는 모든 영단어를 치환한 문자열 생성
for(int i=0; i<words.length; i++) {
s = s.replace(words[i],Integer.toString(i));
}
//반환된 문자열을 정수로 변환한 후 반환
return Integer.parseInt(s);
}
}
4) 정규 표현식
- 정규 표현식은 문자열 패턴을 나타내는 표현 방식이다. 정규 표현식을 이용하면 복잡한 문자열도 쉽게 검색할 수 있다.
자주 사용되는 정규표현식
| 정규표현식 | 내용 |
| . | 개행 문자를 제외한 아무 문자 |
| [abc] | a,b,c 중 아무것이나 |
| [^abc] | a,b,c를 제외하고 |
| [a-g] | a,g 사이의 문자들 [0-9] -> 모든 숫자 [a-z] -> 모든 소문자 [A-Z] -> 모든 대문자 |
| a* | a 0개 이상 |
| a+ | a 1개 이상 |
| a? | a 0개 또는 1개 |
| a{5} | a 5개 |
| a{2,} | a 2개 이상 |
| a{2,4} | a 2개 이상 4개 이하 |
| ab|cd | ab 또는 cd |
| ^a | 문자열의 처음 문자가 a |
| a$ | 문자열의 마지막 문자가 a |
| \ | 사전 정의된 문자를 표현하는 이스케이프 시퀀스 |
String 클래스의 정규표현식 관련 메서드
| 메서드 | 반환형 | 내용 |
| replaceAll(String regex, String replacement) | String | 전달받은 정규표현식에 매칭되는 패턴을 모두 replacement로 치환 |
| matches(String regex) | boolean | 문자열이 전달받은 정규표현식에 매칭되는지 여부를 반환 |
| split(String regex) | String[ ] | 전달받은 정규표현식이 매칭되는 패턴을 기준으로 원본 문자열을 잘라서 반환 |
ex) 문자열이 모두 소문자인지 검사하는 코드
boolean matches = s.matches("[a-z]*");
'Java > 알고리즘' 카테고리의 다른 글
| [PCCP 대비] ch 4. 문자열 (1) (0) | 2024.11.24 |
|---|---|
| [PCCP 대비] ch 3 배열 (2) (1) | 2024.11.23 |
| [PCCP 대비] ch 3. 배열 (1) (2) | 2024.11.10 |
| [자바 알고리즘 인터뷰] 12장 그래프 (9) 코스 일정 (0) | 2024.05.18 |
| [자바 알고리즘 인터뷰] 12장 그래프 (8) 여행 경로 (0) | 2024.05.18 |
