순열 구현

프로그래머스 스타트업 인턴 프로그램에 지원했다. 오늘 코딩 테스트가 있었는데, 그 중 순열로 풀 수 있는 문제가 있었다. 이 전에 순열 구현하는 알고리즘을 훑어보기만 했다. 다시 구현할 수 있을 줄 알았는데, 막상 긴박한 상황에 처하니, 되던것도 안되더라.

test_cases = [
	[100, 4, ['4 +1499', '1 *2', '1 *2', '1 *2', '1 *2']],
]

위와 같은 테스트 케이스가 있을 때(n, money, events) n의 가장 큰 값을 구하는 문제였다. n은 고객의 수, money는 사용 가능한 예산, events의 각 원소는 문자열로, 비용과 고객 증가율로 이루어져 있다. '4 +1499'는 이 이벤트를 실행하는데 4의 비용이 들고 고객의 수 n은 1499만큼 더해진다는 뜻이다. event는 중복될 수 없고, 순서에 따라 n의 값이 다르니 permutation으로 구현해야 한다.

⭐️ 순열(Permutation)

이전에 스크랩해뒀던 코드를 가져왔다. 참고자료에 출처가 있다.
모든 경우의 수를 출력하는 코드는 다음과 같다:

# 순열
# 중복 허용 x, 순서가 다르면 다른 경우의 수

# 4장의 카드 중에서 3장 뽑기 
card = ['A', 'B', 'C', 'D']
path = [0]*3

# used 배열 사용하여 카드 중복 사용 유무 확인
used = [0]*4

def dfs(level):
	# 3장 모두 뽑았으면 출력하고 return
    if level == 3:
        print(*path)
        return
		# 카드 4장 확인하기
    for i in range(4):
        if used[i] == 0:  # 아직 사용하지 않은 카드이면
            used[i] = 1  # 사용 체크 하고
            path[level] = card[i]  # 카드 뽑기
            dfs(level+1)  # 다음 카드 뽑으러 가기
            used[i] = 0  # 리턴 이후에는 다시 사용 체크 해제
            path[level] = 0  # 뽑은 카드 초기화

dfs(0)

백트래킹과 재귀 dfs를 사용한 알고리즘이다. level, path, used를 사용해 기록한다.

아래는 순열 알고리즘을 사용해 다시 도전한 프로그래머스 문제이다.

def solution(n, money, events):
	answer = 0
	computed = [0] * len(events)
	def dfs(level, n, money):
		nonlocal answer
		if money < 0 or level == len(events):
			return
		for i in range(len(events)):
			if not computed[i]:
				computed[i] = 1
				cost, inc = events[i].split()
				cost = int(cost)
				# sign, inc = inc[0], int(inc[1:])
				# dfs(level+1, n+inc if sign=='+' else n*inc, money-cost)
				dfs(level+1, eval(f'{n}{inc}'), money-cost)
				computed[i] = 0
				if n > answer:
					answer = n
				
	dfs(0, n, money)
	return answer
			
if __name__ == '__main__':
	test_cases = [[100, 4, ['4 +1499', '1 *2', '1 *2', '1 *2', '1 *2']],]
	for tc in test_cases:
		print(solution(*tc))   # 1600

1. 종료조건 : money가 0보다 작거나 모든 events가 다 계산되었다면 return
2. 0부터 마지막 인덱스까지 순회하며 computed에 방문표시(computed[i]=1)
3. 비용과 증가량을 더한 값을 다음 레벨 dfs로 넘기고, return되었을 때 방문 표시 해제(computed[i]=0)
4. 반드시 모든 event를 계산한다는 보장이 없으므로 그때그때 answer에 가장 큰 n 값을 기록.
5. eval 함수는 문자열을 파이썬 코드로 바꿔 실행한 값을 반환하는 함수. eval 함수 대신 주석처리한 부분을 사용해도 된다. (곱하기가 별표였는지 x였는지 기억나지 않는다. x여도 주석처리한 부분을 대신 사용한다.)
6. events의 길이는 1000까지 → 시간복잡도 $O(N^2)$으로도 충분히 풀 수 있다.

---

참고자료

1. https://velog.io/@mjieun/Python-%EC%88%9C%EC%97%B4%EC%A1%B0%ED%95%A9%EC%A4%91%EB%B3%B5%EC%88%9C%EC%97%B4%EC%A4%91%EB%B3%B5%EC%A1%B0%ED%95%A9%EB%B6%80%EB%B6%84%EC%A7%91%ED%95%A9-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-with-%EC%9E%AC%EA%B7%80