프로그래머스 문제 5, 6

모음 사전

사전에 알파벳 모음 ‘A’, ‘E’, ‘I’, ‘O’, ‘U’만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 “A”이고, 그다음은 “AA”이며, 마지막 단어는 “UUUUU”입니다. 단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

입력: “AAAAE”

출력: 6

풀이 1

from itertools import product

def solution(word):
    vowel_list = ['A','E', 'I', 'O', 'U']
    
    words = []
    for i in range(1, 6):
        for p in product(vowel_list, repeat=i):
            words.append(''.join(p))
    
    words.sort()
    return words.index(word) + 1
            

• itertools의 product 함수는 중복순열을 계산하는 함수이다.
• product 함수의 repeat 인수는 해당 리스트에서 얼마 만큼 요소를 뽑을지 정하는 값이다.

---

풀이 2

def solution(word):
    res = 0
    cnt = 0

    def dfs(s, w_list):
        nonlocal cnt
        nonlocal res

        if len(s) == 5:
            return

        for i in w_list:
            p = s + i
            cnt += 1
            if p == word:
                res = cnt
                break
            dfs(p, w_list)


    dfs('', ["A", "E", "I", "O", "U"])
    return res

• DFS 방법을 이용하였다.
• 빈 문자열 s에 s의 길이가 5가 될때까지 계속 vowel을 더해나간다.
• s에 i를 더한 값, 즉 p가 word와 같아지더라도 dfs()에 의한 재귀구조의 실행은 계속된다. 즉, 모든 주어진 word 값에 대해 시간 복잡도가 동일하게 나온다.

거리두기 확인하기

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

• 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
• 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
• 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

입력: [[“POOOP”, “OXXOX”, “OPXPX”, “OOXOX”, “POXXP”], [“POOPX”, “OXPXP”, “PXXXO”, “OXXXO”, “OOOPP”], [“PXOPX”, “OXOXP”, “OXPOX”, “OXXOP”, “PXPOX”], [“OOOXX”, “XOOOX”, “OOOXX”, “OXOOX”, “OOOOO”], [“PXPXP”, “XPXPX”, “PXPXP”, “XPXPX”, “PXPXP”]]

출력: [1, 0, 1, 1, 1]

풀이 1

from collections import deque

def bfs(p):
    start = []
    
    for i in range(5): # 시작점이 되는 P 좌표 구하기 -> i는 행, j는 열
        for j in range(5):
            if p[i][j] == 'P':
                start.append([i, j])
    
    for s in start:
        queue = deque([s])  # 큐에 초기값
        visited = [[0]*5 for i in range(5)]   # 방문 처리 리스트
        distance = [[0]*5 for i in range(5)]  # 경로 길이 리스트 
        visited[s[0]][s[1]] = 1     # P인 곳은 1로 만들어주기
        
        while queue:
            y, x = queue.popleft()  # y는 행, x는 열
        
            dx = [-1, 1, 0, 0]  # 좌우
            dy = [0, 0, -1, 1]  # 상하

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0<=nx<5 and 0<=ny<5 and visited[ny][nx] == 0:    # 방문하지 않은 곳만 탐색함
                    
                    if p[ny][nx] == 'O':    # 좌우, 상하에 위치한 값이 0이면 큐에 그 값을 추가함
                        queue.append([ny, nx])
                        visited[ny][nx] = 1
                        distance[ny][nx] = distance[y][x] + 1
                    
                    if p[ny][nx] == 'P' and distance[y][x] <= 1:    # P로 부터 한칸 떨어져 있으면 0을 리턴함
                        return 0
    
        print(distance)
    return 1


def solution(places):
    answer = []
    
    for room in places:
        answer.append(bfs(room))
    
    return answer

• start 리스트에는 p의 P의 좌표를 담는다.
• visited 리스트는 노드의 방문 여부를 얄려준다.
• distance는 경로 길이를 처리하는 리스트로, P로부터 몇 칸 만큼 떨어져 있는지 나타내는 리스트이다. P와 한 칸 떨어져 있으면 0, P와 두 칸 떨어져 있으면 1이다.
• queue 리스트에는 P 주변의 값이 0일 때와 P일 때 그 좌표를 담는다. 즉, P 바로 주변에 있는 값이 P이거나 0을 거쳐서 있는 값이 P일 경우 0을 리턴을 한다.