2/11 Coding Test

✅ Coding Test

🎈 1915 가장 큰 정사각형

NXM 크기의 각 칸이 0/1로 채워진 배열이 있다. 이 중 모든 칸이 1로 채워진 가장 큰 정사각형의 넓이를 구하는 문제.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(n)]
dp = [[0]*m for _ in range(n)]
answer = 0
for i in range(n):
    for j in range(m):
        # 행, 열이 첫 번째이면 dp는 그래프 값
        if i == 0 or j == 0:
            dp[i][j] = graph[i][j]
        # 그래프가 0일 때 dp는 0
        elif graph[i][j] == 0:
            dp[i][j] = 0
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
        answer = max(answer, dp[i][j])

print(answer**2)

< 해설 >

입력값들을 각각 채워주고 dp로 해결했다.
로직은 다음과 같다.

• 2중 for loop를 통해 인덱스를 지정해주고 주어진 nxm 크기의 정사각형의 열과 행이 첫 번째 인덱스면 dp는 해당 그래프 값을 채워준다.
• graph의 값이 0이면 dp도 0
• 이외의 케이스는 이전 3가지 케이스 중 최솟값에 1을 더해준다.

🎈 9935 문자열 폭발

문자열에 폭발 문자열을 심어놨고 폭발 문자열이 복팔하면 그 문자는 문자열에서 사라지고 이외의 문자열은 합쳐진다.
폭발은 다음과정으로 진행

• 문자열이 폭발 문자열을 포함하고 있는 경우, 모든 폭발 문자열이 폭발하고 남은 문자열들은 순서대로 이어 붙여 새로운 문자열이 된다.
• 새로 생긴 문자열에도 폭발 문자열이 포함될 수 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 반복한다.

최종적으로 모든 폭발이 끝나고 남은 문자열을 출력하는 문제.

첫 줄에는 문자열이 주어지고 둘째 줄에는 폭발 문자열이 주어진다.

import sys
input = sys.stdin.readline

word = list(input().rstrip())
destroy = input().rstrip()

stack = []
for i in word:
    stack.append(i)
    # 스택에 마지막이 폭발 문자열 끝 번호, 스택 끝에 있으면 빼기
    if stack[-1] == destroy[-1] and ''.join(stack[-len(destroy):]) == destroy:
        del stack[-len(destroy):]

if stack:
    print(''.join(stack))
else:
    print('FRULA')

< 해설 >

문자열을 word, 폭발 문자열을 destroy로 지정하고 스택을 이용해 폭발 문자열이 스택에 포함되면 제거해주는 방식으로 진행했다.
특히, 제거 후에도 문자열 내 폭발 문자열이 있으면 제거해 주어야 하므로 스택의 남아 있는 끝 값이 폭발 문자열과 동일한지 여부도 체킹해준다.