[자바] 백준 1706 - 크로스워드 (java)

 문제 : boj1706

---

 

필요 알고리즘 개념

• 문자열, 파싱
  
  • 문자열을 파싱해서 원하는 형태로 사용할 수 있어야 한다.
• 구현
  
  • 문제에서 제시된대로 구현만 해주면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  우선 문제를 잘 파악해보자. 가로나 세로로 1개 초과로 연속된 문자열을 모두 뽑아낼 수 있다면, 그 중 가장 사전순으로 앞서는 문자를 출력해주면 된다.

위에서

"good"

"an"

"messy"

...
"sit"
"byte"

의 문자열들이 나오고, 그 중 사전순으로 가장 앞서는 "an"이 답이 된다.

 

  이 때 약간 효율을 더 챙기고 싶다면, 현재 가장 큰 String을 저장해두면서 문자열을 찾을 때 마다 비교해주면 된다. 그럼 찾아낸 문자열이 N개라 할 때, 모두 찾은 후 정렬하고 첫번째 문자열 출력해주면 O(NlogN)이 걸리는데 반해, 매번 비교해주면 O(N)으로 동작할 수 있다. 구현은 문제에서 제시된대로 해주면 되므로, 코드의 주석을 참고해보자.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        char[][] arr = new char[r][c];
        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                arr[i][j] = row.charAt(j);
            }
        }

        String min = String.valueOf((char)('z'+1));	// 존재할 수 있는 최대 문자열보다 항상 사전순으로 더 큰 문자열이다.
        for (int i = 0; i < r; i++) {	// 가로로 체크한다.
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j <= c; j++) {
                if (j==c || arr[i][j] == '#') {	// 가로로 끝에 도착하거나, #을 만날 경우 체크한다.
                    String tmp = sb.toString();
                    if (tmp.length() >= 2 && min.compareTo(tmp) > 0)
                        min = tmp;
                    sb = new StringBuilder();
                } else {
                    sb.append(arr[i][j]);
                }
            }
        }

        for (int j = 0; j < c; j++) {	// 세로로 체크한다.
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i <= r; i++) {
                if (i==r || arr[i][j] == '#') { // 세로로 끝에 도착하거나, #을 만날 경우 체크한다.
                    String tmp = sb.toString();
                    if (tmp.length() >= 2 && min.compareTo(tmp) > 0)
                        min = tmp;
                    sb = new StringBuilder();
                } else {
                    sb.append(arr[i][j]);
                }
            }
        }
        System.out.println(min);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}