파이썬(Python) 알고리즘 문제풀이 카펫 [프로그래머스 / 완전탐색]

출처) 프로그래머스 Facebook

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

 

제한사항

갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

 

 

입출력 예시

brown	yellow	return
10	2	[4,3]
8	1	[3,3]
24	24	[8,6]

 

 

풀이 코드

처음에 생각한 방법으로는, 총 타일 개수에서 사각형을 만들 수 있는 가능한 모든 경우의 수를 찾아내고, 경우의 수 하나 당 2차원 리스트를 만든 뒤 2차원 리스트의 Brown 타일, Yellow 타일 개수를 판단해 문제를 풀 수 있다고 생각하고 풀이했다. 경우의 수를 permutations 라이브러리로 구할 수는 없을까 고민하다 안될 것 같아서 직접 중복을 제거하는 식으로 .. 쌩 구현에 가까운 듯

Yellow 타일 개수가 최대 2,000,000 (10^6 <= Yellow <= 10^7) 이기 때문에 시간 복잡도가 아슬아슬 했던 것 같다.

 

코드를 간단히 설명하자면,

1. 1 ~ 총 타일 개수를 총 타일 개수와 나눠 떨어지는 수가 있는지 판단해서 tuple 형태로 cases 리스트에 담는다.

(tuple 로 담는게 익숙해서 저렇게 했는데, 굳이 tuple 로 안 담아도 됨)

 

2. cases 리스트의 중복을 제거한다. ex) [(1,2), (2,1)] -> [(1,2)]

 

3. 그림을 그려보면 알겠지만, 가로와 세로 길이가 2보다는 커줘야 Yellow 타일이 생길 수 있는데, 제한 사항에서 Yellow 타일도 무조건 하나 이상이라고 했으므로 분기를 걸어준다. 그리고 제한 사항에서 가로 길이 >= 세로 길이므로, 알맞게 가로와 세로를 설정한다.

 

4. 'Y' 로 채워진 2차원 배열을 생성한 뒤 테두리 부분만 'B' 로 다시 갱신한다. 그리고 Brown 타일의 수도 같이 세어준다. (4군데의 모퉁이에서 곂치니까 b_count 를 0 이 아닌, -4 로 초기화했음)

 

5. 총 타일 개수에서 b_count 를 뺀 값이 Yellow 타일 개수와 동일하다면, answer = [가로, 세로] 형태로 반환한다.

# 첫 번째 풀이
def solution(brown, yellow):
    answer = []
    cases = []
    sum_tile = brown + yellow
    for x in range(1, sum_tile + 1):
        if sum_tile % x == 0:
            cases.append((x, sum_tile // x))

    # sorted() 시 결과 Type 은 list 이므로 set 중복제거를 위해선 tuple 로 다시 바꿔줘야한다.
    cases = list(set(tuple(sorted(sublist)) for sublist in cases))

    # 가로 길이 >= 세로 길이
    # (x, y) -> x 는 세로 길이, y 는 가로 길이
    # 2차원 배열을 만든다.
    for case in cases:
        # 4군데의 모퉁이에서 곂치므로 -4로 초기화한다.
        b_count = -4
        high, width = case

        # 중앙 타일이 있으려면 최소 가로, 세로 길이가 2보다는 커야한다.
        if high > 2 and width > 2:
            grid = [['Y' for i in range(width)] for j in range(high)]

            # (위) 가로 방향으로 B 채우기
            for i in range(width):
                grid[0][i] = 'B'
                b_count += 1

            # (아래) 가로 방향으로 B 채우기
            for i in range(width):
                grid[high - 1][i] = 'B'
                b_count += 1

            # (왼쪽) 세로 방향으로 B 채우기
            for i in range(high):
                grid[i][0] = 'B'
                b_count += 1

            # (오른쪽) 세로 방향으로 B 채우기
            for i in range(high):
                grid[i][width - 1] = 'B'
                b_count += 1

            if sum_tile - b_count == yellow:
                answer.append(width)
                answer.append(high)
                break

    return answer

 

 

너무 쌩 구현인 것 같아서 책을 참조해봤는데, 역시 아이디어를 떠올릴 수 있는 문제였다.

총 타일 개수를 활용해 사각형을 만들 수 있는 모든 경우의 수를 뽑아오는 것, 경우의 수에서 중복을 제거하는 것까지는 동일하다.

이후 아이디어는, "테스트케이스 2번을 확인했을 때, 총 타일이 9, 3(가로) * 3(세로) 인데, Yellow 타일 개수는 (가로 - 2) * (세로 - 2) 와 동일하다." 라는 것. 다른 테스트케이스를 확인해봐도 최적의 해가 잘 나오는 것을 확인할 수 있다.

이걸로 제출해보니 테스트케이스 7번에서 내가 풀이한 방법으로는 1300ms 정도 나왔는데 이 풀이는 70ms 정도만 나왔다 ;

# 아이디어만 확인하고 개선한 풀이
def solution(brown, yellow):
    answer = []
    cases = []

    sum_tile = brown + yellow

    # 전체 타일에서 가로, 세로가 3 이상인 모든 경우의 수를 뽑아온다.
    for x in range(1, sum_tile + 1):
        if sum_tile % x == 0:
            y = sum_tile // x
            if x > 2 and y > 2:
                cases.append((x, y))

    # cases 중복 제거
    cases = list(set(tuple(sorted(sublist)) for sublist in cases))

    for case in cases:
        # 가로 >= 세로
        high, width = case
        if (high - 2) * (width - 2) == yellow:
            answer.append(width)
            answer.append(high)

    return answer