티스토리 뷰
1706번: 크로스워드
동혁이는 크로스워드 퍼즐을 좋아한다. R×C 크기의 크로스워드 퍼즐을 생각해 보자. 이 퍼즐은 R×C 크기의 표로 이루어지는데, 퍼즐을 다 풀면 금지된 칸을 제외하고는 각 칸에 알파벳이 하나씩
www.acmicpc.net
문제이해
해당 문제는 입력받은 크로스 워드를 이용해 얻을 수 있는 가장 빠른 문자열을 찾는 문제이다.
문제풀이
1- 우선 입력을 받은 문자열 중에 만들 수있는 문자열을 찾는다.
2- 가로 세로 모든 문자열을 입력 받았다면 가장 빠른 문자열을 찾는다.
이 두 단계로 문제를 해결 할 수 있다.
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();
}
}