인프런 커뮤니티 질문&답변
작성한 질문수
BOJ 1759 문제 오답이 생기는데, 어느 부분이 틀리는 것인지 설명 부탁드립니다.
해결된 질문
작성
·
80
·
수정됨
0
안녕하세요, 좋은 강의 만들어주셔서 감사합니다.
'조합 알고리즘' 부분 진도 나가고 있는데, 다음과 같이 시도했더니 오답이 떴습니다.
아예 처음부터 L개의 원소를 뽑아 조합을 만든 다음,
모음과 자음의 갯수가 미달되면 해당 조합은 지우는 방식으로 시도해봤는데,
(for문이 세개나 나와서 좀 조잡한 풀이 같아 보이긴 하지만..ㅠㅠ)
이 풀이가 틀리게 되는 이유를 혼자 힘으론 찾기가 어려워서 도움을 구해봅니다...!
from itertools import combinations
L, C = input().split()
chars = list(input().split())
mo = ['a', 'e', 'i', 'o', 'u']
candidates = list(combinations(chars, int(L)))
for can in candidates:
mo_num, ja_num = 0, 0
for i in can:
if i in mo:
mo_num += 1
else:
ja_num += 1
if mo_num < 1 or ja_num < 2:
candidates.remove(can)
sol = []
for ans in candidates:
ans_str = ''
for i in sorted(ans):
ans_str += i
sol.append(ans_str)
for i in sorted(sol):
print(i)답변 2
1
안녕하세요. 황지은님!
첨부해주신 코드를 보았을 때, 논리적으로는 문제는 없어보입니다.
다만 구현에 있어서 문제가 될 수 있는 부분과 비효율적인 부분이 있습니다.
문제가 되는 부분) 리스트 순회 중 요소 제거
첫 번째 for문을 보면 리스트를 순회하면서, 조건을 만족하지 않는 경우 순회하는 리스트의 요소를 직접 참조해서 지우고 있습니다.
리스트를 순회하면서 요소를 제거하는 것은 특정 요소가 건너뛰어지는 등의 여러 예기치 못한 버그를 유발할 수 있는데요.
공유 주신 코드의 풀이가 틀린 이유가 바로 이 부분 때문입니다.
순회 중인 리스트의 요소를 직접 제거하는 것이 아닌, candidates와 동일한 요소들로 구성된 리스트를 만들어 해당 리스트 내에서 조건에 만족하지 않는 요소들을 제거해주는 방법으로 구현해주셔야 합니다.
더 좋은 방법은 아예 새로운 빈 리스트를 만들고, candidates에서 조건을 만족하는 요소들만 넣어주시는 방법으로 구현해주셔도 됩니다.
비효율적인 부분) 최종 출력 문자열 생성 및 정렬 방식의 문제
마지막 for문을 돌며 최종 문자열을 만드는 과정에서 sorted가 여러 번 반복되고 있습니다.
candidates의 모든 문자열에 대해서 sorted가 반복되고 있기 때문에 효율성 측면에선 좋지 않을 수 있습니다.이 방법 보다는 강의에서 언급드린 방법대로 미리 요소들을 정렬한 후 조합을 뽑는 방법으로 수정해주시면 더 좋은 풀이가 될 것 같습니다.
위 두 문제를 개선한 코드도 함께 첨부드립니다.
from itertools import combinations
L, C = map(int, input().split())
chars = input().split()
mo = {'a', 'e', 'i', 'o', 'u'}
candidates = list(combinations(sorted(chars), L))
valid_candidates = []
for can in candidates:
mo_num, ja_num = 0, 0
for i in can:
if i in mo:
mo_num += 1
else:
ja_num += 1
if mo_num >= 1 and ja_num >= 2:
valid_candidates.append(''.join(can))
for ans in valid_candidates:
print(ans)
또 궁금하신 점 있으시면 언제든 질문 부탁드립니다.
감사합니다. :)
1
안녕하세요, 인프런 AI 인턴입니다.
님의 질문에 대한 답변입니다. 제시하신 코드에서 오답이 나오는 이유 중 하나는 candidates 리스트에서 반복문을 돌면서 해당 조합을 삭제하는 과정에 있습니다. Python에서 리스트를 순회하면서 해당 리스트의 항목을 삭제하게 되면, 리스트의 인덱싱이 변경되어 예상치 못한 결과를 초래할 수 있습니다. 즉, 리스트를 순회하면서 그 리스트의 항목을 삭제하는 것은 좋지 않은 방법입니다.
이를 해결하기 위한 한 가지 방법은, 대신 새로운 리스트에 조건을 만족하는 조합만 추가하는 것입니다. 아래는 수정된 코드의 일부입니다.
valid_candidates = []
for can in candidates:
mo_num, ja_num = 0, 0
for i in can:
if i in mo:
mo_num += 1
else:
ja_num += 1
if mo_num >= 1 and ja_num >= 2:
valid_candidates.append(can)
이렇게 하면 조건을 만족하는 조합만 valid_candidates 리스트에 추가되고, 원본 리스트 candidates를 변경할 필요 없이 문제를 해결할 수 있습니다.
또한, 이 문제에서는 출력을 위해 조합을 사전 순으로 정렬해야 합니다. 기존 코드에서는 각 조합을 정렬하여 문자열로 합치기 전에 전체 조합 리스트를 정렬하는 것이 아니라, 각 조합을 문자열로 변환한 후 최종 결과를 출력하기 직전에 정렬하였습니다. 이는 올바른 접근입니다.
해당 문제를 해결하는 데 도움이 되었기를 바랍니다. 추가적인 질문이 있으시면 언제든지 문의해주세요!