[백준] 1706번 크로스워드 자바 풀이

문제

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초

128 MB

1463

691

581

48.136%

문제

동혁이는 크로스워드 퍼즐을 좋아한다. R×C 크기의 크로스워드 퍼즐을 생각해 보자. 이 퍼즐은 R×C 크기의 표로 이루어지는데, 퍼즐을 다 풀면 금지된 칸을 제외하고는 각 칸에 알파벳이 하나씩 적혀 있게 된다. 아래는 R = 5, C = 5 인 경우 다 푼 퍼즐의 한 예이다. 검은 칸은 금지된 칸이다.

세로 또는 가로로 연속되어 있고, 더 이상 확장될 수 없는 낱말이 퍼즐 내에 존재하는 단어가 된다. 위의 퍼즐과 같은 경우, 가로 낱말은 good, an, messy, it, late의 5개가 있고, 세로 낱말은 game, one, sit, byte의 4개가 있다. 이 중 사전식 순으로 가장 앞서 있는 낱말은 an이다.

다 푼 퍼즐이 주어졌을 때, 퍼즐 내에 존재하는 모든 낱말 중 사전식 순으로 가장 앞서 있는 낱말을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 퍼즐의 R과 C가 빈 칸을 사이에 두고 주어진다. (2 ≤ R, C ≤ 20) 이어서 R개의 줄에 걸쳐 다 푼 퍼즐이 주어진다. 각 줄은 C개의 알파벳 소문자 또는 금지된 칸을 나타내는 #로 이루어진다. 낱말이 하나 이상 있는 입력만 주어진다.

출력

첫째 줄에 사전식 순으로 가장 앞서 있는 낱말을 출력한다.

풀이

시간복잡도

퍼즐의 크기가 20X20 이하이고, 시간제한이 2초 이므로 시간에 대해서 크게 생각하지 않고 바로구현

1. #을 만나기전까지는 해당 위치의 문자를 버퍼에 쌓는다.
2. #을 만난경우 리스트에 문자열을 추가하고 버퍼를 비운다.
3. #을 만났지만 버퍼 문자열이 비어 있다면 그냥 스킵한다.
4. 행, 열 모두 1~3의 작업을 수행한다.
5. 리스트를 정렬하고 가장 첫번째 값이 사전순으로 가장 앞서 있는 낱말이다.

리스트에 추가하는 작업만 수행하므로 LinkedList를 선택했고 ArrayList와 비교해본 결과

LinkedList로 구현한 코드가 조금 더 빨랐다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] size = br.readLine().split(" ");
        int R = Integer.parseInt(size[0]);
        int C = Integer.parseInt(size[1]);
        char[][] array = new char[R][C];
        for (int i = 0; i < R; i++) {
            array[i] = br.readLine().toCharArray();
        }
        LinkedList<String> list = new LinkedList<>();
        StringBuilder buf = new StringBuilder();
        for (int i = 0; i < R; i++) {
            buf.setLength(0);
            for (int j = 0; j < C; j++) {
                if (array[i][j] == '#') {
                    if (buf.length() != 0) {
                        if (buf.length() > 1) list.add(buf.toString());
                        buf.setLength(0);
                    }
                } else {
                    buf.append(array[i][j]);
                }
            }
            if (buf.length() > 1) list.add(buf.toString());
        }
        for (int i = 0; i < C; i++) {
            buf.setLength(0);
            for (int j = 0; j < R; j++) {
                if (array[j][i] == '#') {
                    if (buf.length() != 0) {
                        if (buf.length() > 1) list.add(buf.toString());
                        buf.setLength(0);
                    }
                } else {
                    buf.append(array[j][i]);
                }
            }
            if (buf.length() > 1)
                list.add(buf.toString());
        }

        Collections.sort(list);
        System.out.println(list.get(0));
    }
}