새싹프로그래머의 이야기

https://www.acmicpc.net/problem/1759

문제: 주어진 문자들을 바탕으로 만들 수 있는 조건에 부합하는 문자열을 출력하는 문제

풀이 방법: 백트래킹

풀이 코드:

import sys

l, c = map(int,sys.stdin.readline().rstrip().split(' '))

if not (3 <= l <= c <= 15):
    sys.exit(0)

vowel = ['a','e','i','o','u']

stringList = sorted(list(sys.stdin.readline().rstrip().split(' ')))
case = []
vowel_cnt = 0

def backTracking(idx):
    global vowel_cnt
    if len(case) == l:
        if vowel_cnt < 1 or len(case)-vowel_cnt < 2:    # 모음 갯수가 1보다 작거나 자음 갯수가 2보다 작으면 출력하지 않고 return
            return
        for i in range(l):  # 문자열 출력
            print(case[i], end='')
        print()
        return

    for i in range(idx,c):
        if len(case) > 0 and case[-1] >= stringList[i]:  # 영문이 역순으로 들어가지 않도록 처리
            continue
        if stringList[i] in vowel:  # 모음 갯수 count
            vowel_cnt += 1

        case.append(stringList[i])
        backTracking(idx+1)
        pop_char = case.pop()

        if pop_char in vowel:   # 모음이 빠질 경우 모음 갯수에서 1 빼줌
            vowel_cnt -= 1

backTracking(0)

풀이 설명:

문제에서 주어진 조건은 다음과 같습니다.

1) 문자열은 오름차순으로 구성되어야 한다.

2) 최소 1개의 모음과 2개의 자음을 포함하고 있어야 한다.

즉, 문제의 핵심은 백트래킹 기법과 주어진 조건을 어떻게 만족시키느냐 입니다.

vowel = ['a','e','i','o','u']

def backTracking(idx):
    global vowel_cnt
    if len(case) == l:
        if vowel_cnt < 1 or len(case)-vowel_cnt < 2:    # 모음 갯수가 1보다 작거나 자음 갯수가 2보다 작으면 출력하지 않고 return
            return
        for i in range(l):  # 문자열 출력
            print(case[i], end='')
        print()
        return

    for i in range(idx,c):
        if len(case) > 0 and case[-1] >= stringList[i]:  # 영문이 역순으로 들어가지 않도록 처리
            continue
        if stringList[i] in vowel:  # 모음 갯수 count
            vowel_cnt += 1

        case.append(stringList[i])
        backTracking(idx+1)
        pop_char = case.pop()

        if pop_char in vowel:   # 모음이 빠질 경우 모음 갯수에서 1 빼줌
            vowel_cnt -= 1

코드를 보시면 먼저 모음을 담고 있는 array를 만들어 준 후, 백트래킹 함수를 구현하였습니다.

최종 출력할 문자들을 담고 있는 case라는 배열에 값을 넣어줄 때마다, 들어가는 문자가 모음인지 확인하여 모음의 갯수를 세어주었습니다.

영어는 자음 + 모음이므로 출력할 총 문자의 갯수에서 담긴 모음의 갯수를 빼주면 자음의 갯수가 나오므로 이를 활용하였습니다.

이를 바탕으로 최종 출력하기 전, 문제에서 주어진 조건이 부합하는지를 확인하고 조건에 부합하는 문자열만 출력하도록 구현하였습니다.