프로그래머스 - 최소직사각형, 전력망을 둘로 나누기.py

 

*  프로그래머스 - 최소직사각형(lv.1)

< 정답 코드 >

def solution(sizes):
    big = []
    small = []
    
    for size in sizes:
        big.append(max(size))
        small.append(min(size))
        
    return max(big)*max(small)

 

가로 세로 회전이 가능한 경우에 어떻게 비교해야 할지 아이디어가 떠오르지 않아서 해설을 참고했다.

제시된 명함의 길이 중 큰 것은 더 큰 값들 사이에 속해야 묻어갈 수 있고, 작은 것은 더 작은 값들에 속해야 묻어가거나 값을 최소화 할 수 있다는 것을 조금만 더 생각했더라면 .. 싶다.

 

*  프로그래머스  - 소수찾기(lv.2)

< 정답코드 >

from itertools import combinations, permutations
def is_prior(check):
    if check <= 1:
        return False;
    for i in range(2,check):
        if check % i == 0:
            return False
    return True

def solution(numbers):
    prior = 0
    s = set()
    checking = set()
    for i in range(1,len(numbers)+1):
        li = list(permutations(numbers,i))
        for a in li:
            check = ''.join(a)
            if is_prior(int(check)) and int(check) not in checking:
                prior+=1
                checking.add(int(check))
    
    return prior

 

순열/조합 사용법과 .join() 사용법, 소수 조건 등을 모르는 상태여서 해법을 구글링했다. 자주 등장하는 개념들이니 기억해놓자.

 

* from itertools import permutations, combinations

permutations(열거형 자료, 선택할 인자 개수) > 반환형태가 주소값이므로, 사용하기 위해서는 list로 감싸주던지 할 것.

 

* ''.join(열거형 자료)

또한 여러 순열형태는 하나로 이어부터있지 않고 ('a','b','c')처럼 생겼으므로 이를 하나의 문자로 합쳐주는 ''.join(열거형 자료) 를 사용한다. 이때 열거형 자료 내부의 자료타입은 문자열(문자)여야 한다. 

 

* 소수

소수는 나눠질 수 있는 약수가 1과 자기 자신 뿐인 수이다.

따라서 N 정수에 대해 검사한다고 가정하면 2부터 N-1까지 모든 수를 나누어 봤을 때 나누어 떨어지는 수가 없어야 한다. ( 나머지가 0 : % == 0 )

1은 소수가 아니다.

 

* 중복 수

'011' '01' 은 각각 11, 1과 같은 수로 인식해야 하므로 문자열 그대로 놔두지 말고 int를 씌워서 같은 수로 처리해야한다. 

이를 고려해서 같은 경우에 대해 중복으로 소수의 숫자를 올리는 일은 없어야한다.

 

 

*  프로그래머스  - 전력망을 둘로 나누기(lv.2)

def dfs(start,wires,used,how):
    if start not in used:
        used.append(start)
        how += 1
        stack = [] #start에서 방문 가능한 노드
        for wire in wires:
            if start == wire[0]:
                stack.append(wire[1])
            if start == wire[1]:
                stack.append(wire[0])
        while stack != []:
            check = stack[0]
            del stack[0]
            dfs(check,wires,used,how)
        return how, used
    else:
        return -1, used
            

def solution(n, wires):
    
    used = []
    can = []
    for i in range(len(wires)):
        check = wires[i]
        del wires[i]
        
        nodes_zero, used = dfs(check[0],wires,used,0) 
        #[0]쪽으로 연결된 트리의 노드 수와 수정된 used
        
        nodes_one, used = dfs(check[1],wires,used,0) 
        #[1]쪽으로 연결된 트리의 노드 수와 수정된 used
        
        #노드를 재방문 하려 한다면 두 트리로 분리되지 않은 것이므로 이를 표시하기 위해 
        #-1 리턴, 그게 아니라면 그 트리의 노드수 리턴
        
        if nodes_zero != -1 and nodes_one != -1: #두 트리가 잘 분리 되었다면
            can.append(abs(nodes_zero - nodes_one))
    print(can)
    answer = min(can)
    return answer