[SW Expert] 5948. 새샘이의 7-3-5 게임

생각

Github - https://github.com/hellojdh/Code/blob/master/src/swexpert/d3/Q5948.java

7개의 숫자가 주어질 때 3개의 수를 더하여 만들 수 있는 수중 5번째로 큰 수를 출력하여라.
중복 숫자는 1개로 친다.

처음 생각

중복을 없앨 생각으로 Set 자료 구조를 생각하였다. Set은 중복을 불허하는 자료구조이다. Set에 담긴 자료들을 정렬하기 위해 List로 바꿔주기 위해 List도 선언해 주었다.

다음 생각

7개중 3개의 숫자 조합이므로 반복문 변수 j,k,z를 사용하였다.

▶ k의 경우는 j+1 부터 시작을, z의 경우는 k+1부터 시작을 하게 하였다.

▶ 이럴경우 중복된 숫자가 골라지지는 않겠지만 더했을 경우 같은 숫자들이 나올 수 있으므로 Set을 이용해 주는게 맞다.

다다음 생각

7개중 순서 상관없이 서로다른 3개를 뽑아 더하는 것이므로 최대 7C3 = 35개의 경우의 수가 생기므로 배열로 관리해도 충분 할 것 같다.

다다다음 생각

Python으로 문제를 풀경우 set 자료형이 존재하기 때문에 Java보다 조금 더 쉽게 처리를 할 수 있었다.

방안

1) Java 풀이

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

package swexpert.d3;   import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*;   public class Q5948 {     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         int tc = Integer.parseInt(br.readLine());         // 정렬을 위해서         List<Integer> list = new ArrayList<>();         // 중복 방지를 위해서         HashSet<Integer> set = new HashSet<>();         StringBuilder sb = new StringBuilder();         int[] arr;         for(int i=1;i<=tc;i++){             StringTokenizer st = new StringTokenizer(br.readLine());             arr = new int[7];             for(int j=0;j<7;j++)                 arr[j] = Integer.parseInt(st.nextToken());               // 초기화             list.clear();             set.clear();             for(int j=0;j<7;j++){                 for(int k=j+1;k<7;k++){                     for(int z=k+1;z<7;z++)                         // 3개를 더한 값을 만들어 준다.                         // 중복 제거를 위해 set을 사용                         set.add(arr[j]+arr[k]+arr[z]);                 }             }             // 정렬을 위해 set의 자료들을 list로 만들어주기             list.addAll(set);             Collections.sort(list,Collections.reverseOrder());             // 제일 큰거에서 5번째             sb.append("#"+i+" "+list.get(4)+"\n");         }         System.out.println(sb);     } }

2) Python 풀이

▶ Python의 경우 itertools의 combinations를 이용하면 쉽게 해결할 수 있다.

1

2

3

4

5

6

7

from itertools import combinations

tc = int(input())

for i in range(tc):

    tList = list(map(int,input().split()))

    result = list(set(i[0]+i[1]+i[2] for i in combinations(tList,3)))

    result.sort()

    print("#"+str(i+1),result[len(result)-5])