[SWEA] 1215. 회문1

new Dean( );·2021년 7월 29일

SWEA 알고리즘

알고리즘

목록 보기

4/30

문제

1215. [S/W 문제해결 기본] 3일차 - 회문1
'기러기', 'level' 과 같이 거꾸로 읽어도 그대로인 문장이나 낱말중에 제시된 길이를 가진 것의 총 개수를 찾아라! (가로, 세로 모두 고려)

풀이

1. input
sc.next() 는 String을 읽어오기때문에, String으로 받아서 char배열에 넣어줬다.

2. 개수세기
(1) 가로 방향과 세로 방향에 따라 getHorizontal(), getVertical() 로 나누었다. (밑에 개선방안 있음)

(2) 중심을 설정한 뒤, 양 방향으로 +1, -1씩 이동하면서 일치여부를 확인한다.

이때, 구하고자 하는 회문의 길이가 홀수일 때, 짝수일 때가 있다. 이를 한 함수에서 처리하기 위하여 파라미터를 총 3개로 했다.

가로의 경우 getHorizontal(r, c1, c2);
이때 중심좌표가 (r, c1), (r, c2) 두 개가 된다.

c1==c2 -> 홀수 (중심좌표가 1개)
c1!=c2 -> 짝수 (중심좌표가 2개)

일치여부 확인 -> 주어진문장과 길이 일치 확인 -> 길이연장 -> 일치여부 확인 -> ...

while(c2<SIZE && c1>=0) { // 영역을 벗어나면 stop
	if (arr[r][c1] != arr[r][c2]) break; // 일치하지 않으면 종료!!
	if (c2-c1+1 == target) return true; // 일치하고 제시된 길이와 일치
	c2 += 1; c1 -= 1; // 다음 좌표로 이동
}

a와 b사이의 길이 = a-b+1

자바코드

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

class Solution
{
	static final int SIZE = 8;
	static char [][] arr = new char[SIZE][SIZE];
	static int target;
	
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = 10;
		for(int test_case = 1; test_case <= T; test_case++)
		{
			// input
			target = sc.nextInt();
			String s = "";
			
			for (int i=0; i<SIZE; i++) {
				s = sc.next();
				for (int j=0; j<SIZE; j++) {
					arr[i][j] = s.charAt(j);
				}
			}

			int count = 0;
			for (int i=0; i<SIZE; i++) {
				for (int j=0; j<SIZE; j++) {
					if (getHorizontal(i, j, j)) count++;
					if (getHorizontal(i, j, j+1)) count++;
					if (getVertical(i, i, j)) count++;
					if (getVertical(i, i+1, j)) count++;
				}
			}
			
			System.out.printf("#%d %d\n", test_case, count);
		}
	}
	public static boolean getHorizontal(int r, int c1, int c2) {
		// c1==c2 ? 홀수 : 짝수개
		while(c2<SIZE && c1>=0) {
			if (arr[r][c1] != arr[r][c2]) break;
			if (c2-c1+1 == target) return true;
			c2 += 1; c1 -= 1; 
		}
		
		return false;
	}
	
	public static boolean getVertical(int r1, int r2, int c) {
		while(r2<SIZE && r1>=0) {
			if (arr[r1][c] != arr[r2][c]) break;
			if (r2-r1+1 == target) return true;
			r2 += 1; r1 -= 1; 
		}
		
		return false;
	}
}