[프로그래머스] <방의 개수> 파이썬

programmers.co.kr/learn/courses/30/lessons/49190#

코딩테스트 연습 - 방의 개수

def solution(arrows):
    move = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
    edge = []
    vertex = [(0,0)]
    current = (0,0)
    room = 0
    for i in arrows :
        current = vertex[-1]
        a,b = current[0] + move[i][0], current[1] + move[i][1]
        if (a,b) in vertex :
            if (current[0], current[1], a, b) in edge or (a, b, current[0], current[1]) in edge:
                continue
            else : 
                edge.append((current[0], current[1], a, b))
                vertex.append((a,b))
                room += 1
        else :
            edge.append((current[0], current[1], a, b))
            vertex.append((a,b))
    return room
            
            

테케는 맞는데 채점 전체 실패

테스트 케이스 추가

def solution(arrows):
    move = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
    edge = []
    vertex = [(0,0)]
    current = (0,0)
    room = 0
    for i in arrows :
        
        for j in range(1,3) :
            current = vertex[-1]
            a, b = current[0] + move[i][0], current[1] + move[i][1]
            if (a,b) in vertex :
                if (current[0], current[1], a, b) in edge or (a, b, current[0], current[1]) in edge:

                    edge.append((current[0], current[1], a, b))
                    vertex.append((a,b))                   
                    continue
                else : 

                    edge.append((current[0], current[1], a, b))
                    vertex.append((a,b))
                    room += 1  
                    continue

            edge.append((current[0], current[1], a, b))
            vertex.append((a,b))

    return room
            
            

정확성 테스트

테스트 1 〉	통과 (1.33ms, 10.3MB)
테스트 2 〉	통과 (15.34ms, 10.3MB)
테스트 3 〉	통과 (62.67ms, 10.5MB)
테스트 4 〉	통과 (217.63ms, 10.8MB)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	통과 (4276.65ms, 14.2MB)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)

채점 결과

정확성: 55.6

합계: 55.6 / 100.0

 

from collections import defaultdict, deque
def solution(arrows):
    move = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
    edge = defaultdict()
    vertex = defaultdict()
    queue = deque()
    
    current = (0,0)
    
    
    room = 0
    for i in arrows :      
        for j in range(2) :
            x, y = current[0]+move[i][0], current[1]+move[i][1]
            vertex[(x,y)] = False
            edge[(current,(x,y))] = False
            current = (x,y)
            queue.append(current)

    current = (0,0)  
    vertex[current] = True
    while queue :
        x, y = queue.popleft()
        
        if vertex[(x,y)] == True and (edge[(current,(x,y))] == False or edge[((x,y), current)] == False) :
            room += 1
        vertex[(x,y)] = True
        edge[(current,(x,y))], edge[((x,y), current)] = True, True
        current = (x,y)


    return room
            
            

정확성 테스트

테스트 1 〉	통과 (0.54ms, 10.3MB)
테스트 2 〉	통과 (1.93ms, 10.6MB)
테스트 3 〉	통과 (3.89ms, 10.8MB)
테스트 4 〉	통과 (8.95ms, 12.3MB)
테스트 5 〉	통과 (71.99ms, 25.4MB)
테스트 6 〉	통과 (517.22ms, 83.2MB)
테스트 7 〉	통과 (38.49ms, 21.4MB)
테스트 8 〉	통과 (340.75ms, 81.1MB)
테스트 9 〉	통과 (706.62ms, 141MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0