섹션3 브루트포스 알고리즘 1342 풀이1 질문

Question

섹션3 브루트포스 알고리즘 1342 문제 풀이 강의에서

풀이1 질문이 있습니다.

for i in range(ord('a'), ord('z') + 1) :
    ans //= fact(S.count(chr(i)))

이렇게 fact로 나눠주라고 하셨는데,

왜 나눠주는 지 이해가 잘 안됩니다.

같은 문자가 있을 때 나눠주는 건 알고있습니다.

근데 그건 경우의 수를 구할 때고,

이건 인접한 문자가 같은 지 아닌 지를 구하는 건데

왜 나눠줘야 하나요?

알리 Ally · Answer

안녕하세요, kimgguggury1002님! 인접한 문자가 같은 지 아닌 지를 구하는 부분 은 아래의 코드입니다. for perm in permutations(S): ok = True for i in range(0, len(S) - 1): if perm[i] == perm[i + 1]: ok = False break ans += ok   위의 과정을 거치면 ans 는 중복된 문자열을 고려하지 않고 문제의 조건을 만족하는 문자열의 개수 가 담겨 있습니다. 중복된 문자열을 고려하지 않고 경우의 수를 구했으니 중복된 문자열을 고려해야 하며, 이를 처리하는 부분이 질문자님께서 올려주신 코드 부분입니다. 중복된 문자열을 고려하여 처리하는 방법은 같은 것이 있는 순열의 개념을 이용 하면 되며, 이러한 내용은 해당 강의의 2:10 - 4:02 부분에서 설명하고 있으니 참고하시면 될 것 같습니다!   질문에 대해 만족스러운 답변이 되었기를 바랍니다! 추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. kimgguggury1002님.

질문하신 내용은 백준 1342번 문제를 풀면서 ‘행운의 문자열’을 계산하는 부분에서 페르마법칙을 적용하여 중복을 제거하는 방법에 관한 것입니다. 각 문자의 빈도수에 해당하는 패턴이 반복될 수 있을 때, 그 중복된 경우의 수를 나누어 제거해야 합니다. 이는 같은 알파벳의 배열 방법이 많기 때문에, 중복된 패턴을 없애기 위한 과정입니다.

다시 말해, S.count(chr(i))는 특정 문자의 개수를 의미하고, fact는 해당 문자의 개수로 나타낼 수 있는 모든 순열의 경우의 수를 뜻합니다. 이렇게 나눠주는 이유는 각 문자별 중복을 제거하여 중복된 배열 방법을 줄이기 위함입니다.

유사한 질의와 관련된 답변을 확인하고자 한다면, 브루토 포스 백준 1342 질문을 참고해 보세요. 이 답변에서는 연속된 문자를 포함하지 않는 문자열을 생성하는 방식을 설명하고 있으며, 특히 중복과 관련된 시간 복잡도 및 효율성을 설명하고 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

섹션3 브루트포스 알고리즘 1342 풀이1 질문