문제
R x C 크로스워드 퍼즐에서 가로/세로 방향으로 2글자 이상인 단어들을 추출하여 사전순으로 가장 앞선 단어를 출력하라.
입력
격자 크기 R, C와 R줄의 격자가 주어진다. #은 검은 칸이다.
출력
사전순으로 가장 앞선 단어를 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 4 luka o##i kula i##a | kala |
풀이
가로와 세로 방향으로 단어를 추출한 뒤 정렬하여 최솟값을 구한다.
- 각 행을 순회하며
#으로 구분된 연속 문자열 중 길이 2 이상인 것을 수집한다 - 각 열을 순회하며 동일한 방식으로 단어를 수집한다
- 수집된 모든 단어를 정렬하여 첫 번째를 출력한다
핵심 아이디어: #을 구분자로 사용해 행/열에서 단어를 파싱하고, 사전순 정렬로 최솟값을 찾는 구현 문제이다.
코드
r, c = map(int, input().split())
data = [list(input()) for _ in range(r)]
words = []
for i in range(r):
tmp = ""
for j in range(c):
if data[i][j] == "#":
if len(tmp) > 1:
words.append(tmp)
tmp = ""
continue
tmp += data[i][j]
if len(tmp) > 1:
words.append(tmp)
for j in range(c):
tmp = ""
for i in range(r):
if data[i][j] == "#":
if len(tmp) > 1:
words.append(tmp)
tmp = ""
continue
tmp += data[i][j]
if len(tmp) > 1:
words.append(tmp)
print(sorted(words)[0])복잡도
- 시간: O(RC + W log W)
- 공간: O(RC)