[solved.ac 골드4] 1089_스타트링크 타워 (파이썬, 구현)

밑의 사진을 클릭하면 문제 링크로 이동합니다

제한 사항

문제

스타트링크 타워는 총 10N개 층이 있는 고층 건물이고, 0층부터 10N-1층으로 번호가 매겨져 있다. 층 번호를 숫자 N개로 표현한다. 숫자 N개로 층 번호를 표시할 수 없는 경우 앞에 0을 채운다.

숫자 1개를 표현하려면 전구 5×3개가 필요하고, 이 전구를 세로 크기 5, 가로 크기 3인 격자 형태로 배치한다. 다음은 0부터 9까지 숫자를 나타낸 것이다. '#'는 불이 켜져있는 전구, '.'는 불이 꺼져있는 전구이다.

###...#.###.###.#.#.###.###.###.###.###
#.#...#...#...#.#.#.#...#.....#.#.#.#.#
#.#...#.###.###.###.###.###...#.###.###
#.#...#.#.....#...#...#.#.#...#.#.#...#
###...#.###.###...#.###.###...#.###.###

엘리베이터에 있는 층 번호 안내판의 상태가 주어진다. 안내판의 각 숫자는 불이 꺼져있는 전구 한 열로 구분되어 있다. 안내판의 일부 전구는 고장이 나서 항상 꺼져있는 상태이다. 꺼져있는 전구의 일부가 고장이 났다고 가정할 때, 현재 층 번호 안내판이 나타내고 있다고 볼 수 있는 모든 층 번호의 평균을 구해보자.

입력

첫째 줄에 N이 주어진다. N은 9보다 작거나 같은 자연수이다. 둘째 줄부터 다섯 개의 줄에는 엘리베이터 층 번호 안내판의 상태가 주어진다. 각 문자열의 길이는 4N-1이다.

 

출력

첫째 줄에 층 번호 안내판이 나타내고 있다고 가정할 수 있는 모든 층 번호의 평균을 출력한다. 만약, 가능한 층 번호가 없는 경우 -1을 출력한다.

정답과의 절대/상대 오차는 10^(-5)까지 허용한다.

예제

 

---

나의 풀이

숫자 떼어놓기

주어진 입력은 3열의 숫자와 1열의 공백이 n번 반복되는 구조이다. 이 숫자들을 하나씩 떼어놓으려면 4개 마다 분리를 한 후 3개의 열만 저장하면 된다. 그리고 샘플로 주어진 0 ~ 9 까지의 문자열도 마찬가지의 방법으로 떼어놓을 수 있다.

두 번 이상 사용되는 기능이기 때문에 함수로 따로 작성했다.

def split_nums(li):
    n = (len(li[0]) + 1) // 4 # 분리 후 개수
    ret = [[] for _ in range(n)]
    for i in range(5): # 행 순회
        row = li[i]
        for j in range(n):
            start = j * 4 # 4 칸 뛰기
            ret[j].append(row[start:start + 3]) # 3개 열만 저장

    return ret

 

부분 집합 확인

떼어낸 5 x 3 문자열 리스트와 어떤 숫자를 나타낸 5 x 3 문자열 리스트의 겹치는 부분을 확인하기 위해서 Set 자료구조를 사용했다. set에는 5 x 3 리스트에서의 좌표를 저장한다. set을 사용하면 issubset 메서드를 통해서 간단히 부분 집합임을 확인할 수 있다.

확인하고자 하는 문자열 리스트를 0 ~ 9 까지의 문자열 리스트를 순회하며 부분 집합인지 확인하고 부분 집합이라면 기록한다.

# '#'의 좌표를 set에 저장하여 반환
def pos(li):
    ret = set()
    for i in range(5):
        for j in range(3):
            if li[i][j] == '#':
                ret.add((i, j))
    return ret

tmp = [[] for _ in range(n)]
for i in range(n):
    for j in range(10):
        if nums[i].issubset(decimal[j]): # 부분집합 확인
            tmp[i].append(j)

 

답 구하기

만약 부분집합을 확인해서 얻은 가능한 숫자 리스트가 li = [[1, 2, 3], [4, 5], [6]] 이라면 조합 가능 한 숫자는 다음과 같을 것이다.

• 146
• 156
• 246
• 256
• 346
• 356

우선 답을 구하기 위해서는 위 6개의 숫자를 모두 더해서 6으로 나누면 된다. 이걸 어떻게 코드로 나타낼까? 백트래킹이나 DFS와 같은 알고리즘을 사용할 수도 있을 것이다. 하지만 각 리스트의 크기가 달라서 쉽진 않다.

나는 이것을 쉽게 할 수 있는 방법을 찾아냈다.

우선 나올 수 있는 숫자의 개수를 센다. li 의 아이템 크기가 각각 3, 2, 1이기 때문에 조합해보면 3 x 2 x 1 = 6개의 숫자가 나올 것을 계산할 수 있다.

 

이제 각 자리 수가 몇 번 등장하는 지 알 수 있다.

첫 번째 자리 숫자인 1, 2, 3은 각각 2번씩, 두 번째 자리 숫자인 4, 5는 각각 3번씩, 그리고 세 번째 자리 숫자인 6은 6번 등장했다.

등장하는 횟수는 전체 나올 수 있는 숫자의 개수에서 해당 자리에 올 수 있는 숫자의 개수를 나눈 것이다.

즉, 2번, 3번, 6번 등장한 것은 (3 / 6), (2 / 6), (1 / 6) 인 것이다.

 

이제 숫자를 더해볼 수 있다.

첫 번째 자리 숫자는 1, 2, 3이 2번 씩 등장하므로 (1+2+3) x 2 로 표현할 수 있다. 마찬가지로 두 번째 자리 숫자는 (4+5) x 3, 세 번째 자리 숫자는 6 x 6 으로 표현할 수 있다.

첫 번째 자리는 백의 자리를 나타내므로 100을 곱하고, 두 번째 자리 숫자는 십의 자리를 나타내므로 10을 곱하고, 세 번째 자리 숫자는 1을 곱한 후에 각각을 더하면 답을 구할 수 있다.

 

결국 식은 다음과 같이 만들 수 있다.

위 식에서 전체 수의 개수만큼 나누면 찾고자 하는 답이 된다.

단, 어떤 자리 숫자는 어떤 숫자도 만들 수 없는 경우는 바로 -1을 반환하면 된다.

def get_answer(li):
    if [] in li: return -1 # 만들 수 없는 수가 존재
    count = 1
    for i in range(n):
        count *= len(li[i]) # 만들 수 있는 수의 개수
    ret = 0
    for i in range(n):
        ret += sum(li[i]) * (count // len(li[i])) * 10 ** (n - i - 1)
    return ret / count

 

전체 코드

n = int(input())
nums = [input() for _ in range(5)]
decimal = ["###...#.###.###.#.#.###.###.###.###.###",
           "#.#...#...#...#.#.#.#...#.....#.#.#.#.#",
           "#.#...#.###.###.###.###.###...#.###.###",
           "#.#...#.#.....#...#...#.#.#...#.#.#...#",
           "###...#.###.###...#.###.###...#.###.###"]


def split_nums(li):
    n = (len(li[0]) + 1) // 4
    ret = [[] for _ in range(n)]
    for i in range(5):
        row = li[i]
        for j in range(n):
            start = j * 4
            ret[j].append(row[start:start + 3])

    return ret


def pos(li):
    ret = set()
    for i in range(5):
        for j in range(3):
            if li[i][j] == '#':
                ret.add((i, j))
    return ret


def init():
    global nums, decimal
    nums = split_nums(nums)
    nums = list(map(pos, nums))
    decimal = split_nums(decimal)
    decimal = list(map(pos, decimal))


def get_answer(li):
    if [] in li: return -1
    count = 1
    for i in range(n):
        count *= len(li[i])
    ret = 0
    for i in range(n):
        ret += sum(li[i]) * (count // len(li[i])) * 10 ** (n - i - 1)
    return ret / count


def solution():
    tmp = [[] for _ in range(n)]
    for i in range(n):
        for j in range(10):
            if nums[i].issubset(decimal[j]):
                tmp[i].append(j)
    print(get_answer(tmp))


init()
solution()

 

채점 결과