백준 10819(차이를 최대로)- Python(파이썬),Java(자바) - 구현,브루트포스(Permutations,Combinations,백트래킹,Java- 스택 사용 )

10819번: 차이를 최대로

 

예제 설명

일단 배열 A를 오름차순으로 정렬한다. 

인덱스	0	1	2	3	4	5
배열	1	4	8	10	15	20

인덱스의 차이가 최대이기 위해서는 고른 인덱스와 선택하지 않은 배열 중 제일 먼 인덱스를 골라야한다.

ex ] 0고르기 -> 5고르기 -> 1고르기 -> 4고르기 -> 2고르기 -> 3고르기

하지만 마지막에 2를 고르고 3을 고르는 것보다 인덱스 3을 제일 앞에 두는 것이 더 차이의 합이 커진다

ex ] 3고르기 -> 0고르기 -> 5고르기 -> 1고르기 -> 4고르기 -> 2고르기

1. 처음 인덱스가 0인 경우
   

   인덱스	3	0	5	1	4	2	차이의 합
   인덱스의 값	10	1	20	4	15	8	9+19+16 +11+7=62

2. 처음 인덱스가 5인 경우

   인덱스	2	5	0	4	1	3	차이의 합
   인덱스의 값	8	20	1	15	4	10	12+19+14 +11+6=62

이런식으로 둘이 비교하였을 때 최대인 값이 차이의 합이 최대인 62가 나오게 되었다.

 

N = 6

   1. 처음 인덱스가 0인 경우

    이 때 고른 인덱스의 경우를 나열하면 ( 3, 0 ), ( 0, 5), ( 5,1 ),  ( 1, 4 ), ( 4, 2 ) 이렇게 다섯가지이다. 이 경우를 분류하면

    ① 인덱스의 합  5(N-1)인 경우 : ( 0, 5 ) ( 1, 4 ) 

    i = 0 -> a[ 5-0 ] - a[ 0 ] 

    i = 1 -> a [ 5-1 ] - a[ 1 ]

    i = 5//2 = 2 -> ( N-1 )을 2로 나눈 몫 전까지 수행

    ② 인덱스의 합 6(N)인 경우 : ( 5,1 ) ( 4,2 ) 

    i = 1 -> a[ 6-1 ] - a[ 1 ]

    i = 2 -> a [ 6-2 ] - a[ 2 ]

    i = 6//2 = 3 -> ( N)을 2로 나눈 몫 전까지 수행

    ③ 예외 : ( 3,0 ) -> 둘의 차이가 3( N//2 )

    : a[n//2] - a[0]

   

   2. 처음 인덱스가 5인 경우

   이 때 고른 인덱스의 경우를 나열하면 ( 2,5 ), ( 5, 0 ), ( 0, 4 ), ( 4, 1 ), ( 1, 3 )이렇게 다섯가지이다. 이 경우를 분류하면

    ① 인덱스의 합  5(N-1)인 경우 : ( 5, 0 ) ( 4, 1 )

    i = 0 -> a[ 5-0 ] - a[ 0 ] 

    i = 1 -> a [ 5-1 ] - a[ 1 ]

    i = 5//2 = 2 -> ( N-1 )을 2로 나눈 몫 전까지 수행

    ② 인덱스의 합 4(N -2)인 경우 : ( 0, 4 ) ( 1, 3 )

    i = 0 -> a[ 4-1 ] - a[ 1 ]

    i = 1 -> a [ 4-2 ] - a[ 2 ]

    i = 4//2 = 2 -> ( N-2 )를 2로 나눈 몫 전까지 수행

    ③ 예외 : ( 2,5 ) -> 둘의 차이가 3( N//2 )

   : a[n-1] - a[n-1 - n//2]

=> ①은 공통이고 ②+③의 최대의 값을 찾아서 sum을 구하면 된다.

---

문제풀이

① 인덱스의 합이 N-1인경우 : 0부터 시작해서 (N-1)//2 전까지 for문으로 a 배열의 차이( a[ n-1 -i ] - a[ i ] )를 더하기
② 인덱스의 합이 N인 경우 : 1부터 시작해서 N//2전까지 for문으로 a배열의 차이( a[n-i] - a[i] )를 더하기
   + ( a[ n// 2 ] - a[ 0 ] ) 
③ 인덱스의 합이 N-2인 경우 : 0부터 시작해서 (N-2)//2전까지 for문으로 a배열의 차이( a[ n-2-i ] - a[ i ] )를 더하기
   + ( a[n-1] - a[ n-1 - n//2 ] )
④ ②,③의 경우를 비교하여서 큰 값을 ①을 더하기 

💻Python(파이썬)

import sys
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
#정렬
a.sort()
sum=num1=num2 =0
#1.인덱스의 합이 N-1인 경우
for i in range((n-1)//2):
    sum+=a[n-1-i]-a[i]
#2.인덱스의 합이 합이 N인 경우
for i in range(1,n//2):
    num1 += a[n-i]-a[i]
num1 += a[n//2]-a[0]
#3.인덱스의 합이 N-2인 경우
for i in range(1,(n-2)//2):
    num2 += a[n-2-i]-a[i]
num2 += a[n-1]-a[n-1-n//2]
#2번과 3번 비교
if num1>num2:
    sum+=num1
else:
    sum+=num2

print(sum)

💻 Java(자바)

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[] a = new int[n];
        for(int i=0;i<n;i++){
            a[i]=Integer.parseInt(st.nextToken());
        }
        Arrays.sort(a);
        int sum =0;
        for(int i=0;i<(n-1)/2;i++){
            sum+=a[n-1-i]-a[i];
        }
        int num1=0,num2=0;
        for(int i=1;i<n/2;i++){
            num1 += a[n-i]-a[i];
        }
        num1 += a[n/2]-a[0];
        for(int i=0;i<(n-2)/2;i++){
            num2+= a[n-2-i]-a[i];
        }
        num2 += a[n-1]-a[n-1-n/2];
        if(num1>num2){
            sum+=num1;
        }else{
            sum+=num2;
        }
        System.out.println(sum);
    }
}

---

📌 파이썬 Permutation 사용 

 Python( 파이썬 )

참고 자료 : https://velog.io/@dramatic/Python-permutation-combination-순열과-조합

  📖 permutations : 순열 라이브러리(nPr)

- 서로 다른 n개 중에서 r개를 골라 순서를 나열하는 가짓수

from itertools import permutations

arr = [ 'A', 'B', 'C' ]
#('A', 'B', 'C') ('A', 'C', 'B') ('B', 'A', 'C') ('B', 'C', 'A') ('C', 'A', 'B') ('C', 'B', 'A')
nP3 = permutations(arr) #arr의 가짓수
#('A', 'B') ('A', 'C') ('B', 'A') ('B', 'C') ('C', 'A') ('C', 'B')
nP2 = permutations(arr,2) #arr에서 2개의 원소를 골라 나열하는 가짓수
#('A')('B')('C')
nP1 = permutations(arr,1) #arr에서 1개의 원소를 골라 나열하는 가짓수

  📖 combinations : 조합 라이브러리(nCr)

- 서로 다른 n개 중에서 r개를 뽑는 경우의 수

- 조합의 경우는 순서를 신경쓰지 않고 누구를 뽑았는지 중요

from itertools import combinations

arr = [ 'A', 'B', 'C' ]
#('A', 'B', 'C')
nC3 = combinations(arr,3) #arr의 가짓수
#('A', 'B') ('A', 'C') ('B', 'C')
nC2 = combinations(arr,2) #arr에서 2개의 원소를 고르는 가짓수
#('A')('B')('C')
nC1 = combinations(arr,1) #arr에서 1개의 원소를 고르는 가짓수
for i in nC3:
    print(i,end=" ")
for i in nC2:
    print(i,end=" ")
for i in nC1:
    print(i,end=" ")

---

문제 풀이

① 배열이 나열 될 수 있는 전체 가짓수 n!를 저장
② 입력 받은 배열을 하나씩 차이의 sum 값을 계산하고 전에 구한 값보다 지금 구한 sum값이 클 경우 변경
③ 최종 최댓값 출력 

💻 Python(파이썬) - Permutation 라이브러리 사용

import sys
#순열
from itertools import permutations

n = int(sys.stdin.readline())
array = list(map(int,sys.stdin.readline().split()))

#배열의 가짓수
nPr = permutations(array)
#가장 큰 배열 초기화
max_sum=0
#배열마다 하나씩 실행 
for arr in nPr:
    sum=0
    #배열 하나마다 차이의 sum 값 구하기
    for j in range(len(arr)-1):
        sum+=abs(arr[j]-arr[j+1])
    #만약 전에 구한 값보다 지금 구한 sum이 크면
    if max_sum<sum:
        max_sum = sum

print(max_sum)

---

📌  Permutation 사용하지 않고 백트래킹으로 구하기

문제 풀이

① 백트래킹 함수(x) 함수를 구현
   - temp : 인덱스 숫자를 담는 배열 ( ex. [0 1 2 3] -> 0,1,2,3 인덱스 )
   - x : 백트래킹 함수의 인수로 temp에 담긴 개수는 x을 의미
   - if x==n 은 temp에 모든 숫자가 담겼다는 의미로 배열[temp의 숫자]를 for문으로 돌려서 차이의 합을 구해야한다
     이 값이 전에 값이랑 비교해서 큰 경우 답에 적기

백트래킹은 이해가 되었는데 코드를 봤더니 이해가 되지 않아서 코드 하는 방법을 좀 적어보았다.

 

부연 설명 펼쳐보기

 1. sol[0]를 실행해서 [0]을 집어넣고 pop을 하기 전에 재귀함수를 호출해서 sol[0+1]를 호출

2. sol[1]를 실행해서 [0 1]을 집어넣고 pop을 하기 전에 재귀함수를 호출해서 sol[1+1]를 호출

 

3. sol[2]를 실행해서 [0 1 2]을 집어넣고 pop을 하기 전에 재귀함수를 호출해서 sol[2+1]를 호출

4.sol[3]를 실행해서 [0 1 2 3]을 집어넣고 pop하기 전에 재귀함수를 호출해서 백트래킹 함수(sol[3+1])를 호출

 

5.sol[4]를 실행해서 [0 1 2 3 4]을 집어넣고 pop하기 전에 재귀함수를 호출해서 백트래킹 함수(sol[4+1])를 호출

 

6.sol[5]를 실행해서 [0 1 2 3 4 5]을 집어넣고 pop하기 전에 재귀함수를 호출해서 백트래킹 함수(sol[5+1])를 호출

7.sol[6]을 실행하는데 6==N이랑 동일하므로 if문 실행해서 차이를 구하고 종료 -> sol[5]의 pop 하러 가기

8. sol[5] pop을 하였기에 [0 1 2 3 4]하고 종료 -> sol[4]의 pop하러가기

9.sol[4]의 pop을 하였기에 [0 1 2 3]하고 i=5하기 -> i=5가 없기에 5를 집어넣고 [0 1 2 3 5] 재귀함수 호출해서 sol[4+1] 호출

10. sol[5]를 실행하는데 i=4 인덱스가 없으므로 [0 1 2 3 5 4]로 append하고 pop하기 전에 재귀함수 sol[5+1]을 호출

11.so[6]을 실행하는데 6==N이랑 동일하므로 If문 실행해서 아까 7번에서 구한 값과 비교하여 큰값을 저장 -> sol[5] pop하러 가기

12. sol[5]의 pop을 하였기에 [0 1 2 3 5]에서 i=5를 실행하는데 이미 인덱스 5가 있으므로 종료

13. sol[3]의 pop을 하여서 [0 1 2 3]에서 i=4 실행

..........

코드 참고 자료 : https://fre2-dom.tistory.com/442

💻 Python(파이썬) - Permutation 라이브러리 사용하지 않고 재귀함수 백트래킹

import sys


def sol(x):
    global answer
    # x가 n개라면 => x == len(temp)
    # 조건에 맞게 수를 더해준다.
    if x == n:
        total=0
        #차이의 합을 구하기
        total = sum(abs(m[temp[i + 1]] - m[temp[i]]) for i in range(n - 1))
        #이전에 구한 합과 비교해서 큰값을 저장
        answer = max(total,answer)
        return

    # 반복문을 통해 idx를 temp에 저장
    for i in range(n):
        if i not in temp:
            temp.append(i)
            sol(x + 1) # 백 트래킹
            temp.pop()


n = int(sys.stdin.readline())
m = list(map(int, sys.stdin.readline().split()))
#차이의 합
answer = 0
#배열의 인덱스의 값
temp = []
sol(0)

print(answer)

💻 Java(자바)  -> Python과 동일한 방법으로 temp를 pop 사용

참고 자료 : https://wakestand.tistory.com/197

* 스택 선언 - Stack<Integer> temp = new Stack<Integer>();

* 스택 인덱스 확인 temp.elementAt(i) : i번째 인덱스 확인

* 스택 안에 특정 값있는지 확인 temp.indexof(i): i가 스택안에 들었는지 확인

* 스택 안에 넣기 temp.push(i) -> 스택 temp안에 i 넣기

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

public class Main {
    static int sum =0;
    static int n;
    static int[] array;
    static Stack<Integer> temp = new Stack<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        array = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<n;i++){
            array[i] = Integer.parseInt(st.nextToken());
        }
        sol(0);
        System.out.println(sum);
    }
    static void sol(int x){
        if(x==n){
            int total = 0;
            for(int i=0;i<n-1;i++){
                //스택 인덱스 확인
                total += Math.abs(array[temp.elementAt(i+1)]- array[temp.elementAt(i)]);
            }
            if(total>sum){
                sum = total;
            }
            return;
        }
        for(int i=0;i<n;i++){
            if(!temp.contains(i)){
                temp.push(i);
                sol(x+1);
                temp.pop();
            }
        }
    }
}

💻 Java(자바) -> visted로 포함한 함수인지 확인하는 법

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

public class Main {
    static int sum =0;
    static int n;
    static int[] array,temp;
    static boolean[] visted;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        array = new int[n];
        temp = new int[n];
        visted=new boolean[n];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<n;i++){
            array[i] = Integer.parseInt(st.nextToken());
        }
        sol(0);
        System.out.println(sum);
    }
    static void sol(int x){
        if(x==n){
            int total = 0;
            for(int i=0;i<n-1;i++){
                total += Math.abs(array[temp[i+1]]- array[temp[i]]);
            }
            if(total>sum){
                sum = total;
            }
            return;
        }
        for(int i=0;i<n;i++){
            if(!visted[i]){
                visted[i]=true;
                temp[x]=i;
                sol(x+1);
                visted[i]=false;
            }
        }
    }
}