백준 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.
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
로 된 문자가 펠린드롬이 가능한지 여부를 체크하는 메소드이다.
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
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