모의고사 해설 3. 방의갯수

 

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

 

 

arrows = [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0]  # 3
arrows = [5, 2, 7, 1, 6, 3]  # 3
arrows = [6, 0, 3, 0, 5, 2, 6, 0, 3, 0, 5]  # 3


now = [0, 0]  # 현재좌표
dic_arrows = {
    0: [0, 1],
    1: [1, 1],
    2: [1, 0],
    3: [1, -1],
    4: [0, -1],
    5: [-1, -1],
    6: [-1, 0],
    7: [-1, 1]
}
path = {}


def check_dia(path, now, arrow):
    # print("-----------------------")
    c_now = now[:]
    c_arrow = arrow
    if c_arrow > 6:
        c_arrow -= 7
    else:
        c_arrow += 1
    c_now[0] += dic_arrows[c_arrow][0]
    c_now[1] += dic_arrows[c_arrow][1]

    if c_arrow > 2:
        c_arrow -= 3
    else:
        c_arrow += 5
    # print(c_now)
    # print(c_arrow)
    # print("-----------------------")
    try:

        c_check_list = path[str(c_now)]
        if c_arrow in c_check_list:
            return True
    except:
        pass
    # print("-----------------------")
    return False


def solution(arrows):
    result = 0
    for arrow in arrows:
        # 이동전
        inline = True
        dic_p = str(now)
        try:
            if arrow not in path[dic_p]:
                path[dic_p] = path[dic_p]+[arrow]
        except:
            path[dic_p] = [arrow]
        # 이동후
        now[0] += dic_arrows[arrow][0]
        now[1] += dic_arrows[arrow][1]
        if arrow > 3:
            arrow = arrow-4
        else:
            arrow = arrow+4

        dic_p = str(now)
        try:
            if arrow not in path[dic_p]:
                path[dic_p] = path[dic_p]+[arrow]
                result += 1
                inline = False
            else:
                inline = True

        except:
            path[dic_p] = [arrow]
            inline = False

        if (arrow % 2 == 1) and (not inline):
            result += check_dia(path, now, arrow)
    return result


print(solution(arrows))

 

 

 

 

해설

1. 선을 그리는 도중 다른 선을 만나면 공간이 생긴다.

• 이동한 점에대한 정보를 path 출력해서 있을때마다 result+=1
• 없으면 path에 저장

문제점=> 교차점 있으면 추가가 안된다, 같은 선은 겹치는 경우 오류

2. 같은선인 경우 inline=True로 적용

3. 대각선으로 교차할경우=> 확인하는 작업 check_dia()

 

공간복잡도 낮추는방안

path에서 각 좌표에 대한 방향성을 메모하지만 각 변마다 2개의 좌표에 찍힌다

즉 중복처리를 한다면 공간복잡도는 내려가지만 확인하는 작업에서 시간복잡도가 올라갈것이다

 

같이 한팀원 :https://sogummi.tistory.com/89