[8회차]

Programmers Level.2 전화번호 목록

def solution(phone_book):
    for p_1 in phone_book:
        for p_2 in phone_book:
            if p_1 == p_2:
                continue
            for i in range(min(len(p_1),len(p_2))):
                if p_1[i] == p_2[i] and i == min(len(p_1),len(p_2)) - 1:
                    return False
                elif p_1[i] == p_2[i]:
                    continue
                else:
                    break
    return True

def solution(phone_book):
    for p_1 in phone_book:
        for p_2 in phone_book:
            if p_1 == p_2:
                continue
            m = min(len(p_1),len(p_2))
            if p_1[:m] == p_2[:m]:
                return False
    return True

 - 처음에는 전화번호 부에서 두 개의 번호 씩을 선택해 한 글자 씩 비교하는 방식으로 했는데 효율성테스트에서 시간초과가 나왔다.

def solution(phone_book):
    phone_book = sorted(phone_book)
    for i in range(len(phone_book) - 1):
        m = min(len(phone_book[i]),len(phone_book[i+1]))
        if phone_book[i][:m] == phone_book[i+1][:m]:
            return False
    return True

 - 위에 2개가 효율성 테스트에서 안 되는 이유는 모든 케이스를 일일이 비교하느라 생긴 일이라고 생각했다. 비교해야할 케이스를 줄이고 비교하려면 어떻게 해야할 지 고민했다.

 - 다른 사람의 풀이른 보니 startswith를 이용할 수도 있더라.

 

 

Programmers Level.2 소수 찾기

from math import sqrt
from itertools import permutations


def is_prime(number):
    if number in (0, 1):
        return False
    for i in range(2, int(sqrt(number)) + 1):
        if number % i == 0:
            return False
    return True


def solution(numbers):
    answer = 0
    permut = []
    for r in range(1, len(numbers) + 1):
        for i in permutations(numbers, r):
            a = int(''.join(list(i)))
            if a not in permut:
                permut.append(a)
    for i in permut:
        if is_prime(i):
            answer += 1
    return answer

 - 모든 길이에 대한 순열을 만들기 위해 for문을 사용.

 

 

Programmers Level.2 방문 길이

def solution(dirs):
    answer = 0
    graph = [[[False, False, False, False] for __ in range(11) ] for _ in range(11)] # 순서대로 U, R / L, D
    direction = ['U','R','L','D']
    dx = [0, 1, -1, 0]
    dy = [1, 0, 0, -1]
    x = 5
    y = 5
    for i in dirs:
        for j in range(4):
            if direction[j] == i:
                nx = x + dx[j]
                ny = y + dy[j]
                if nx < 0 or nx > 10 or ny < 0 or ny > 10:
                    continue
                if graph[nx][ny][3-j] == False or graph[x][y][j] == False:
                    graph[x][y][j] = True
                    graph[nx][ny][3-j] = True
                    answer += 1
                x = nx
                y = ny
    return answer

 - 이미 방문한 지점을 구별하기 위한 아이디어 구상에 시간이 좀 걸렸다.

 - 아래는 다른 사람의 풀이이고, 집합을 이용해 구현했다. 

def solution(dirs):
    s = set()
    d = {'U': (0,1), 'D': (0, -1), 'R': (1, 0), 'L': (-1, 0)}
    x, y = 0, 0
    for i in dirs:
        nx, ny = x + d[i][0], y + d[i][1]
        if -5 <= nx <= 5 and -5 <= ny <= 5:
            s.add((x,y,nx,ny))
            s.add((nx,ny,x,y))
            x, y = nx, ny
    return len(s)//2

 

 

Programmers Level.2 최댓값과 최솟값

def solution(s):
    lists = list(map(int, s.split(' ')))
    maxi = max(lists)
    mini = min(lists)
    answer = ' '.join([str(mini), str(maxi)])
    return answer

 

 

Programmers Level.2 최솟값 만들기

def solution(A,B):
    answer = 0
    A = sorted(A)
    B = sorted(B,reverse=True)
    for a,b in zip(A,B):
        answer += a*b
    return answer

 

 

Programmers Level.2 행렬의 곱셈

def solution(arr1, arr2):
    answer = [[0] * len(arr2[0]) for _ in range(len(arr1))]
    for i in range(len(arr1)):
        for j in range(len(arr2[0])):
            for k in range(len(arr1[0])):
                answer[i][j] += arr1[i][k]*arr2[k][j]
    return answer

 

 

Programmers Level.2 가장 큰 정사각형 찾기

def solution(board):
    m = len(board)
    n = len(board[0])
    for i in range(1,m):
        for j in range(1,n):
            if board[i][j] != 0:
                board[i][j] = min(board[i-1][j], board[i-1][j-1], board[i][j-1]) + 1
    a = max(map(max, board))
    return a ** 2