[SWEA] 1216. 회문 2 (Java)

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14Rq5aABUCFAYi 

SW Expert Academy

 

풀이 1

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Solution {
    static char[][] arr; // 글자판
    static final int L = 100;
 
    public static boolean solve(int l) {
        for (int i = 0; i < L; i++) {
            for (int j = 0; j <= (L - l); j++) {
                if(solveRow(i, j, l) || solveColumn(j, i, l) ) return true;
            }
        }
         
        return false;
    }
  
    // 가로 탐색
    public static boolean solveRow(int i, int j, int l) {
        for (int k = 0; k < l / 2; k++) {
            if(arr[i][j + k] != arr[i][j + l - 1 - k]) return false;
        }
        return true;
    }
     
    // 세로 탐색
    public static boolean solveColumn(int i, int j, int l) {
        for (int k = 0; k < l / 2; k++) {
            if(arr[i + k][j] != arr[i + l - 1 - k][j]) return false;
        }
        return true;
    }
     
     
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        for(int test =0; test<10; test++) {
            int t = Integer.parseInt(br.readLine()); // 테스트 케이스 번호
            arr = new char[L][L];
             
            // 글자판 입력
            for(int i=0; i<L; i++) {
                String str = br.readLine();
                for(int j=0; j<L; j++) {
                    arr[i][j] = str.charAt(j);
                }
            }
             
            for(int i=L; i>0; i--) {
                if(solve(i)) {
                    System.out.println("#"+ t + " " + i);
                    break;
                }   
            }
        }
         
        br.close();
    }
}

2022.01.29 - [알고리즘, 자료구조/SWEA] - [SWEA] 1215. 회문1 (Java)

[SWEA] 1215. 회문1 (Java)

회문 1 문제에서 조금 변형하면 풀 수 있는 문제이다.

길이를 입력받는 것이 아니므로 가장 큰 길이부터 하나씩 줄여가며 탐색하고,

가장 긴 것 하나만 찾으면 되므로 찾으면 즉시 리턴하면 된다.

 

기존의 코드가 깨끗하지 못해서 변수와 함수를 깔끔하게 정리해주고,

100 * 100 배열 이므로

StringBuffer의 reverse를 사용하지 않고 회문인지 하나씩 판별하는 식으로 해결하였다.

 

1. 글자판 입력, 탐색

글자판을 입력받고

큰 길이부터 찾아서 리턴해야하므로

길이가 100일때 부터 하나씩 solve 메서드에 넣는다.

solve 메서드에선

가로,세로 탐색 메서드에 또 넘겨준다.

 

2. 가로, 세로 방향 탐색

0번 인덱스 <-> 마지막 인덱스

1번 인덱스 <-> 마지막-1 인덱스

 

계속 반복하면서

같지 않을경우 즉시 리턴하는 방식으로 탐색한다.

 

전부 다 같을경우 회문이므로

true를 리턴한다.

 

풀이 2 (reverse)

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution {
	static char[][] arr; // 글자판
	static final int L = 100;

	public static boolean solve(int l) {
		for (int i = 0; i < L; i++) {
			for (int j = 0; j <= (L - l); j++) {
				if(solveRow(i, j, l) || solveColumn(j, i, l) ) return true;
			}
		}
		
		return false;
	}
 
	// 가로 탐색
	public static boolean solveRow(int i, int j, int l) {
		String tmp = "";
		int count = 0;
		
		while(count < l) {
			tmp += arr[i][j+count];
			count++;
		}
		
		// 문자열 뒤집기
		StringBuffer bf = new StringBuffer(tmp);
		String reverse = bf.reverse().toString();

		// 회문 여부 검사
		if(tmp.equals(reverse)) {
			return true;
		}
		
		return false;
	}
	
	// 세로 탐색
	public static boolean solveColumn(int i, int j, int l) {
		String tmp = "";
		int count = 0;
		
		while(count < l) {
			tmp += arr[i+count][j];
			count++;
		}
		
		// 문자열 뒤집기
		StringBuffer bf = new StringBuffer(tmp);
		String reverse = bf.reverse().toString();

		// 회문 여부 검사
		if(tmp.equals(reverse)) {
			return true;
		}
		
		return false;
	}
	
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for(int test =0; test<10; test++) {
			int t = Integer.parseInt(br.readLine()); // 테스트 케이스 번호
			arr = new char[L][L];
			
			// 글자판 입력
			for(int i=0; i<L; i++) {
				String str = br.readLine();
				for(int j=0; j<L; j++) {
					arr[i][j] = str.charAt(j);
				}
			}
			
			for(int i=L; i>0; i--) {
				if(solve(i)) {
					System.out.println("#"+ t + " " + i);
					break;
				}	
			}
		}
		
		br.close();
	}
}

시간이 얼마나 걸리나 궁금해서

문자열을 다 만들어서 reverse 하는 방식으로 짜 보았는데

 

실행시간이 상상이상으로 걸린다.