[PCCE 기출문제] 10번 / 공원

 

https://school.programmers.co.kr/learn/courses/30/lessons/340198

프로그래머스

최적화가 필요하지만, 일단 막코딩..

def solution(mats, park):
    max_y, max_x = len(park), len(park[0])
    successes = set()
    for y in range(max_y):
        for x in range(max_x):
            if park[y][x] != '-1':
                continue
            for mat in mats:
                success = True
                for cur_y in range(y, y + mat):
                    for cur_x in range(x, x + mat):
                        if cur_y >= max_y or cur_x >= max_x or park[cur_y][cur_x] != '-1':
                            success = False
                            break
                    if not success:
                        break
                if success:
                    successes.add(mat)
    return max(successes, default=-1)

테스트 1 〉	통과 (4.01ms, 10.2MB)
테스트 2 〉	통과 (0.17ms, 10.1MB)
테스트 3 〉	통과 (11.71ms, 10.2MB)
테스트 4 〉	통과 (3.21ms, 10.1MB)
테스트 5 〉	통과 (37.48ms, 10.2MB)
테스트 6 〉	통과 (32.52ms, 10.2MB)
테스트 7 〉	통과 (0.12ms, 10.2MB)
테스트 8 〉	통과 (2.70ms, 10.2MB)
테스트 9 〉	통과 (0.03ms, 10.2MB)
테스트 10 〉	통과 (3.70ms, 10.2MB)
테스트 11 〉	통과 (10.52ms, 10.1MB)
테스트 12 〉	통과 (5.42ms, 10.2MB)
테스트 13 〉	통과 (3.87ms, 10.2MB)
테스트 14 〉	통과 (0.98ms, 10.3MB)
테스트 15 〉	통과 (0.03ms, 10.2MB)
테스트 16 〉	통과 (27.31ms, 10.2MB)
테스트 17 〉	통과 (4.97ms, 10MB)
테스트 18 〉	통과 (2.43ms, 10.2MB)
테스트 19 〉	통과 (26.75ms, 10.2MB)
테스트 20 〉	통과 (13.88ms, 10.2MB)

 

작은 매트가 통과하지 못하면, 큰 매트도 통과하지 못하니까..
mats를 정렬한 뒤에 succcess == False 가 뜨면 break 시키자. 
속도의 차이가 꽤 크다. 

def solution(mats, park):
    max_y, max_x = len(park), len(park[0])
    successes = set()
    for y in range(max_y):
        for x in range(max_x):
            if park[y][x] != '-1':
                continue
            for mat in sorted(mats):
                success = True
                for cur_y in range(y, y + mat):
                    for cur_x in range(x, x + mat):
                        if cur_y >= max_y or cur_x >= max_x or park[cur_y][cur_x] != '-1':
                            success = False
                            break
                    if not success:
                        break
                if success:
                    successes.add(mat)
                else:
                    break
    return max(successes, default=-1)

테스트 1 〉	통과 (1.78ms, 10.2MB)
테스트 2 〉	통과 (0.08ms, 10.2MB)
테스트 3 〉	통과 (5.61ms, 10.4MB)
테스트 4 〉	통과 (1.25ms, 10.1MB)
테스트 5 〉	통과 (15.74ms, 10.2MB)
테스트 6 〉	통과 (28.83ms, 10.2MB)
테스트 7 〉	통과 (0.06ms, 10.2MB)
테스트 8 〉	통과 (1.65ms, 10.3MB)
테스트 9 〉	통과 (0.02ms, 10MB)
테스트 10 〉	통과 (1.55ms, 10.1MB)
테스트 11 〉	통과 (2.61ms, 10.1MB)
테스트 12 〉	통과 (2.19ms, 10.1MB)
테스트 13 〉	통과 (1.58ms, 10.1MB)
테스트 14 〉	통과 (0.32ms, 10.3MB)
테스트 15 〉	통과 (0.02ms, 10.3MB)
테스트 16 〉	통과 (17.77ms, 10.1MB)
테스트 17 〉	통과 (1.64ms, 10.2MB)
테스트 18 〉	통과 (0.50ms, 9.97MB)
테스트 19 〉	통과 (9.50ms, 10.3MB)
테스트 20 〉	통과 (4.83ms, 10.4MB)

 

위 코드는 매트를 검색할 때 중복되는 영역이 발생한다. 
중복 영역 없이 reach를 증가시키면서 한줄 한줄 직접 탐색하도록 바꿔주면 더 빨라질 것 같은데...
속도 차이가 별로 안난다. 오히려 느리기도 --;
신묘한 파이썬...

for ~ else는 좋지 않은 패턴이라고 쓰지 말자는 이야기도 있다. 
for 문에서 break가 걸리지 않을 때 else문 이하가 실행된다.

def solution(mats, park):
    successes = set()
    max_y, max_x = len(park), len(park[0])
    max_mat = max(mats)
    for y in range(max_y):
        for x in range(max_x):
            for reach in range(1, max_mat + 1):
                success = False
                for cur_y in range(y, y + reach):
                    if cur_y >= max_y or x + reach > max_x or park[cur_y][x + reach - 1] != '-1':
                        break
                else:
                    for cur_x in range(x, x + reach):
                        if cur_x >= max_x or y + reach > max_y or park[y + reach - 1][cur_x] != '-1':
                            break
                    else:
                        successes.add(reach)
                        success = True
                if not success:
                    break
    max_success = max(successes, default=-1)
    for each in sorted(mats, reverse=True):
        if each <= max_success:
            return each
    return -1

테스트 1 〉	통과 (1.20ms, 10.2MB)
테스트 2 〉	통과 (0.08ms, 10.2MB)
테스트 3 〉	통과 (5.93ms, 10.3MB)
테스트 4 〉	통과 (1.09ms, 10.3MB)
테스트 5 〉	통과 (14.29ms, 10.3MB)
테스트 6 〉	통과 (34.34ms, 10.2MB)
테스트 7 〉	통과 (0.10ms, 10.2MB)
테스트 8 〉	통과 (1.93ms, 10.3MB)
테스트 9 〉	통과 (0.04ms, 10.1MB)
테스트 10 〉	통과 (1.60ms, 10.1MB)
테스트 11 〉	통과 (3.05ms, 10.1MB)
테스트 12 〉	통과 (2.17ms, 10.2MB)
테스트 13 〉	통과 (1.40ms, 10.2MB)
테스트 14 〉	통과 (1.65ms, 10.2MB)
테스트 15 〉	통과 (0.02ms, 10.1MB)
테스트 16 〉	통과 (17.42ms, 10.3MB)
테스트 17 〉	통과 (2.34ms, 10.1MB)
테스트 18 〉	통과 (0.79ms, 10.1MB)
테스트 19 〉	통과 (8.07ms, 10.2MB)
테스트 20 〉	통과 (10.99ms, 10.3MB)

 

mats를 기준으로 큰 값부터 처리하도록 코딩하면 짧게 코딩할 수 있따. 

def solution(mats, park):
    max_y, max_x = len(park), len(park[0])
    for mat in sorted(mats, reverse=True):
        for y in range(max_y - mat + 1):
            for x in range(max_x - mat + 1):
                success = True
                for cur_y in range(y, y + mat):
                    for cur_x in range(x, x + mat):
                        if park[cur_y][cur_x] != '-1':
                            success = False
                            break
                    if not success:
                        break
                if success:
                    return mat
    return -1

테스트 1 〉	통과 (0.03ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.1MB)
테스트 3 〉	통과 (2.57ms, 10.3MB)
테스트 4 〉	통과 (0.07ms, 10.3MB)
테스트 5 〉	통과 (11.46ms, 10.2MB)
테스트 6 〉	통과 (0.03ms, 10.3MB)
테스트 7 〉	통과 (0.01ms, 10.2MB)
테스트 8 〉	통과 (0.39ms, 10.1MB)
테스트 9 〉	통과 (0.01ms, 10.3MB)
테스트 10 〉	통과 (0.84ms, 10.2MB)
테스트 11 〉	통과 (2.81ms, 10.3MB)
테스트 12 〉	통과 (0.63ms, 10.2MB)
테스트 13 〉	통과 (0.42ms, 10.3MB)
테스트 14 〉	통과 (0.09ms, 10.2MB)
테스트 15 〉	통과 (0.02ms, 10.2MB)
테스트 16 〉	통과 (5.40ms, 10.3MB)
테스트 17 〉	통과 (0.52ms, 10.2MB)
테스트 18 〉	통과 (0.01ms, 10.2MB)
테스트 19 〉	통과 (7.26ms, 10.2MB)
테스트 20 〉	통과 (4.82ms, 10.2MB)