문제
해결 방안 고민
- a와 b로만 이루어진 문자열이 주어진다.
- a를 모두 연속으로 만들기 위해 필요한 교환의 횟수를 최소로 하는 프로그램 작성
======
- a를 모두 연속적으로 만들기 위해선 먼저 주어진 문자열에서 a의 길이를 센다.
- a가 연속적이라면 교환을 통해서 해당 a의 길이만큼 연속적으로 배치가 된다.
- 예를들어, "ababab"라면 a가 3개 있으므로 a의 길이는 3이 된다.
- 따라서 a를 연속적으로 만들려면 "aaa" 형태가 되어야 한다.
- 주어진 문자열 0번째 인덱스부터 문자열 끝까지 시작하여 그 위치에서 a의 길이까지 살펴보면서 b가 있으면 b를 a와 교환해주면 연속적인 a를 만들 수 있다.
- 이때 구하는 건 교환 횟수의 최솟값이므로 b와 a를 직접 교환해주는 게 아니라, b가 있다면 b의 카운팅을 세주고 최솟값을 구하면 된다.
- ababab -> b = 1개
- ababab -> b = 2개
Markdown
복사
•
문제를 이해하는 것부터가 어려운 문제였다. 문자열이 원형이기 때문에 처음과 끝은 서로 인접해있다는 조건을 주목하여 문제풀이를 진행해야 한다.
•
해당 문제에 대한 좋은 자료가 있어서 참고해보았다.
해결 방법
•
문자열에 있는 a의 갯수를 a의 길이로 정한다.
•
교환의 횟수롤 최소로 해야 하기 때문에 최솟값 변수 하나를 만든다.
•
문자열에 있는 b의 갯수를 카운트한다.
•
최솟값을 구해야 하기 때문에 순회하면서 각각의 부분문자열 케이스별로 a를 모두 연속으로 만들기 위한 횟수를 구하는 코드를 작성하였다.
코드
package algo250217;
import java.io.*;
// 문자열 교환 - 실버 1
public class Baek1522 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String str = br.readLine();
int length = str.length();
int min = Integer.MAX_VALUE;
int aLength = 0;
for (int i = 0; i < length; i++) {
if (str.charAt(i) == 'a') {
aLength++;
}
}
for (int i = 0; i < length; i++) {
int count = 0; // b의 갯수
for (int j = i; j < aLength + i; j++) {
if (str.charAt(j % length) == 'b') {
count++;
}
}
min = Math.min(min, count);
}
bw.write(String.valueOf(min));
bw.flush();
bw.close();
br.close();
}
}
Java
복사