BOJ_1759 암호 만들기

• TOC {:toc}

이 글은 백준 온라인 저지의 1759번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.07.23 (Python)

import sys
input = sys.stdin.readline

L, C = map(int, input().split())
alpha = list(input().split())
alpha.sort(reverse=True)

def dfs():
    v_cnt = 0
    stack = []
    for i, x in enumerate(alpha):
        cnt = 0
        if x in ("a", "e", "i", "o", "u"):
            cnt = 1
        stack.append((i, x, cnt))

    while stack:
        i, w, v_cnt = stack.pop()
        if len(w) == L:
            print(w)
            continue

        for k in range(i):
            # L - len(w) - 1: 뒤에 더 와야 하는 문자의 개수
            # k: 남은 사용할 수 있는 문자의 개수
            if k < L - len(w) - 1:
                continue

            is_vowel = 0
            if alpha[k] in ("a", "e", "i", "o", "u"):
                is_vowel = 1

            v_cnt += is_vowel
            if (L - len(w) - 1) + v_cnt >= 1 and L - v_cnt >= 2:
                stack.append((k, w + alpha[k], v_cnt))
            v_cnt -= is_vowel

dfs()

아이디어 & 풀이

백 트래킹을 이용한 풀이이다.

dfs로 입력받은 문자들을 방문하면서 조건을 만족하면 단어에 추가한다.

• 입력받은 문자는 역순으로 정렬한다.
  • 첫 문자를 가장 처음에 꺼내 써야 하는데 popleft가 아닌 pop을 이용하기 위해서는 역순으로 방문해 push 해야 한다.
• 암호는 알파벳이 증가하는 순서로 배열되어있기 때문에 현재 문자보다 뒤쪽의 문자들만 순회하면 된다.
  • 이를 위해 마지막으로 추가한 문자의 순번 i를 함께 저장한다.
• 조건은 최종 자음, 모음 수가 제한 이상이어야 하는 것이다.
• dfs는 스택을 이용해 구현한다.
  • 위의 내용을 구현하기 위해 스택에 현재 단어 w와 함께, 현재 단어의 마지막 문자의 위치 i, 모음의 개수 v_cnt를 함께 push 한다.

스택에서 pop 한 원소에 대해

• 단어 w의 길이가 암호 길이인 L과 같으면 출력하고 다음 원소로 넘어간다.
• 입력받은 알파벳(alpha)을 i - 1번째까지 순회하면서
  • i는 단어 w의 마지막 문자의 순번으로 스택에 해당 원소를 추가할 때 같이 추가한다.
  • 역순으로 정렬되어 있기때문에 i까지 순회하면 마지막 문자보다 뒤에 오는 원소만 역순으로 순회하게 된다.
• 조건을 만족하면 스택에 추가한다.
  • 조건은 암호를 완성했을 때 모음은 한 개 이상, 자음은 두 개 이상이어야 한다.

조건을 확인하는 과정은 다음과 같다.

• 자음 개수는 현재 단어의 길이 - 모음의 개수이다.
• 남은 문자에는 자음, 모음 어느 것이 들어갈 줄 모르기 때문에 예상 자/모음 개수는 현재 자/모음 개수 + 남은 문자의 수이다.
• 현재 단어는 이전 단어 w + 현재 문자 alpha[k]로 구성되어 있다.
  • 현재 단어의 전체 문자 수는 len(w) + 1)이다.
• 현재 문자가 모음이면 v_cnt를 1 증가하고 자음이면 증가하지 않는다.
  • 현재 단어의 모음 count, is_vowel을 정의해 그 값을 모음이면 1, 자음이면 0으로 정해 더한다.
• 남은 문자의 수는 전체 암호 길이인 L에서 현재 단어 길이를 빼면 된다.
  • 현재 단어의 문자 수가 len(w) + 1 이기 때문에 남은 문자의 수는 L - len(w) - 1 이다.

위의 내용을 종합해 예상 자/모음 개수를 구하면 다음과 같다.

• L - len(w) - 1 + v_cnt + is_ vowel 는 1보다 크거나 같아야 하고,L - (v_cnt + is_vowel) 는 2보다 크거나 같아야 한다.
• 풀이에서는 v_cnt += is_vowel을 미리 계산한 뒤, 조건을 검사하고 다시 되돌렸다.
  • 다음 문자에 대해 검사하려면 다시 이전 단어로 돌려놔야 하므로.
• 이 조건을 통과하지 못하면 스택에 추가되지 않기 때문에 해당 문자 이후의 경우를 모두 drop 하는 것과 같다.

추가로, 뒤에 덧붙여야 하는 문자보다, 덧붙일 수 있는 문자의 개수가 적으면 암호를 완성하지 못한다. 이 경우는 위의 조건을 체크하지 않고 바로 넘긴다.

• 예를 들어 예제 입력에서 at는 뒤에 두 글자가 더 붙어야 암호를 완성할 수 있지만, 뒤에 덧붙일 수 있는 문자는 w 밖에 없기 때문에 암호를 완성할 수 없다.
• 현재 문자 alpha[k]를 추가한 경우에
  • 뒤에 더 와야 하는 문자의 개수는 남은 문자의 수와 같으므로 L - len(w) - 1이다.
  • alpha[k] 뒤에 덧붙일 수 있는 문자의 수는 k개이다.
    • alpha[k]보다 뒤의 알파벳이어야 하므로 alpha[0] ~ alpha[k - 1] 값이다. k개
• 즉, k < L - len(w) - 1의 경우 조건 체크 없이 넘어간다.

피드백

• 문자열도 iterable 하므로 aeiou를 리스트가 아닌 문자열로 둬도 된다.

2022.04.08 (JS)

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

function dfs(n, pw) {
    if (pw.length === L) {
        let verbCount = 0;
        for (const c of pw) {
            if ("aeiou".includes(c)) verbCount += 1;
        }

        if (verbCount >= 1 && pw.length - verbCount >= 2) {
            console.log(pw);
        }
        return;
    }

    for (let i = n + 1; i < C; i += 1) {
        dfs(i, pw + alpha[i]);
    }
}

const [LC, line] = input;
const [L, C] = LC.split(" ").map((n) => parseInt(n));
const alpha = line.split(" ").sort();

dfs(-1, "");

참고 답안

from itertools import combinations

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

for pw in list(combinations(alpha, L)):
    v = 0
    for c in pw:
        if c in "aeiou":
            v += 1

    if v >= 1 and L - v >= 2:
        print("".join(pw))

아이디어 & 풀이

itertools의 combination을 이용한다.

• 입력받은 문자를 오름차순으로 정리한 뒤 이 중 L개의 문자를 뽑아 combination을 만든다.
• 암호 combination의 각 암호를 순회하면서 해당 암호(i.e., pw)의 모음 개수를 센다.
• 모음이 1개 이상이고 자음이 2개 이상인 조건을 만족하면 해당 pw를 문자열의 형태로 출력한다.