[Java] SWEA 1216 회문2

Lee GaEun·2024년 11월 12일

JAVA 알고리즘 SWEA

[Java] 알고리즘

목록 보기

14/93

1216 회문2 문제 링크

문제분석

100x100 글자판의 가로, 세로에서 가장 긴 회문의 길이를 구하는 문제

제약 사항

각 칸의 들어가는 글자는 'A', 'B', 'C' 중 하나 (char type)
글자 판은 항상 정사각형임
ABA, ABBA, A 모두 회문임
가로, 세로 각각에 대한 직선으로만 판단

입력 조건

첫째 줄 : 테스트 케이스 번호
둘째 줄 : 테스트 케이스 ( 총 10개 )

출력 조건

#부호 + 테스트 케이스 번호 + " " + 가장 긴 회문의 길이 출력

#1

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        /*int T;
        T=sc.nextInt();*/

        for(int test_case = 1; test_case <= 10; test_case++)
        {
            int N = sc.nextInt();
            char[][] arry = new char[100][100];

            for(int i=0; i<100; i++) {
                String a = sc.next();
                for(int j=0; j<100; j++) {
                    arry[i][j] = a.charAt(j);
                }
            }

            int answer = 1;

            for(int j=0; j<100; j++){
                for(int i=0; i<100; i++){
                    count(arry, i, j);
                }
            }
            System.out.println("#"+test_case+" "+answer);
        }
    }

    static int count(char[][] arry, int i, int j) {
        int answer = 1;
        for(int a=0; a<49; a++) {
            if (arry[j][i+a] == arry[j][99-a]) {
                answer++;
            }

        }
    }
}

40분 테스트로 풀어보다가 말음
뭔가 방법이 틀린 것 같음.. 이게 될 리가 없음..

#2

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        /*int T;
        T=sc.nextInt();*/

        for(int test_case = 1; test_case <= 10; test_case++)
        {
            int N = sc.nextInt();
            char[][] arry = new char[100][100];

            for(int i=0; i<100; i++) {
                String a = sc.next();
                for(int j=0; j<100; j++) {
                    arry[i][j] = a.charAt(j);
                }
            }

            int answer = 1;

            for(int j=0; j<100; j++){
                for(int i=0; i<100; i++){
                    answer = Math.max(count(arry, i, j), answer);
                }
            }
            System.out.println("#"+test_case+" "+answer);
        }
    }

    static int count(char[][] arry, int i, int j) {
        int len = 1;
        boolean ll1 = true;
        boolean ll2 = true;

        for(int b=99; b>i; b--) {
            for(int a=0; a<((b-i)/2); a++) {
                if (arry[j][i+a] != arry[j][b-a]) {
                    ll1 = false;
                    break;
                }
            }
            for(int a=0; a<((b-i)/2); a++) {
                if (arry[i+a][j] != arry[b-a][j]) {
                    ll2 = false;
                    break;
                }
            }
            len = ll1 || ll2 ? Math.max(len, b+1) : len;
        }

        return len;
    }
}

아니 회문 길이 구하는 방식이 이상하다는 건 알겠는데 어떻게 수정해야 될 지를 모르겠음..

#3

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
    static char[][] arr = new char[100][100];

    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        /*int T;
        T=sc.nextInt();*/

        for(int test_case = 1; test_case <= 10; test_case++)
        {
            int N = sc.nextInt();

            for(int i=0; i<100; i++) {
                String a = sc.next();
                for(int j=0; j<100; j++) {
                    arr[i][j] = a.charAt(j);
                }
            }

            // 회문의 길이별로 탐색
            // 회문 길이 가장 긴 값을 구해야 함으로 100부터 0까지 탐색함
            for(int i=100; i>0; i--) {
                // 해당 회문 길이로 탐색했을 때 가로 or 세로가 회문임으로
                if(slove(i)) {
                    // 가장 긴 회문의 길이는 i
                    System.out.println("#"+test_case+" "+i);
                    // 가장 긴 값을 구하면 더 탐색할 필요없음
                    break;
                }
            }
        }
    }

    static boolean slove(int i) {
        // 모든 회문의 시작점을 찍어줘야됨 
        for(int a=0; a<100; a++) {
            // b는 100-i까지만 -> 회문의 시작점이니까
            for(int b=0; b<=(100-i); b++) {
                // 가로 or 세로 중 하나가 회문이면 true 반환
                if(sloveRow(a,b,i) || sloveCol(a,b,i)) return true;
            }
        }
        return false;
    }

    // 가로에서 탐색
    static boolean sloveRow(int a, int b, int i) {
        // i는 탐색하려는 회문 길이
        // 회문 길이의 1/2만큼 반복 -> 회문인지를 첫점과 끝점 비교로 하니까
        for(int z=0; z<i/2; z++) {
            // 해당 문자열이 회문인지 판별
            // 회문의 시작점 b, 회문의 가장 끝점 b+i-1, 회문 안의 모든 문자를 비교할 수 있게하는 변수 z
            // 회문이 아니면 false를 반환
            if(arr[a][b+z] != arr[a][b+i-1-z]) return false;
        }
        // 회문이면 true 반환
        return true;
    }

    // 세로에서 탐색
    static boolean sloveCol(int a, int b, int i) {
        for(int z=0; z<i/2; z++) {
            if(arr[b+z][a] != arr[b+i-1-z][a]) return false;
        }
        return true;
    }
}

다른 사람 블로그 참고함
시간 잰다고 너무 급하게 생각하는 것 같음
- 차분하게 방법을 생각하고 코딩을 하는 게 나음
- 결론 내가 구하고자 하는 값이 뭔지를 먼저 생각할 수 있도록
함수를 왜 하나만 쓰려고 하는지 모르겠음
- 복잡한 수식은 함수 여러 개로 나눠야됨

근데 틀림
댓글 보니까 해당 문제 테스트 번호가 순차적이지 않고 무작위로 출력되는 듯
System.out.println("#"+test_case+" "+i); 이 출력 문구를
System.out.println("#"+N+" "+i);으로 수정

뿌듯하지 않은 성공..

5/2 다시 풀어봄

#4

43분


import java.util.HashMap;
import java.util.Scanner;
import java.io.FileInputStream;
import java.util.Set;

class Solution
{
    static char[][] arr;
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=10;

        for(int test_case = 1; test_case <= T; test_case++)
        {
            int N = sc.nextInt();
            String a;
            arr = new char[100][100];
            for(int i=0; i<100; i++) {
                a = sc.next();
                for(int j=0; j<100; j++) {
                    arr[i][j] = a.charAt(j);
                }
            }

            int answer = 0;
            for(int i=100; i>=0; i--) { // 회문의 길이 별 탐색
                answer = findS(i);
                if(answer != 0) break;
            }

            System.out.println("#"+N+" "+answer);
        }
    }

    static int findS(int T) {
        int a = 0;
        int b = 0;
        for(int i=0; i<100; i++) {
            for(int j=0; j<=100-T; j++) {  // 배열 전부 돌기
                for(int k=0; k<T/2; k++) { // 회문인지
                    if(arr[i][j+k] == arr[i][j+T-1-k]) a++;  // 가로
                    if(arr[j+k][i] == arr[j+T-1-k][i]) b++;  // 세로
                }

                if(a == T/2) return T;
                if(b == T/2) return T;
                a = 0;
                b = 0;
            }
        }
        return 0;
    }
}