[백준] 1522. 문자열 교환 (자바 JAVA)

[ 문제 ]  [백준] 1522. 문자열 교환 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/1522

1522번: 문자열 교환

---

# 접근 방법 및 풀이 

 

• 아이디어를 떠올리기가 어려운 문제다.
• 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개
• ababab -> b = 1개
• ababab  -> b =  2개
• ababab  -> b = 1개
• ababab  -> b = 2개
• 위와 같이 0인덱스부터 끝 인덱스 까지 살펴보면서 b의 개수를 카운팅해주고 그때 b의 최솟값이 최소의 교환회수가 된다.
• 자세한건 코드참조

 

 

# 주의할 점 

 

• 문자열이 원형으로 이어져있으므로 나머지 연산자를 통해서 주어진 문자열의 범위에 넘어가면 다시 0번째 부터 살펴볼 수 있도록 구해야함.

 

JAVA 코드

package Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class bj1522_문자열교환 {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String s = in.readLine();
		int min = Integer.MAX_VALUE;
		int a_len = 0;
		for(int i = 0; i < s.length(); i++) {
			if(s.charAt(i) == 'a')
				a_len++;
		}
		for (int i = 0; i < s.length(); i++) {
			int b_cnt = 0;
			for (int j = i; j < a_len+i; j++) {
				if(s.charAt(j % s.length()) == 'b')
					b_cnt++;
			}
			min = Math.min(min, b_cnt);
		}
		System.out.println(min);
	}
}

 

 

 

REVIEW

풀면 풀수록 새로운 문제 천지구나~~

a와 b를 어떻게 교환하지?에서 머물러있으면 이렇게 못풀듯..