[python code review] 6주차 (암호 만들기, 기둥과 보 설치, Z)

[암호만들기]

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

[bruteforce]

from itertools import combinations

l, c = map(int, input().split())
words = sorted(input().split())

for comb in list(combinations(words, l)):
    v, e = 0, 0
    for word in comb:
        if word in ['a', 'e', 'i', 'o', 'u']:
            v += 1
        else:
            e += 1
    # 최소 한개의 모음과 두개의 자음을 포함한다면
    if v >= 1 and e >=2:
        print(''.join(comb))

 

combinations을 이용하면 가장 간단해보여서 구현해봤더니 정답 처리되었다. 

자음이 영단어로 뭐였는지 기억이 안나서 e라고 했는데.. 자음은 영어로 Consonants이다.  

코드 개선 )

for comb in list(combinations(words, l)):
    v = 0
    for word in comb:
        if word in ['a', 'e', 'i', 'o', 'u']:
            v += 1
    # 최소 한개의 모음과 두개의 자음을 포함한다면 : 자음 변수를 만들지 않고 l-v 사용 
    if v >= 1 and (l-v) >= 2:
        print(''.join(comb))

 

그리고 딱 보니까 백트래킹으로도 가능해서 이리저리 열심히 풀어보았다.

[backtracking]

L, C = map(int, input().split())
words = sorted(input().split())

def possible(lst):
    vowel, consonants = 0, 0
    for data in lst:
        if data in ['a', 'e', 'i', 'o', 'u']:
            vowel += 1
        else:
            consonants += 1
    if vowel >= 1 and consonants >= 2:
        return True
    return False


def backtracking(l, idx, arr):
    if len(arr) == l:
        if possible(arr):
            print(''.join(arr))
        return
    for idx in range(idx, C):
        arr.append(words[idx])
        backtracking(l, idx + 1, arr)
        arr.pop()

backtracking(L, 0, [])

코드개선)

L, C = map(int, input().split())
words = sorted(input().split())
vowels = ['a', 'e', 'i', 'o', 'u']

def backtracking(l, idx, arr, v, c):
    if len(arr) == l:
        if v >= 1 and c >= 2:
            print(''.join(arr))
        return
    for idx in range(idx, C):
        arr.append(words[idx])
        if words[idx] in vowels:
            backtracking(l, idx + 1, arr, v+1, c)
        else:
            backtracking(l, idx + 1, arr, v, c+1)
        arr.pop()

backtracking(L, 0, [], 0, 0)

 

이런 식으로 모음개수와 자음개수를 매개변수로 이용하여 풀면 더 간결하게 문제를 풀 수 있다.

백트래킹이 멋은 있지만 구현하기 어려울 뿐더러 combination을 사용한 풀이가 속도면에서 더욱 빨랐다.

코딩테스트에서는 왠만하면 combination을 사용하여 정확하고 빠르게 풀이하는게 나을 듯 싶다.

 

 

[기둥과 보 설치]

https://programmers.co.kr/learn/courses/30/lessons/60061

코딩테스트 연습 - 기둥과 보 설치

[구현]

def build(answer):
    for x, y, s in answer:
        # 기둥인 경우
        if s == 0:
            # 바닥 위에 있는 경우
            if y == 0:
                continue
            # 보의 한쪽 끝에 위에 있는 경우
            if [x, y, 1] in answer:
                continue
            if [x-1, y, 1] in answer:
                continue
            # 다른 기둥 위에 있는 경우
            # if [x, y+1, 0] in answer:
            if [x, y-1, 0] in answer:
                continue
            return False
        # 보인 경우 (s == 1)
        else:
            # 한쪽 끝 부분이 기둥 위에 있는 경우
            if [x, y-1, 0] in answer:
                continue
            if [x+1, y-1, 0] in answer:
                continue
            # 양쪽 끝 부분이 다른 보와 동시에 연결된 경우
            if [x-1, y, 1] in answer and [x+1, y, 1] in answer:
                continue
            return False
    return True
        
def solution(n, build_frame):
    answer = []
    for i, j, a, b in build_frame:
        # 삭제할 경우 
        if b == 0:
            answer.remove([i,j,a])
            if not build(answer):
                answer.append([i,j,a])
        # 설치할 경우 
        else:
            answer.append([i,j,a])
            if not build(answer):
                answer.remove([i,j,a])
        
    return sorted(answer)

처음에는 아래처럼 build 함수에서 answer 변수를 전역변수로 지정하여

우선 기둥인 경우와 보인 경우를 나눈 뒤 answer 리스트에 조건을 만족하는 변수가 있는 경우,

answer 리스트에 해당 변수를 추가하게끔 구현.

하지만 이런식으로 구현하려다보니 보의 조건 중에서 '양쪽 끝 부분이 다른 보와 동시에 연결된 경우'를 구현하기 위해서는 이중 for문이 필요하였기에 매우 비효율적이었다.

전에 이 문제를 풀어본 적이 있어서 모든 answer 변수와 target x, y 변수를 비교하지 말고 조건에 충족하는 좌표가 answer 리스트 있는지 즉 if 조건에 충족하는 좌표 in answer:  라는 조건문을 대체하여 쓸 수 있다는 점이 떠올랐다. 

조건 하나라도 실수하는 경우 오답이 나오는 구현 문제가 코딩테스트에서 많이 출제된다.    

 

def build(x, y, structure):
    global answer
    # 기둥인 경우
    if structure == 0:
        # 바닥 위에 있는 경우
        if y == 0:
            answer.append((x, y, structure))
            return
         
        for sx, sy, s in answer:
            # 보의 한쪽 끝에 위에 있는 경우
            if s == 1 and (sx = x or sx+1 == x):
                answer.append((x, y, structure))
                return
            # 다른 기둥 위에 있는 경우
            if s == 0 and (sy+1 == y):
                answer.append((x, y, structure))
                return

 

[Z]

https://www.acmicpc.net/problem/1074

1074번: Z

[재귀 구현]

n, r, c = map(int, input().split())
result = 0
while n > 1:
    # 각 사분면의 길이
    half = (2**n)//2
    # 2사분면에 위치
    if r < half and c < half:
        pass
    # 1사분면에 위치
    elif r < half and c >= half:
        result += half**2
        c -= half
    # 3사분면에 위치
    elif r >= half and c < half:
        result += (half**2)*2
        r -= half
    # 4사분면에 위치
    else:
        result += (half**2)*3
        r -= half
        c -= half
    n -= 1
# 2^1 * 2^1 일 때
if n == 1:
    if (r,c) == (0,0):
        pass
    if (r,c) == (0,1):
        result += 1
    if (r,c) == (1,0):
        result += 2
    if (r,c) == (1,1):
        result += 3
print(result)

아무리 생각해도 모르겠어서 블로그를 참고함..

그래프를 4등분으로 나눠 몇사분면인지를 알아내는 과정을 더 이상 쪼갤 수 없을때까지 반복.

• 함수의 크기가 2ⁿ*2ⁿ인 2차원 배열을 4등분으로 나누려면 half = 2ⁿ//2
• n -= 1 을 반복하며 나눌 수 있는 제일 작은 사분면의 위치까지 알아낸다.