Q. 1215. 회문(D3)

Q. 1215. 회문(D3)

 

0. 문제

 

D3 난이도의 문제이고, 격자형 그래프를 활용한 구현 문제라고 생각된다.

N이 주어지고 문자가 적혀있는 격자형 그래프가 주어진다.

격자형 그래프의 가로 / 세로 N개의 문자열을 뽑았을 때

똑바로/거꾸로 읽어도 똑같은 단어의 경우의 수를 구하는 문제이다.

---

1. 풀이

 

1) 격자형 그래프를 두 개 저장하는데, 하나는 그대로 나머지는 90도 돌린 방향으로 저장한다.

(가로 / 세로 모두를 고려 해야 하므로)

2) 나올 수 있는 모든 문자열에 대해 회문 문자인지 판별한다.

(만약 N이 홀수인 경우 ex.4 모든 문자를 비교해야 하지만, 5인 경우 1 2번째와 4 5번째 문자만 비교하면 된다.)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Solution {
 
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static char[][] inputArrHorizon;
    static char[][] inputArrVertical;
    static int N;
     
    public static void input() throws IOException {
         
        N = Integer.parseInt(br.readLine());
        inputArrHorizon = new char[8][];
        inputArrVertical = new char[8][8];
        for (int i = 0; i < 8; i++) {
        	inputArrHorizon[i] = br.readLine().toCharArray(); 
        }
        for (int i = 0; i < 8; i++) {
        	for (int j = 0; j < 8; j++) {
        		inputArrVertical[i][j] = inputArrHorizon[j][i];	
			}
		}
    }
     
    public static void pro(int tc) {
         
        int res = 0, cnt = 0;;
        for (int i = 0; i < 8; i++) {
        	for (int j = 0; j < 8 - N + 1; j++) {
				if (compare(inputArrHorizon[i], j)) res++;
				if (compare(inputArrVertical[i], j)) res++;
			}
		}
        
        sb.append(String.format("#%d %d\n", tc, res));
    }
    
    public static boolean compare(char[] Arr, int startIdx) {
    	
    	for (int i = 0; i < N/2 ; i++) {
			if (Arr[startIdx + i] != Arr[startIdx + N - i - 1]) {
				return false;
			}
		}
    	return true;
    }
     
     
     
     
    public static void main(String[] args) throws Exception {
         
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("res/input.txt")));
        br = new BufferedReader(new InputStreamReader(System.in));
        int T = 10;
         
        for (int tc = 1; tc <= T; tc++) {
            input();
            pro(tc);
        }
        System.out.println(sb);
    }
 
}

---

2. 시간복잡도 계산

 

 

1) 문자열 저장 - O(8 x 8)

2) 풀이 2번 - O(2 x 8 x (8-N))

따라서 시간복잡도는 상수 시간 범위 내에서 충분히 해결할 수 있다.