BAEKJOON / 백준 - JAVA 31846번 문자열 접기

2024.06.20기준 - 실버4

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 종이 위에 적힌 글씨를 한 번만 접었을 때 맞닿은 쌍의 개수가 가장 많은 개수를 출력하는 문제입니다.

 

1. 부분 문자열을 따로 저장했습니다.

while (t-- > 0) {
    st = new StringTokenizer(br.readLine());
    int l = Integer.parseInt(st.nextToken());
    int r = Integer.parseInt(st.nextToken());

    sub = new char[r - l + 1];
    for (int i = l - 1; i < r; i++) { // 부분 문자열 저장
        sub[i + 1 - l] = arr[i];
    }

    sb.append(function(sub)).append("\n");
}

 

2. 부분 문자열을 제한된 범위 안에 반으로 접었을 때, 가장 글자가 많이 겹치는 수를 함수를 통해 구했습니다.

// 반을 접었을 때 나올 수 있는 최대값을 구하는 함수
private static int function(char[] arr) {
    char[] one, two; // one: 접히지 않는 부분, two: 접힌 부분
    int count = 0, subCount;

    for (int i = 0; i < arr.length; i++) {
        subCount = 0;
        one = new char[i + 1];
        two = new char[arr.length - one.length];

        for (int j = 0; j < arr.length; j++) {
            if (j <= i) { 
                one[j] = arr[j];
            } else { // 접히는 부분이기 때문에 뒤에서 부터 저장한다.
                two[two.length - j + i] = arr[j];
            }
        }

        // 접힌 뒷 부분을 비교하기 때문에 마지막 인덱스 끼리 비교한다.
        for (int j = 0; j < (one.length > two.length ? two.length : one.length); j++) {
            if (one[one.length - 1 - j] == two[two.length - 1 - j]) { // 접혔을때 서로 값이 같으면 ++
                subCount++;
            }
        }

        count = Math.max(count, subCount);
    }

    return count;
}

 

첫 번째 for문에서 접을 위치를 전부 계산해주고 2개의 배열에 접히지 않은 종이와 접힌 종이를 따로 저장해 2개를 서로의 마지막 인덱스로 비교하여 count를 올려주고 그 중에 가장 큰 값을 반환하도록 해주었습니다.

 

3. ABAACA가 들어 왔을 때 1 6이 입력되었다면.

 

1. 1번째 인덱스부터 6번째 인덱스 까지 사이에 접을 수 있는 경우의 수는 (1, 2),(2, 3),(3, 4),(4, 5),(5, 6) 총 5개가 나옵니다.

 

(1, 2)를 접었을 떄,

접히지 않은 종이는 A, 접힌 종이는 ACAAB가 나오게되며 짝지어지는 문자열은 0입니다.

 

(2, 3)을 접었을 때,

접히지 않은 종이는 AB, 접힌 종이는 ACAA가 나오게되며 짝지어지는 문자열은 (A,A)로 1입니다.

 

(3, 4)를 접었을 때,

접히지 않은 종이는 ABA, 접힌 종이는 ACA가 나오게되며 짝지어지는 문자열은 (A,A), (A,A)로 2입니다.

 

(4, 5)를 접었을 때,

접히지 않은 종이는 ABA A , 접힌 종이는 AC가 나오게되며 짝지어지는 문자열은 (A,A)로 1입니다.

 

(5, 6)을 접었을 때,

접히지 않은 종이는 ABA A , 접힌 종이는 AC가 나오게되며 짝지어지는 문자열은 0입니다.

 

그렇게 접히는 부분에 따라 제일 많이 겹치는 문자열 수는 2입니다.

 

 

코드

package Main;

import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine()); // 문자열의 길이
		char[] arr = br.readLine().toCharArray(); // 문자열
		int t = Integer.parseInt(br.readLine()); // 테이스 케이스 개수
		
		char[] sub; // l에서 r까지 문자열을 저장할 배열
		StringTokenizer st;
		while (t-- > 0) {
			st = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());
			
			sub = new char[r - l + 1];
			for (int i = l - 1; i < r; i++) { // 부분 문자열 저장
				sub[i + 1 - l] = arr[i];
			}
			
			sb.append(function(sub)).append("\n");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 반을 접었을 때 나올 수 있는 최대값을 구하는 함수
	private static int function(char[] arr) {
		char[] one, two; // one: 접히지 않는 부분, two: 접힌 부분
		int count = 0, subCount;
		
		for (int i = 0; i < arr.length; i++) {
			subCount = 0;
			one = new char[i + 1];
			two = new char[arr.length - one.length];
			
			for (int j = 0; j < arr.length; j++) {
				if (j <= i) { 
					one[j] = arr[j];
				} else { // 접히는 부분이기 때문에 뒤에서 부터 저장한다.
					two[two.length - j + i] = arr[j];
				}
			}
			
			// 접힌 뒷 부분을 비교하기 때문에 마지막 인덱스 끼리 비교한다.
			for (int j = 0; j < (one.length > two.length ? two.length : one.length); j++) {
				if (one[one.length - 1 - j] == two[two.length - 1 - j]) { // 접혔을때 서로 값이 같으면 ++
					subCount++;
				}
			}
			
			count = Math.max(count, subCount);
		}
		
		return count;
	}
}