BOJ 2804 - 크로스워드 만들기

문제

BOJ 2804 - 크로스워드 만들기

두 단어 A, B가 주어졌을 때, A를 가로로, B를 세로로 교차하는 크로스워드를 만들어라. 공통 문자가 여러 개이면 A에서 가장 먼저 나오는 것, 그 중에서도 B에서 가장 먼저 나오는 위치를 사용한다.

입력

두 단어 A, B가 공백으로 구분되어 주어진다.

출력

len(B) 줄에 len(A) 문자를 출력한다. 교차하지 않는 위치는 .으로 채운다.

예제

풀이

두 단어에서 공통 문자를 찾아 교차 위치를 결정한 뒤 격자를 출력한다.

1. A의 각 문자를 순서대로 탐색하면서 B에도 존재하는 첫 번째 공통 문자를 찾는다
2. A에서의 위치를 col, B에서의 위치를 row로 저장한다
3. B의 길이만큼 줄을 출력하되, row번째 줄에는 A 전체를, 나머지 줄에는 col 위치에 B의 해당 문자를 놓고 나머지는 .으로 채운다

핵심 아이디어: A에서의 인덱스를 우선 탐색하고, B에서 처음 등장하는 위치를 index()로 찾으면 문제 조건을 자동으로 만족한다.

코드

s1, s2 = map(str, input().split())
 
for i in range(len(s1)):
    if s1[i] in s2:
        col = i
        row = s2.index(s1[i])
        break
 
for i in range(len(s2)):
    if i == row:
        print(s1)
    else:
        print("." * col + s2[i] + "." * (len(s1) - col - 1))

복잡도

• 시간: O(|A| * |B|) — 공통 문자 탐색 및 격자 출력
• 공간: O(|A|) — 한 줄 출력용 문자열 생성