[SWEA 1215] 회문1 - Palindrome을 이해하기까지

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14QpAaAAwCFAYi 

SW Expert Academy

 

Palindrome 회문 또는 팰린드롬은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말이다.
보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다. (위키피디아)

 

 

먼저 10개의 테스트를 돌릴 수 있게 for문을 만들고

찾아야 하는 회문의 길이와 테스트 케이스를 입력받아야겠죠?

그래서 회문 길이를 int형 findNum 변수에 넣고, 8 * 8의 2차원 배열에 테스트 케이스들을 입력받았습니다

 

import java.util.Scanner;

public class Palindrome1 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        
        for(int num = 1; num <= 10; num++) {
            int findNum = sc.nextInt();
            //sc.nextLine();
            
            int count = 0;
            boolean flag = true;
            
            char[][] array = new char[8][8];
            
            //배열에 입력
            for(int i = 0; i < array.length; i++) {
                String str = sc.next(); //nextLine() //a[i] = sc.next().toCharArray();
                for(int j = 0; j < array[i].length; j++) {
                    array[i][j] = str.charAt(j);
                }
            }
            
            //출력
            System.out.println("#" + num + " " + count);
        }
    }
}

 

 

가장 먼저 생각한 건 특정 지점 예를 들어 (i, j)를 기준으로

가로(행)에서의 회문을 모두 구하고

세로(열)에서의 회문의 개수를 모두 구해서 그 합으로 총 회문의 개수를 구해보자라고 생각했어요

 

 

import java.util.Scanner;

public class Palindrome1 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        
        for(int num = 1; num <= 10; num++) {
            int findNum = sc.nextInt();
            // 아래 str을 nextLine()으로 받으면 줄바꿈 문제 때문에 여기서 nextLine() 한 번 해줘야 함
            //sc.nextLine(); 
            
            int count = 0;
            boolean flag = true;
            
            char[][] array = new char[8][8];
            
            //배열에 입력
            for(int i = 0; i < array.length; i++) {
                String str = sc.next(); //a[i] = sc.next().toCharArray();
                for(int j = 0; j < array[i].length; j++) {
                    array[i][j] = str.charAt(j);
                }
            }
            
            //가로 
            for(int i = 0; i < array.length; i++) {
                for(int j = 0; j < array.length - findNum + 1; j++) {
                    flag = true;
                    for(int h = 0; h < findNum / 2; h++)
                        if(array[i][j + h] != array[i][j - h + findNum - 1])
                            flag = false;
                    if(flag) count++;
                }
            }
            
            //세로 
            for(int i = 0; i < array.length - findNum + 1; i++) {
                for(int j = 0; j < array.length; j++) {
                    flag = true;
                    for(int h = 0; h < findNum / 2; h++)
                        if(array[i + h][j] != array[i - h + findNum - 1][j])
                            flag = false;
                    if(flag) count++;
                }
            }
            
            System.out.println("#" + num + " " + count);

        }
    }
}

 

 

자 가로에 회문이 몇 개 있나 찾아볼게요

총 8 * 8의 2차원 배열에서 (i, j), (행, 열), (0,0)을 시작으로 이중 for문을 돌면서 모든 배열을 지나쳐 가겠죠?

그런데! 생각해보면 열의 처음부터 끝까지 돌 필요는 없어요

예를 들어 회문의 길이가 4인 문자열이 회문인지 아닌지 찾는 다면

총 '5번'만 가도 그 행의 길이만큼의 문자열들을 다 둘러보고 올 수 있는 거죠

 

1일 때 → 8번

2 → 7

3 → 6

4 → 5

5 → 4

6 → 3

7 → 2

8 → 1

 

즉 j는 array.length인 배열의 마지막 방까지 뒤져볼게 아니라

array.length - findNum + 1만큼만 뒤져도 그 행의 모든 문자열 쌍들을 찾을 수 있어요!

 

아래 문자열이 회문인지 아닌지 판단을 해봅시다.

 

0	1	2	3	4
C	A	B	A	C

 

위와 같은 문자 배열이 있습니다

이 문자열을 반으로 똑! 접었어요

접었을 때 맞물리는 문자열이 같다면 이 문자열은 회문일 것입니다

 

즉, 문자 배열의 가장 처음 0번째 방의 값과 마지막 4번 방의 값이 같고

1번 방의 값과 3번 방의 값이 같다면

나머지 2번 방은 중심이니까 볼 것도 없이 이건

앞으로 읽어도 뒤로 읽어도 똑같은 회문입니다!

 

for문으로 돌린다면 0부터 시작해서 findNum을 2로 나눈 '반'만 돌리는 것입니다

 

자 이제 이 문자열이 회문이라면 true를 반환하게 하고, 아니라면 false를 반환하게 해서 회문인지 아닌지 판별을 합니다

for문의 끝까지 돌리고도 true라면 회문이기에 count(회문의 개수를 세는 변수)를 ++

중간에 하나라도 틀려서 false가 된다면 절대 회문이 될 수 없죠

 

아래는 가로 세로를 한 번에 처리한 코드이다.

 

//가로 세로 한번에
for(int i = 0; i < array.length; i++) {
	for(int j = 0; j < array.length - findNum + 1; j++) {
		// 가로 
		flag = true;
		for(int h = 0; h < findNum / 2; h++)
			if(array[i][j + h] != array[i][j - h + findNum - 1])
				flag = false;
		if(flag) count++;

		// 세로
		flag = true;
		for(int h = 0; h < findNum / 2; h++)
			if(array[j + h][i] != array[j - h + findNum - 1][i])
				flag = false;
		if(flag) count++;
	}
}

전체코드

import java.util.Scanner;

public class Palindrome1 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        
        for(int num = 1; num <= 10; num++) {
            int findNum = sc.nextInt();
            //sc.nextLine();
            
            int count = 0;
            boolean flag = true;
            
            char[][] array = new char[8][8];
            
            //배열에 입력
            for(int i = 0; i < array.length; i++) {
                String str = sc.next(); //nextLine() //a[i] = sc.next().toCharArray();
                for(int j = 0; j < array[i].length; j++) {
                    array[i][j] = str.charAt(j);
                }
            }
            
//            //가로 
//            for(int i = 0; i < array.length; i++) {
//                for(int j = 0; j < array.length - findNum + 1; j++) {
//                    flag = true;
//                    for(int h = 0; h < findNum / 2; h++)
//                        if(array[i][j + h] != array[i][j - h + findNum - 1])
//                            flag = false;
//                    if(flag) count++;
//                }
//            }
//            
//            //세로 
//            for(int i = 0; i < array.length - findNum + 1; i++) {
//                for(int j = 0; j < array.length; j++) {
//                    flag = true;
//                    for(int h = 0; h < findNum / 2; h++)
//                        if(array[i + h][j] != array[i - h + findNum - 1][j])
//                            flag = false;
//                    if(flag) count++;
//                }
//            }
            
            //가로 세로 한번에
            for(int i = 0; i < array.length; i++) {
                for(int j = 0; j < array.length - findNum + 1; j++) {
					// 가로 
                    flag = true;
                    for(int h = 0; h < findNum / 2; h++)
                        if(array[i][j + h] != array[i][j - h + findNum - 1])
                            flag = false;
                    if(flag) count++;
                    
					// 세로
                    flag = true;
                    for(int h = 0; h < findNum / 2; h++)
                        if(array[j + h][i] != array[j - h + findNum - 1][i])
                            flag = false;
                    if(flag) count++;
                }
            }
            
            
            System.out.println("#" + num + " " + count);
        }
    }
}