[swexpert] Intermediate / String / 1213, 1215 ,1216

🅰 1213. String

​

✏️ 문제 풀이

- 주어진 문자열에서 특정 문자열이 몇번 나오는지 검색하는 문제이다.

- 특정 문자열과, 주어진 문자열의 내용을 String으로 받아와 toCharArray() 를 이용하여 char[]배열 형태로 바꿔주었다.

보이어 무어 기법을 이용하였다.

- 각 문자마자 이동시킬 자리수를 저장할 Skip배열을 생성하였고, 특정 문자열중에 같은 문자가 없을 시 문자열 크기만큼 이동

시켜 줄 값을 Skip배열 마지막에 넣어주었다.

​

✏️ 소스코드

package string;

import java.util.Scanner;

public class Sw_1213 {

	public static void main(String[] args) {

		int T = 0;
		Scanner sc = new Scanner(System.in);

		for (int test_case = 1; test_case <= 10; test_case++) {
			T = sc.nextInt();
			// 찾을 문장 정렬
			String input = sc.next();
			char[] inputArr = input.toCharArray();
			int last = inputArr.length - 1;
			int now = inputArr.length - 1;
			int cnt = 0;
			
			
			// 주어진 문장 정렬
			String sentence = sc.next();
			char[] cSent = sentence.toCharArray();
			int[] IASkip = new int[inputArr.length + 1];
			for (int i = IASkip.length - 1; i > 0; i--) { // skip배열 생성(보이어 무어 기법)
				IASkip[i - 1] = IASkip.length - i - 1;
			}
			IASkip[IASkip.length - 1] = IASkip.length - 1; // 같은 값이 없을 때 찾을 문장 길이만큼 이동

			while (now < cSent.length) {
				Loop1 : for (int i = 0; i < inputArr.length; i++) {
					int a = 0;
					if (now < cSent.length) {
						// 마지막 값 같은지 비교
						if (inputArr[last] == cSent[now]) {
							for (int j = last; j >= 0; j--) {
								// 같으면 앞으로 가면서 문자열 비교
								if (inputArr[j - 1] == cSent[now - 1]) {
									// 전부 같으면 cnt++
									now -= 1;
									if (j - 1 == 0) {
										cnt++;
										a++;
										now += IASkip.length + a;
										break;
									}
								} else {
									now += IASkip.length-1;
									break Loop1;
								}
							}

						} else if (inputArr[i] == cSent[now]) {
							now += IASkip[i];
							break;
						} else if (i == inputArr.length - 1) {
							now += IASkip[IASkip.length - 1];
							break;
						}
					}
				}
			}

			System.out.printf("#%d %d\n", test_case, cnt);
		}
	}
}

}

✅ 후기

​

보이어 무어 기법을 이용하려고 했으나 생각한대로 구현하기가 힘들었다. 그러다보니 코드가 길어지고, 처음 생각한 코드와는 달리 디버깅을 하면서 테스트케이스에 맞게 답을 맞춰나갔다.

다음부터는 완벽하게 브레인스토밍을 한 후 코드를 구현하도록 해야겠다.

---

🅰 1215. 회문 1

​

✏️ 문제 풀이

- 회문의 길이가 주어지기 때문에 left와 right를 이용하여 중심으로 오면서 값이 같은지 비교하였다.

- 이중 for문을 이용하여 i는 행을 나타내고, j는 열(가로)를 나타내서 j을 시작점으로 잡고 left = j , right = j+N-1 로 선언했다.

- 1. Arr(i)(left)와 Arr(i)(right) 값이 같으면 left+=1, right-=1을 해줘서 중심으로 오면서 값을 비교했다.

- 만약 N이 짝수이면 left==right일때 회문이 성립될 것이고, N이 홀수이면 right-left = -1일때 회문이 성립될 것이다.

- 1.if (right - left == -1 || left == right) { ​ cnt++; ​ break; ​ } 회문조건이 성립되면 cnt++를 해주도록 설계했다.

-행 먼저 탐색하고 그 후 열도 탐색해서 총 회문의 개수를 측정하였다.

 

✏️ 소스코드

 } }

package string;

import java.util.*;

public class Sw_1215 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		for (int test_case = 1; test_case <= 10; test_case++) {
			int N = sc.nextInt();
			char Arr[][] = new char[8][8];
			String str[] = new String[8];
			int cnt = 0;

			// String to char 2차원 배열로 선언
			for (int i = 0; i < Arr.length; i++) {
				str[i] = sc.next();
				for (int j = 0; j < Arr.length; j++) {
					Arr[i][j] = str[i].charAt(j);
				}
			}

			// 행 먼저 탐색
			for (int i = 0; i < 8; i++) {
				for (int j = 0; j <= 8 - N; j++) {
					int left = j;
					int right = j + N - 1;

					while (true) {
						if (Arr[i][left] == Arr[i][right]) {
							left += 1;
							right -= 1;
							if (right - left == -1 || left == right) {
								cnt++;
								break;
							}
							continue;
						} else
							break;
					}
				}
			}

			// 열 탐색
			for (int j = 0; j < 8; j++) {
				for (int i = 0; i <= 8 - N; i++) {
					int left = i;
					int right = i + N - 1;

					while (true) {
						if (Arr[left][j] == Arr[right][j]) {
							left += 1;
							right -= 1;
							if (right - left == -1 || left == right) {
								cnt++;
								break;
							}
							continue;
						} else
							break;
					}
				}
			}
			
			System.out.printf("#%d %d\n",test_case,cnt);
		}
	}
}

✅ 후기

​

처음에는 회문크기만큼의 배열을 따로 만들어서 일일이 저장해서 비교하려 하였으나 비 효율적일것 같아서

주어진 Arr 2차원 배열 안에서 해결할 수 있는 방법을 생각해 보았고, 문제를 풀었다.

회문의 길이가 주어져 있어서 쉽게 해결했던 것 같다.

---

🅰 1216. 회문2

​

✏️ 문제 풀이

- 회문 1은 밖에서 중심으로 오면서 회문인지를 확인해 봤다면, 회문 2는 회문의 길이가 지정되어 있지 않기 때문에 중심(자신

을 기준)부터 밖으로 가면서 회문인지를 확인해보았다.

- 마찬가지로 Arr 2차원 배열 안에서 left = N-1, N, right = N+1 3가지를 가지고 계산을 하였다.

cnt = 회문 길이 측정, max = 현재 최장회문 길이

- 방법은 크게 2가지로 생각해보았다

- 회문의 길이가 홀수일 때

- N이 중심이므로 Arr(i)(left) == Arr(i)(right) 이면 회문 기준이 성립된다.

- if(left>0 && right<99) 조건을 걸어주어 배열의 크기를 벗어나지 않도록 하였고,

- 계속 left와 right의 배열 값을 비교하여 같으면 cnt+=2를 하여 회문의 길이를 측정하였다.

- cnt 값이 max 값보다 크면 max = cnt를 해줘서 결과값을 넣어주었다.

- else이면 cnt =1을 하여 회문을 초기화 시켜주었고 break;를 하여 while문을 종료하였다.

- 회문의 길이가 짝수일 때

- N은 0열부터 시작하므로 N이 right 값과 같으면 1차적으로 짝수 회문 조건이 성립된다.

- if(left>0 && right<99) 조건을 걸어주어 배열의 크기를 벗어나지 않도록 하였고,

- 기준이 N과 right 이므로 left 와 right+1이 같으면 회문의 조건이 성립되어 cnt+=2를 하여 회문의 길이를 측정하였다.

- cnt 값이 max 값보다 크면 max = cnt를 해줘서 결과값을 넣어주었다.

- else이면 cnt =1을 하여 회문을 초기화 시켜주었고 break;를 하여 while문을 종료하였다.

- 세로일때도 마찬가지로 하여 값을 구해주었다.

​

✏️ 소스코드

 

package string;

import java.util.*;

public class Sw_1216 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = 0;

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

			int max = 0;

			// String으로 문자열 받아오기
			String str[] = new String[100];
			// 2차원 배열 char 형태로 선언
			char Arr[][] = new char[100][100];
			for (int i = 0; i < 100; i++) {
				str[i] = sc.next();
				for (int j = 0; j < 100; j++) {
					Arr[i][j] = str[i].charAt(j);
				}
			}
			//가로 
			for (int i = 0; i < Arr.length; i++) {
				for (int j = 1; j < Arr.length - 1; j++) {
					int left = j - 1;
					int now = j;
					int right = j + 1;
					int cnt =1;
					if (Arr[i][left] == Arr[i][right]) {
						while (left > 0 && right < 99) {
							if (Arr[i][left] == Arr[i][right]) {
								left -= 1;
								right += 1;
								cnt += 2;
								if (cnt > max) {
									max = cnt;
								}
							} else {
								cnt = 1; // 회문 초기화
								break;
							}
						}
					}
					else if(Arr[i][j] == Arr[i][right]) {
						cnt++;
						while (left > 0 && right < 99) {
							if(Arr[i][left] == Arr[i][right+1]) {
								left-=1;
								right+=1;
								cnt+=2;
								if(cnt>max) {
									max = cnt;
								}
							}else {
								cnt = 1;
								break;
							}
						}
					}
				}
			}	
			//세로 
			for (int i = 0; i < Arr.length; i++) {
				for (int j = 1; j < Arr.length - 1; j++) {
					int left = j - 1;
					int now = j;
					int right = j + 1;
					int cnt =1;
					if (Arr[left][i] == Arr[right][i]) {
						while (left > 0 && right < 99) {
							if (Arr[left][i] == Arr[right][i]) {
								left -= 1;
								right += 1;
								cnt += 2;
								if (cnt > max) {
									max = cnt;
								}
							} else {
								cnt = 1; // 회문 초기화
								break;
							}
						}
					}
					else if(Arr[j][i] == Arr[right][i]) {
						cnt++;
						while (left > 0 && right < 99) {
							if(Arr[left][i] == Arr[right+1][i]) {
								left-=1;
								right+=1;
								cnt+=2;
								if(cnt>max) {
									max = cnt;
								}
							}else {
								cnt = 1;
								break;
							}
						}
					}
				}
			}
			System.out.printf("#%d %d\n", test_case, max);
			max = 0;
		}
	}
}

 

✅ 후기

​

길이가 없는 회문이라 어떻게 접근할지가 걱정이였으나, 생각한대로 결과를 구현해서 만족스러웠다.

하지만 구글에 다른 사람이 푼 문제를 봤는데 완전탐색을 이용하여 가로, 세로를 나누지 않고 하나의 for문으로 짜서 코드의 길이가 나의 1/4은 되는 것 같았다.

더 공부해서 다른 기법을 적용해 볼 수 있도록 해야겠다 생각했다.

​