[SWEA] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금 D3 JAVA (자바) 풀이

문제 1244. 최대 상금 (백트래킹)

 

 :  보너스 상금 만들기

 :  숫자판들 중에 두 개를 선택해 위치 교환



 교환전 >

 

 

 

[입력]

 

숫자판 : 정수형 숫자

 

최대 자릿수는 6자리, 최대 교환 횟수는 10번

 

[출력]

각 테스트 케이스마다, 첫 줄에는 “#C”를 출력해야 하는데 C는 케이스 번호이다.

같은 줄에 빈 칸을 하나 사이에 두고 교환 후 받을 수 있는 가장 큰 금액을 출력한다.

 

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹

 

 종료 조건) 교횐 횟수가 채워지면 result에 저장하고 다음 백트래킹 시작

 

 예) 교환횟수 = 2라 할 때

• depth = arr의 길이만큼
• 종료 : count = 2
  • 현재값 이전값 비교해서 크면
• 백트래킹(0,0) / depth = 0 
• 교환 노드 1 : arr[0]
• 교환 노드 2 : arr[1]
• 백트래킹(0,1) / depth = 0
  • 교환노드 

 

 

 [함수 1] String.toCharArray()

 

• String(문자열)을 한 글자씩 쪼개서 char형 배열에 집어넣어주는 친절한 메소드
  
  String s1 = "Hello World";
  char[] charArr = s1.toCharArray();
  

 

 [함수 2] 기준값.compareTo(비교값);

• 숫자비교
  • 기준값 == 비교값 : 0 반환
  • 기준값 > 비교값 : 1 반환
  • 기준값 < 비교값 : -1 반환
    
    

• 문자비교
  
  • 같으면 : 0 반환
  • 다르면 : 다른 문자의 개수만큼 리턴
    • 양수 : 기준이 사전순으로 더 뒤에 있다 = 아스키코드 더 크다
    • 음수 : 기준이 사전순으로 더 앞에 있다 = 아스키코드 더 작다

 

백트래킹

• 2중 for문 안에서 백트래킹 호출로 다시 한 번 겹쳐서 백트래킹이 시작될 때
  초기화된 조건이 아니라 이전 이중 for문의 조건을 그대로 수용한다
  
  
• 백트래킹 메서드 예제
  
  for(int i=depth; i<arr.length;i++){
             for(int j =i+1; j<arr.length; j++){
                 change(i, j);
                 back(i, count+1);
                 change(i,j);
             }
  }
  
  초기시작 : back(0,0) → i = 0, j = 0
  백트래킹 호출 : back(0,1) → i = 0, j = 1
  
  이때 이전 이중 for문에서 j++ 했으므로 다시 백트래킹이 시작된다고 하더라도 i = 0, j = 0 부터 시작하는게 아니라 이전 조건들을 이어서 j = 1인 상태로 시작한다

 

 

 [코드]

import java.util.*;
import java.io.*;

class Solution
{
    static char arr[];
    static int n;
    static String result;
	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
		int T = Integer.parseInt(br.readLine());
	
        StringTokenizer st;
		for(int test_case = 1; test_case <= T; test_case++)
		{
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
            arr = s.toCharArray();  
           
            n = Integer.parseInt(st.nextToken());
            
             result = ""; 
            back(0,0);
            System.out.println("#"+test_case+" "+ result);
        }
	}
    
    public static void back(int depth, int count){
        
       if(count==n){
            String current = new String(arr); 
            if (current.compareTo(result) > 0) {  
                result = current;  
            }
           return;
       }
        
       for(int i=depth; i<arr.length;i++){
           for(int j =i+1; j<arr.length; j++){
               change(i, j);
               back(i, count+1);
               change(i,j);
           }
       }
    }
    
    private static void change(int i, int j){
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

 

 [해설]
     

 :  static char arr[];  숫자집합
    static int n;  교환횟수
    static String result;  출력

 

 :  int T = Integer.parseInt(br.readLine());

 :  StringTokenizer st;
    for(int test_case = 1; test_case <= T; test_case++)
   {
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
            arr = s.toCharArray();  
           
            n = Integer.parseInt(st.nextToken());
            
            result = "";  보통은 result = 0으로 초기화 / but 이번 출력은 문자열이라 ""으로 초기화
            back(0,0);  깊이, 교환횟수 카운트
            System.out.println("#"+test_case+" "+ result);  출력
   }

    
 :  public static void back(int depth, int count){  백트래킹 시작
        
       if(count==n){  종료 조건 = 교환 다 했음 종료
            String current = new String(arr);  백트래킹 돌려서 만든 현재 문자 배열 상태를 문자열로 변환
            if (current.compareTo(result) > 0) {  현재값이 이전 값과 비교했을 때 더 크면
                result = current; 더 큰 값으로 result 업데이트
            }
           return; 
       }
        
       for(int i=depth; i<arr.length;i++){
           for(int j =i+1; j<arr.length; j++){
               change(i, j);  change메서드 통해서 문자 교환하기
               back(i, count+1);  재귀 다시 깊이 호출
               change(i,j);  다시 이전으로 되돌리기 (if문 종료한 다음)
           }
       }
    }
    
    private static void change(int i, int j){  문자 교환하기
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
  

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD

SW Expert Academy

 

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *