문제
R x C 크로스워드 퍼즐에서 #으로 구분된 길이 2 이상의 단어들 중 사전순으로 가장 앞서는 단어를 구하라.
입력
첫째 줄에 R, C, 이후 R줄에 크로스워드가 주어진다.
출력
사전순으로 가장 앞서는 단어를 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 4 a#c# abb# c#dd #bcd | ab |
풀이
가로 방향과 세로 방향으로 #을 구분자로 단어를 추출하고, 사전순 최솟값을 구한다.
- 각 행을 순회하며
#으로 분리된 길이 2 이상 단어를 추출한다 - 각 열을 순회하며 같은 방식으로 단어를 추출한다
- 모든 단어 중 사전순 최솟값을 출력한다
핵심 아이디어: 가로와 세로 양방향으로 단어를 추출해야 하며, #을 만나거나 끝에 도달할 때 단어를 완성한다.
코드
package day549;
import java.io.*;
import java.util.*;
public class Day522BOJ1706크로스워드 {
public static void main(String[] args) 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);
}
}복잡도
- 시간: O(R * C)
- 공간: O(R * C)