21394번 - 숫자 카드 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) (하단 참고) | 512 MB | 171 | 117 | 111 | 79.286% |
문제
Albert는 총 n장의 숫자 카드를 가지고 있다. 각 숫자 카드는 1부터 9까지의 숫자가 하나씩 적혀있고, 6과 9는 카드를 회전하면 구분할 수 없기 때문에 Albert가 임의로 회전할 수 있다.
구체적으로, xi 는 i가 적힌 숫자 카드의 개수라 하자 (따라서 x1 + x2 + ... + x9 = n 이다).
요즘 Albert는 집에서 혼자 카드 놀이를 하는데, 아래와 같은 방법으로 진행한다.
- 먼저, n장의 카드를 임의의 순서로 좌-우로 나열한다. 이 때, Albert 마음대로 6이 적힌 카드나 9가 적힌 카드는 회전할 수 있다.
- 이제 n장의 카드를 아래 규칙에 따라 한 장씩 가져와서 큰 수를 만든다.
- 처음에는 가장 좌측에 놓인 카드를 가져온다.
- 다음에는 가장 우측에 놓인 카드를 가져와서 이전에 가져온 카드 우측에 둔다.
- 이후로 계속해서 좌측과 우측에서 번갈아 카드를 가져와 그 직전에 가져온 카드 우측에 둔다.
n장의 카드를 모두 가져오고나면 길이가 n인 정수가 만들어지는데, Albert는 이 수의 값이 가장 크게 되도록 하고 싶다.
예를 들어 n = 5 이고 Albert가 가진 카드가 [6, 6, 7, 8, 9]라 하자. 아래와 같이 세 가지 다른 방법으로 다섯 장의 카드를 좌측부터 우측으로 나열한 경우, Albert가 규칙대로 게임을 진행하여 만들 수 있는 수는 아래와 같다.
- 6 6 7 8 9 순으로 나열한 경우: 가장 좌측의 6, 가장 우측의 9, 좌측에서 두 번째에 놓인 6, 우측에서 두 번째에 놓인 8, 그리고 중간에 놓인 7이 적힌 카드를 순서대로 가져와 69687 을 만들 수 있다.
- 9 9 7 8 9 순으로 나열한 경우: 가장 좌측의 9, 가장 우측의 9, 좌측에서 두 번째에 놓인 9, 우측에서 두 번째에 놓인 8, 그리고 중간에 놓인 7이 적힌 카드를 순서대로 가져와 99987 을 만들 수 있다.
- 9 7 9 8 9 순으로 나열한 경우: 가장 좌측의 9, 가장 우측의 9, 좌측에서 두 번째에 놓인 7, 우측에서 두 번째에 놓인 8, 그리고 중간에 놓인 9가 적힌 카드를 순서대로 가져와 99789 를 만들 수 있다.
- 이 예제의 경우, 99987이 Albert가 만들 수 있는 가장 큰 수 이다.
입력으로 n장의 숫자 카드가 주어졌을 때, 맨 처음 Albert가 카드를 어떻게 나열해야 가장 큰 수를 만들 수 있는지 찾아서 알려주자.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 한 줄에 총 9개의 정수가 (x1, x2, ..., x9) 공백으로 구분되어 주어진다.
출력
각 테스트 케이스에 대해 n장의 카드를 어떻게 나열해야하는지 (좌측부터 우측으로) 한 줄에 걸쳐 출력한다.
제한
- 1 ≤ T ≤ 50
- 2 ≤ n ≤ 1,000 (n = x1 + x2 + ... + x9)
- 0 ≤ xi ≤ 1,000 (1 ≤ i ≤ 9)
예제 입력 1
4 0 0 0 0 0 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 0 0 0 0 0 0 1 2 2 0 0 0 0 0 0
예제 출력 1
9 9 7 8 9 9 8 5 3 1 2 4 7 9 3 3 1 2 3 3 2 1 2 3
예제 1: 본문에서 다루었다.
예제 2: 6이 적힌 카드를 회전하여 9로 만든 후 출력에 나온 것과 마찬가지로 나열할 경우 998754321 이라는 수를 만들 수 있다.
예제 3: 추가 설명 없음
예제 4: 추가 설명 없음
시간 제한
- Java 8: 2 초
- Java 8 (OpenJDK): 2 초
- Java 11: 2 초
- Kotlin (JVM): 2 초
- Java 15: 2 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호