본문 바로가기

알고리즘

2인자 선발

Best 20 · 16번Lv. 2완전 탐색

2인자 선발

(주)캣네생선

문제 설명

(주)캣네생선을 이끌어야 할 대리인 No.1이 라이캣의 비밀 명령지를 받아 자리를 비운 후 (주)캣네생선은 명령을 내려줄 사람이 없어 업무가 마비된 상태에 이르게 됩니다. 이를 안 대리인 No.1은 대리인 No.2를 뽑기 위해 아래와 같은 문제를 출제합니다. 이 문제를 푼 사람이 앞으로 캣네생선을 운영하게 됩니다. 다음은 대리인 No.1의 문제입니다.

아스키코드로 이루어진 배열(arr)을 받으면 이에 해당하는 알파벳(로마 기호)으로 치환한 뒤, 이 요소들을 활용해 문자로 조합 가능한 경우의 수를 모두 도출합니다. 주어진 기호를 모두 한 번씩 써서 늘어놓은 로마 숫자 가운데 가장 큰 값을 반환하는 solution 함수를 작성해 주세요.

로마 기호는 숫자로 나타낼 때 다음과 같이 매칭됩니다.

로마 숫자 기호값
I1
V5
X10
L50
C100
D500
M1000

로마 숫자는 감산 표기법을 적용할 수 있습니다. 감산 표기법이란, 두 문자를 조합하여 하나의 숫자를 나타낼 때 큰 수 앞에 작은 수를 놓아 큰 수에서 작은 수를 뺀 값을 표기하는 방식입니다. 예를 들어, 4는 V - I = IV로 표시할 수 있습니다. 늘어놓은 기호는 왼쪽부터 읽으며, 바로 오른쪽 기호보다 작은 기호는 빼고 나머지는 더합니다(예: XIV = 10 - 1 + 5 = 14).


제한 사항

  • 입력받은 배열 내에는 중복되는 요소가 없습니다.
  • 1 ≤ 배열의 길이 ≤ 5
  • 1 ≤ 최댓값 ≤ 1660
  • 배열의 수는 I(73), V(86), X(88), L(76), C(67), D(68), M(77) 중 하나의 아스키코드입니다.

입출력 예

숫자 리스트결괏값
[73, 88, 86]16
[67, 86, 77, 76]1155
[68, 86, 76, 73, 88]566

입출력 설명

  • 아스키코드(숫자)의 배열을 입력받습니다.
  • 나올 수 있는 결괏값 중 최대 숫자를 반환합니다.
  • [73, 88, 86]을 로마 문자로 치환하면 [I, X, V]입니다.
  • 가장 큰 수인 X가 arr[0]에 와야 하며 [X, I, V]와 [X, V, I] 두 가지 경우로 조합할 수 있습니다.
  • 배열을 문자로 바꿨을 때 전자는 14, 후자는 16을 나타내므로 최댓값인 결과는 16입니다.

예시 테스트

#입력기대값
1[73, 88, 86]16
2[67, 86, 77, 76]1155
3[68, 86, 76, 73, 88]566

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 8개도 함께 채점해요.