[백준] 16719번 - ZOAC (Python, 파이썬)

문제

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

16719번: ZOAC

 

접근 방법

주어지는 문자열의 길이가 최대 100까지밖에 안되므로, 모든 경우의 수를 다 세는 방식으로 풀이하였다.

현재 문자 상태에서 추가하지 않은 각 문자 하나하나에 대하여 추가해서 후보군을 추리고,

그중에서 문자열이 가장 앞서는 걸 택하고 이를 반복한다.

 

상세

나는 문자열 target과 각 문자에 대한 선택 여부를 isActivate배열 2개를 두어 풀이하였다.

 

ZOAC를 예시로 들어보자. A → AC → OAC → ZOAC 순으로 선택해야 한다.

 

1단계

현재 문자열: _ _ _ _

현재 선택되지 않은 Z, O, A, C 각각에 대하여 선택한 경우를 후보군에 넣는다.

Z, O, A, C 중 A가 사전상 가장 앞서므로 A를 선택한다.

 

2단계

현재 문자열: _ _ A _

현재 선택되지 않은 Z, O, C 각각에 대하여 선택한 경우를 후보군에 넣는다.

ZA, OA, AC 중 AC가 사전상 가장 앞서므로 C를 선택한다.

 

3단계

현재문자열: _ _ A C

현재 선택되지 않은 Z, O 각각에 대하여 선택한 경우를 후보군에 넣는다.

ZAC, OAC 중 OAC가 사전상 가장 앞서므로 O를 선택한다.

 

4단계

현재 문자열: _ O A C

현재 선택되지 않은 Z 각각에 대하여 선택한 경우를 후보군에 넣는다.

ZOAC 중 ZOAC가 사전상 가장 앞서므로 Z를 선택한다.

 

코드

# ex. showActivateStr("CAT", [True, True, False])는 True에 해당하는 문자인 "CA"를 반환함
def showActivateStr(target, isActivate):
    result = ""
    for i in range(len(isActivate)):
        if isActivate[i]:
            result += target[i]
    return result

target = input()
isActivate = [False] * len(target)

for i in range(len(target)):
    # isActivate값이 False인것 하나하나에 대해서 추가했을 때의 가능한 문자열들을 모아놓고 가장 앞서는 경우를 확인
    tempResult = [] # (문자열, 그때 활성화 시킨 인덱스)
    
    for j in range(len(isActivate)):
        if isActivate[j] == False:
            isActivate[j] = True
            tempResult.append((showActivateStr(target, isActivate), j))
            isActivate[j] = False
    
    tempResult.sort() # tempResult의 가장 앞에는 (가장 앞서는 문자열, 그때 활성화 시킨 인덱스)가 될 것임
    print(tempResult[0][0])
    isActivate[tempResult[0][1]] = True

 

풀이 정보

시도 횟수: 1회

총 문제 풀이에 걸린 시간: 14분 39초