[SWEA / Java] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금

문제 링크

SWEA/D3/1244. ［S／W 문제해결 응용］ 2일차 － 최대 상금/［S／W 문제해결 응용］ 2일차 － 최대 상금.java

• 배열의 교환을 통해 → 배열의 원소를 쭉 나열했을 때 수가 최대가 되도록!

문제 설명

---

💡 Info

• 난이도 : D3
• 시간 제한 : 15개 테스트케이스를 합쳐서 Java의 경우 20초
• 메모리 제한 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

내용

퀴즈 대회에 참가해서 우승을 하게 되면 보너스 상금을 획득할 수 있는 기회를 부여받는다.

우승자는 주어진 숫자판들 중에 두 개를 선택해서 정해진 횟수만큼 서로의 자리를 위치를 교환할 수 있다.

예를 들어, 다음 그림과 3, 2, 8, 8, 8 의 5개의 숫자판들이 주어지고 교환 횟수는 2회라고 하자.

• 교환 전
  

처음에는 첫 번째 숫자판의 3과 네 번째 숫자판의 8을 교환해서 8, 2, 8, 3, 8이 되었다.

다음으로, 두 번째 숫자판 2와 마지막에 있는 8을 교환해서 8, 8, 8, 3, 2이 되었다.

정해진 횟수만큼 교환이 끝나면 숫자판의 위치에 부여된 가중치에 의해 상금이 계산된다.

숫자판의 오른쪽 끝에서부터 1원이고 왼쪽으로 한 자리씩 갈수록 10의 배수만큼 커진다.

위의 예에서와 같이 최종적으로 숫자판들이 8, 8, 8, 3, 2의 순서가 되면 88832원의 보너스 상금을 획득한다.

여기서 주의할 것은 반드시 횟수만큼 교환이 이루어져야 하고 동일한 위치의 교환이 중복되어도 된다.

다음과 같은 경우, 1회의 교환 횟수가 주어졌을 때 반드시 1회 교환을 수행하므로 결과값은 49가 된다.

94의 경우, 2회 교환하게 되면 원래의 94가 된다.

정해진 횟수만큼 숫자판을 교환했을 때 받을 수 있는 가장 큰 금액을 계산해보자.

📥입력 조건

• 가장 첫 줄은 전체 테스트 케이스의 수이다.
• 최대 10개의 테스트 케이스가 표준 입력을 통하여 주어진다.
• 각 테스트 케이스에는 숫자판의 정보와 교환 횟수가 주어진다.
• 숫자판의 정보는 정수형 숫자로 주어지고 최대 자릿수는 6자리이며, 최대 교환 횟수는 10번이다.

  3
  123 1
  2737 1
  32888 2
  ...

📤출력 조건

• 각 테스트 케이스마다, 첫 줄에는 “#C”를 출력해야 하는데 C는 케이스 번호이다.
• 같은 줄에 빈칸을 하나 사이에 두고 교환 후 받을 수 있는 가장 큰 금액을 출력한다.

  #1 321
  #2 7732
  #3 88832
  ...

문제 이해

---

• 주어지는 숫자판과 교환 횟수를 통해 숫자를 최대로 만들기

알고리즘

---

실제 풀이 시간 : 60분

• 선언
  • 숫자판 정보 배열 arr 선언하기(최대 6자리)
  • 교환 횟수 N 선언하기(최대 10번)
  • 최대 숫자 결과값인 result 선언하기
  • 임시 배열 temp 선언하기
• 입력
  • 테스트 케이스 수 T 입력받기
  • 숫자판 정보 배열 arr 입력받기(최대 6자리)
  • 교환 횟수 N 입력받기(최대 10번)
• 계산
  • 배열을 내림차순 정렬하기(실제 정렬 함수를 쓰는 것이 아님)
    • for문 : N 이하까지만 진행하도록 하기
      • if문 : 앞에서부터 2개씩만 수를 비교하며 arr[i] < arr[i+1]이라면
      • 교환 진행
        • arr[i] = temp[i]; temp[i] = arr[i+1]; arr[i+1] = arr[i];
          
• 출력
  • 최대 숫자인 result 출력하기

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
	
	static int[] arr;
	static int N;
	static int result = 0;
	
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T=sc.nextInt();
	
	
		for(int test_case = 1; test_case <= T; test_case++)
		{
	
			// 1. 숫자판 정보 arr 및 교환 횟수 N 입력받기
			arr = new int[6];
			for(int i=0; i<6; i++) {
				arr[i] = sc.nextInt();
			}
			
			N = sc.nextInt();
			
			
			//2. 계산 : 배열 교환 계산하기
			for(int i=0; i<N; i++) {
				if(arr[i] < arr[i+1]) {
					int temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
				}
				result = arr[i];
			}
			
			//3. 교환 결과값 출력하기
			System.out.println("#" + test_case + " " + result);
		}
	}
}

오답 체크

---

• 입력이 끝났음에도, 계속해서 입력을 받는 문제 발생
  • 이를 수정하더라도 답안이 완전히 다르게 나옴.
• DFS를 적용해 이를 해결
  • 배열의 값을 교환하는 아이디어는 좋았으나, 이를 dfs를 활용해야 한다는 점을 알지 못했음.
  • max = Math.max(max, result);
    • 현재의 최대 숫자와 계산한 숫자를 비교해 두 값 중 더 큰 값을 max에 갱신하는 역할
  • 기존의 교환 알고리즘(for문)을 DFS 연산 내부에 넣음.
    • 또한, i와 j 중첩 for문을 사용
      • i = start = 확인하려는 숫자(이전의 arr[i] 역할)
      • j = i+1 = i 바로 다음에 오는 숫자(이전 코드의 arr[i+1] 역할)
    • 교환 완료 후 dfs를 증가
      • 그런 다음, 배열을 처음 상태로 초기화 해준 다음 처음으로 돌아가 다시 교환을 해야 함!

최종 풀이

---

실제 풀이 시간 : 1시간 30분(첫 풀이 시간 포함)

• 선언
  • 숫자판 정보 배열 arr 선언하기(최대 6자리)
  • 교환 횟수 N 선언하기(최대 10번)
  • 최대 숫자 결과값인 max 선언하기
• 입력
  • 테스트 케이스 수 T 입력받기
  • 숫자판 정보 배열 arr 입력받기(최대 6자리)
    • 이 배열은 int형을 String형으로 변환하는 과정이 필요함.
  • 교환 횟수 N 입력받기(최대 10번)
• 시간 초과 해결
  • arr.length가 교환 횟수 N보다 작은 경우에는 N=arr.length가 될 수 있도록 해 최적화
• 계산
  • dfs 진행
• 출력
  • 최대 숫자인 max 출력하기
• 별도 메서드
  • dfs
    • dfs의 count가 교환 횟수 N과 같을 때, 현재의 최대 숫자와 계산한 숫자를 비교해 두 값 중 더 큰 값을 max에 갱신
    • 숫자 교환하기
      • for문 : i는 start 부터 N 이하(즉, arr.length)까지만
        • for문 : j는 i+1(i 다음 수)부터 N 이하(즉, arr.length)까지만
        • 교환 진행
          • temp = arr[i]; arr[i] = arr[j]; arr[i+1] = arr[i];
            
        • 다음 dfs 진행을 위해 count를 1 증가
        • i와 j의 교환이 종료되고, 다시 새롭게 교환을 처음부터 하기 위해 다시 처음으로 교환하기!!

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
	
	static int[] arr;
	static int N;
	static int max;
	
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T=sc.nextInt();
	
	
		for(int test_case = 1; test_case <= T; test_case++)
		{
	
			// 1. 숫자판 정보 arr 및 교환 횟수 N 입력받기
			String num = sc.next();
			arr = new int[num.length()];
            for (int i = 0; i < num.length(); i++) {
                arr[i] = num.charAt(i) - '0';
            }
			
			N = sc.nextInt();
			
			max = 0;
			
			if(arr.length < N) {
            	N = arr.length;
      }
			
			dfs(0,0);
			
			//3. 교환 결과값 출력하기
			System.out.println("#" + test_case + " " + max);
		}
	}
	
	static void dfs(int start, int count){
        if(count == N) {
        	int result = 0;
        	for(int s : arr) {
        		result = result*10 + s;
        	}
        	max = Math.max(max, result);
        	return;
        }
   
        //2. 계산 : 배열 교환 계산하기
				for(int i = start; i < arr.length; i++) {
					for(int j = i+1; j < arr.length; j++) {
						int temp = arr[i];
		        arr[i] = arr[j];
		        arr[j] = temp;
		                
		        dfs(i, count+1);
		                
		        temp = arr[i];
		        arr[i] = arr[j];
			      arr[j] = temp;  
			}
		}
	}
}