백준 23932번
https://www.acmicpc.net/problem/23932

Google Coding Practice with Kick Start Session #2 - Kick Start 2022

https://codingcompetitions.withgoogle.com/kickstart/round/00000000008f4a94/0000000000b54d3b

문제

---

Anna has a row of N blocks, each with exactly one letter from A to Z written on it. The blocks are numbered 1, 2, ..., N from left to right.

Today, she is learning about palindromes. A palindrome is a string that is the same written forwards and backwards. For example, ANNA, RACECAR, AAA and X are all palindromes, while AB, FROG and YOYO are not.

Bob wants to test how well Anna understands palindromes, and will ask her Q questions. The i-th question is: can Anna use all of the blocks numbered from Li to Ri, inclusive, rearranging them if necessary, to form a palindrome? After each question, Anna puts the blocks back in their original positions.

Please help Anna by finding out how many of Bob's questions she can answer "yes" to.

생각하기

---

• 팰린드롬이 가능한 조합을 탐색한다.
• 조합을 해서 진행할 경우 시간이 초과된다.
• 규칙은 간다하다 펠린드롬은 알파벳을 조합할 경우, 홀수 개수의 알파벳이 2개 이상일 경우 펠린드롬은 불가능하다. (즉, 홀수 하나 짝수여러개 조합 OR 짝수 조합일 경우에만 펠린드롬이 가능함)

동작

			for(int i=1; i<=N; i++) {
				for(int j=0; j<26; j++) {
					if(chArr[i-1] - 'A' == j) arr[i][j] = arr[i-1][j] + 1;
					else arr[i][j] = arr[i-1][j];
				}
			}

전체 문자열 길이N에서 총 알파벳이 들어오는 값을 2차원 배열로 만들어준다.

	private static boolean checkPalindrome(int L, int R) {
		long odd = 0; // 홀수의 개수
		for(int i=0; i<26; i++) {
			odd += (arr[R][i] - arr[L-1][i]) % 2;
		}
		
		if(odd < 2) return true;
		return false;
	} // End of checkPalindrome

L에서 R로 된 문자가 펠린드롬이 가능한지 여부를 체크하는 메소드이다.

코드

---

Java

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

public class Main {
	static int arr[][] = new int[100100][26];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());
		for(int t=1; t<=T; t++) {
			sb.append("Case #").append(t).append(": ");
			long result = 0;
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int Q = Integer.parseInt(st.nextToken());
			char chArr[] = br.readLine().toCharArray();
			
			for(int i=1; i<=N; i++) {
				for(int j=0; j<26; j++) {
					if(chArr[i-1] - 'A' == j) arr[i][j] = arr[i-1][j] + 1;
					else arr[i][j] = arr[i-1][j];
				}
			}
			
			while(Q-->0) {
				st = new StringTokenizer(br.readLine());
				if(checkPalindrome(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()))) result++;
			}
			sb.append(result).append('\n');
		}
		bw.write(sb.toString()); bw.flush(); bw.close();
	} // End of main

	private static boolean checkPalindrome(int L, int R) {
		long odd = 0; // 홀수의 개수
		for(int i=0; i<26; i++) {
			odd += (arr[R][i] - arr[L-1][i]) % 2;
		}
		
		if(odd < 2) return true;
		return false;
	} // End of checkPalindrome
} // End of Main class

Kotlin

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

private var arr : Array<IntArray> = Array(100100){IntArray(26)}
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    val sb = StringBuilder()

    var T = br.readLine().toInt()
    for(t in 0 until T) {
        var result = 0
        sb.append("Case #").append(t+1).append(": ")
        var st = StringTokenizer(br.readLine())
        var N = st.nextToken().toInt() // 전체 문자열 길이
        var Q = st.nextToken().toInt() // 질문의 수
        var chArr = br.readLine().toCharArray()

        for(i in 1..N) {
            for(j in 0 until 26) {
                if (chArr[i - 1] - 'A' == j) arr[i][j] = arr[i - 1][j] + 1
                else arr[i][j] = arr[i - 1][j]
            }
        }

        while(Q-->0) {
            st = StringTokenizer(br.readLine())
            if(checkPalindrome(st.nextToken().toInt(), st.nextToken().toInt())) result++
        }
        sb.append(result).append('\n')
    }
    bw.write(sb.toString()); bw.flush(); bw.close()
} // End of main

private fun checkPalindrome(L : Int, R : Int) : Boolean {
    var odd = 0 // 홀수의 개수
    for(i in 0 until 26) {
        odd += (arr[R][i] - arr[L-1][i]) % 2
    }

    if(odd < 2) return true;
    return false
} // End of checkPalindrome