[백준 1759] 암호 만들기 (C#, C++) - soo:bak

작성일 :

문제 링크https://soo-bak.github.io/algorithm/boj/passwordGen-44/#문제-링크

1759번 - 암호 만들기

설명https://soo-bak.github.io/algorithm/boj/passwordGen-44/#설명

이 문제는 주어진 알파벳 중에서 L개의 문자를 선택하여,
최소 1개의 모음과 최소 2개의 자음을 포함하고
사전 순으로 증가하는 암호들을 전부 출력하는 문제입니다.

접근법https://soo-bak.github.io/algorithm/boj/passwordGen-44/#접근법

  • 백트래킹(DFS)을 사용하여 가능한 조합을 모두 탐색합니다.
  • 현재 선택된 문자 수가 L과 같아지면, 모음과 자음 개수를 검사합니다.
  • 조건을 만족하는 조합만 출력하며, 사전 순 출력을 위해 알파벳을 정렬한 후 탐색을 시작합니다.
  • 각 단계에서는 현재 인덱스보다 큰 인덱스만 탐색하여 중복 없이 증가하는 순서를 유지합니다.

Codehttps://soo-bak.github.io/algorithm/boj/passwordGen-44/#code

[ C# ] 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

using System;
using System.Collections.Generic;
using System.Linq;

namespace Solution {
  class Program {
    static int l, c;
    static List<char> alpha = new();
    static readonly HashSet<char> vowels = new() { 'a', 'e', 'i', 'o', 'u' };

    static void Main(string[] args) {
      var input = Console.ReadLine()!.Split().Select(int.Parse).ToArray();
      l = input[0]; c = input[1];

      alpha = Console.ReadLine()!.Split().Select(char.Parse).ToList();
      alpha.Sort();

      for (int i = 0; i <= c - l; i++)
        Dfs(alpha[i].ToString(), i, 1);
    }

    static void Dfs(string pwd, int idx, int depth) {
      if (depth == l) {
        int cntV = pwd.Count(ch => vowels.Contains(ch));
        int cntC = pwd.Length - cntV;
        if (cntV >= 1 && cntC >= 2)
          Console.WriteLine(pwd);
        return;
      }

      for (int i = idx + 1; i <= c - (l - depth); i++)
        Dfs(pwd + alpha[i], i, depth + 1);
    }
  }
}



[ C++ ] 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <bits/stdc++.h>

using namespace std;

int lenPwd, numApb;
vector<char> alpha;

bool isVowel(const char& c) {
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' ||
      c == 'u') return true;
  return false;
}

void dfs(string pwd, int now, int depth) {
  if (depth == lenPwd) {
    int cntV = 0, cntC = 0;
    for (int i = 0; i < lenPwd; i++) {
      if (isVowel(pwd[i])) cntV++;
      else cntC++;
    }
    if (cntV >= 1 && cntC >= 2) cout << pwd + "\n";
    return ;
  }

  for (int i = now + 1; i <= numApb - lenPwd + depth; i++)
    dfs(pwd + alpha[i], i, depth + 1);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> lenPwd >> numApb;
  for (int i = 0; i < numApb; i++) {
    char input; cin >> input;
    alpha.push_back(input);
  }

  sort(alpha.begin(), alpha.end());

  string pwd = "";
  for (int i = 0; i <= numApb - lenPwd; i++)
    dfs(pwd + alpha[i], i, 1);

  return 0;
}

이 블로그의 다른 글