Cooper's devlog

1216. [S/W 문제해결 기본] 3일차 - 회문 본문

Algorithm/SWEA

1216. [S/W 문제해결 기본] 3일차 - 회문

cooper_dev 2020. 4. 17. 20:05

[1]개념

 

- String 탐색하기

 

[2] 접근 방법

 

  1. 배열을 입력받는다.
  2. 행 탐색으로 palindrome의 수를 counting한다.
  3. 열 탐색으로 palindrome의 수를 counting한다.
  4. (2)와 (3)과정의 값을 합한다.

 

<<code>>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
package intermediate;
 
import java.util.*;
 
public class String1_palindrome {
    
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String1_palindrome sol = new String1_palindrome();
        
        for (int test_case = 1; test_case <= 10; test_case++) {
            char[][] test_charArr = new char[8][8];
            int palindrome_len = Integer.parseInt(sc.nextLine());
            
            for(int column = 0; column < test_charArr.length; column++) {
                char[] inputLine_charArr = sc.nextLine().toCharArray();
                for(int row = 0; row< inputLine_charArr.length; row++) {
                    test_charArr[column][row] = inputLine_charArr[row];
                }
            }
 
            int row_count = sol.countRowSearch(test_charArr,palindrome_len);            
            int col_count = sol.countColSearch(test_charArr, palindrome_len);            
 
            int match_count = row_count + col_count;
            
            System.out.println("#" + test_case + " " + match_count);
            
        }
    }
 
    public int countRowSearch(char[][] test_charArr, int palindrome_len) {
        int match_count = 0;
        
        for (int col = 0; col < test_charArr.length; col++) {
            for (int row = 0; row < test_charArr[0].length - palindrome_len + 1; row++) {
                boolean palin_flag = true;
                for(int index = row; index < index + palindrome_len/2 - (index-row); index++) {
                    if(test_charArr[col][index] != test_charArr[col][(row + palindrome_len - (index - row) -1)]) {
                        palin_flag = false;
                        break;
                    }
                }
                if(palin_flag == true)    match_count++;
            }    
        }
        
        return match_count;
    }
    
    public int countColSearch(char[][] test_charArr, int palindrome_len) {
        int match_count = 0;
        
        for (int row = 0; row < test_charArr.length; row++) {
            for (int col = 0; col < test_charArr[0].length - palindrome_len + 1; col++) {
                boolean palin_flag = true;
                for(int index = col; index < index + palindrome_len/2 - (index-col); index++) {
                    if(test_charArr[index][row] != test_charArr[(col + palindrome_len - (index - col) -1)][row]) {
                        palin_flag = false;
                        break;
                    }
                }
                if(palin_flag == true)    match_count++;
            }    
        }
        
        return match_count;
    }
    
}
 
 
  

[4] 막혔던 부분

 

  1. 양 끝의 단어를 비교할 때, index를 이동할 때의 배열의 위치를 수식화하는데 시간이 오래걸림.(산수를 몬하나;;)
  2. 아직까지도 변수명명을 하는 법이 어렵다. -> 좀 더 간결성있고 직관성 있는 코드를 작성해야 할 것.

[5] 개선 필요점

 

1. 삼중 for문을 이용한 방법이라 O(n^3)의 시간 복잡도를 가지기 때문에 좀더 효율적인 알고리즘 찾아봐야할 것 같다.

(ps. 다른 문제 풀이를 검색해봐도 모두 삼중루프를 이용해서 푼 문제 밖에 없다;;)

'Algorithm > SWEA' 카테고리의 다른 글

1219. [S/W 문제해결 기본] 4일차 - 길찾기  (0) 2020.04.20
1208. [S/W 문제해결 기본] 1일차 - Flatten  (0) 2020.04.16
'Algorithm/SWEA' Related Articles more
Comments