[코드트리 챌린지] 3주차 - 구현

지난 주에 너무 못풀어서 낮은 점수를 받게 되어 이번 주.. 알고리즘 감각을 조금 끌어올렸습니다!!
시즌 최고 점수를 받으면서 뿌듯한 일주일을 시작할 수 있을거 같아요 :)

 

이번에는 +1 -1과 같은 고난이도의 알고리즘 문제에서 틀렸습니다를 받았지만.. 문제를 꼼꼼히 안 읽어서 출력 요구 사항을 틀리고 있었다는 사실을 종료 5분전에 알게 되었습니다.. 더 높은 점수를 받을 수 있었지만 다음 부터는 같은 실수를 하지 말자는 교훈으로 이번 주 테스트는 종료!!

 

삼성전자 발표가 얼마 안남은거 같아 코딩테스트 대비 구현 문제를 풀었습니다.

 

https://www.codetree.ai/cote/13/problems/max-area-of-positive-rectangle/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

평소 구현에는 자신이 있었기에 쉽게 풀 줄 알았지만, 요즘 알고리즘을 자주 안 풀어서 그런지 틀렸습니다를 계속 받게 되어 생각보다 오래걸렸다..

# 처음 아이디어

• 처음에 너무 어렵게 생각하여, 모든 격자를 돌며 양수를 만났을 때, 아래 로직을 수행하였다.
  • 현재 양수인 칸에서, 아래로 탐색하며 최대 세로 길이를 구해준다.
  • 오른쪽으로 탐색하며 최소의 가로 길이를 구해준다.
  • 현재 칸에서 만들 수 있는 최대 직사각형 크기는 최대 세로 크기 * 최소의 가로 크기로 만들어주며, result를 갱신해주기!!
• 만들어본 테스트 케이스는 다 맞았지만.. 더 이상 반례를 찾지 못해 ac를 받지 못하였다.

N, M = map(int, input().split())  
arr = [[*map(int, input().split())] for _ in range(N)]  

def check(si, sj):  
    max_i = N-si  
    max_j = N-sj  
    di, dj = [1, 0], [0, 1]  
    for d in range(2):  
        ni, nj = si, sj  
        while 0<=ni<N and 0<=nj<M:  
            if arr[ni][nj] <= 0:  
                if d == 0:  
                    max_i = min(max_i, ni-1)  
                else:  
                    max_j = min(max_j, nj-1)  
                break  
            ni, nj = ni+di[d], nj+dj[d]  

    return max_i, max_j  

result = -1  
for i in range(N):  
    for j in range(M):  
        if arr[i][j] > 0:  
            can_i, can_j = check(i, j)  
            vi, vj = can_i - i, can_j - j  
            if not vi:  
                vi = 1  
            if not vj:  
                vj = 1  
            result = max(result, vi*vj)  
print(result)

# AC 아이디어

• 너무 어렵게 구현한 것 같아서 로직을 조금 바꾸었다.
• 최초에 입력받은 배열을 양수인 경우, 오른쪽으로 연속된 양수의 최대 개수를 미리 COUNT 리스트에 기록해두었다.
• 이후, 현재 칸이 양수라면, 아래 칸들을 순회하며 최소의 count배열의 값을 0이하의 숫자가 나오기 전까지 구해준후, 세로의 개수 * min_가로의 개수를 해주며 result를 갱신하였다.

N, M = map(int, input().split())  
arr = [[*map(int, input().split())] for _ in range(N)]  

count = [[0] * M for _ in range(N)]  

# 오른쪽으로 연속된 양수의 개수 적어주기  
def check(si, sj):  
    temp = 0  
    for nj in range(sj, M):  
        if arr[si][nj] <= 0:  
            break  
        temp += 1  
    count[si][sj] = temp  

result = -1  
for i in range(N):  
    for j in range(M):  
        if arr[i][j] > 0:  
            check(i, j)  

for i in range(N):  
    for j in range(M):  
        if count[i][j]:  
            ti = 0  
            tj = M - j  
            for k in range(i, N):  
                if not count[k][j]:  
                    ti = k - i  
                    break  
                ti += 1  
                tj = min(tj, count[k][j])  
                result = max(result, ti*tj)  

print(result)

• 처음 아이디어를 보충하자면, 완전 탐색으로 모든 직사각형을 그려가며 내부가 모두 양수로 되어있는 직사각형의 크기로 갱신해주면 되었다..!