SW 역량 테스트 기출 문제(연산자 끼워넣기, 스타트와 링크)

[연산자 끼워넣기 _ 14888]

 

 

* 조건

1. 피연산자와 연산자로 구성할 수 있는 모든 경우의 식을 구한다
2. 계산된 값 중에서 최댓값과 최솟값을 출력한다
3. 나누기 연산 시 부호를 고려해야 한다

* 알고리즘

- 주어진 연산자로 구성할 수 있는 모든 경우의 식을 도출: 브루트포스

 

* 로직(Logic)

- 그동안 풀었던 모든 경우의 수 구하는 코드 적용

- 식이 사용되면 하나씩 차감을 하면서 남아있는 부호를 가지고 조합 진행

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Problem_14888 {

    static int numSize;
    static int[] nums;
    static int[] operations;  //연산자 (+, -, x, / 개수)

    static HashSet<Long> hashSet = new HashSet<>();  //나오는 값들을 담는 공간

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        numSize = Integer.parseInt(br.readLine());
        nums = new int[numSize];
        operations = new int[4];

        String config = br.readLine();
        st = new StringTokenizer(config, " ");
        for(int i=0; i<numSize; ++i){
            nums[i] = Integer.parseInt(st.nextToken());
        }

        String input = br.readLine();
        st = new StringTokenizer(input, " ");
        for(int i=0; i<4; ++i){
            operations[i] = Integer.parseInt(st.nextToken());
        }

        //부호 기준
        for(int i=0; i<4; ++i){
            if(operations[i] > 0){
                for(int j=0; j<operations[i]; ++j){
                    int sign = i;           //부호 = 0(+) 1(-) 2(*) 3(/)
                    int numIdx = 0;         //숫자의 인덱스 관리
                    long acc = nums[numIdx++];

                    doProcess(acc, sign, numIdx);
                }
            }
        }

        long max = Integer.MIN_VALUE;
        long min = Integer.MAX_VALUE;
        for(long ans : hashSet){
            if(max < ans){
                max = ans;
            }
            if(min > ans){
                min = ans;
            }
        }

        System.out.println(max);
        System.out.println(min);

    }

    private static void doProcess(long acc, int sign, int numIdx) {

        if(numIdx == numSize){
            hashSet.add(acc);
            return;
        }

        if(operations[sign] == 0){
            return;
        }

        long tmp = doCalculate(acc, sign, numIdx);
        for(int i=0; i<4; ++i){
            if(operations[i] > 0){
                for(int j=0; j<operations[i]; ++j){
                    operations[sign]--;
                    numIdx++;
                    doProcess(tmp, i, numIdx);
                    numIdx--;
                    operations[sign]++;
                }
            }
        }
    }

    private static long doCalculate(long acc, int sign, int numIdx) {
        switch (sign){
            case 0:
                acc += nums[numIdx];
                break;

            case 1:
                acc -= nums[numIdx];
                break;

            case 2:
                acc *= nums[numIdx];
                break;

            case 3:
                if(acc < 0 && nums[numIdx] < 0){
                    //양수로 바꾸고
                    acc = acc * -1;
                    int temp = nums[numIdx] * -1;
                    acc /= temp;
                }
                else if(acc > 0 && nums[numIdx] < 0){
                    //양수로 바꾸고
                    int temp = nums[numIdx] * -1;
                    acc /= temp;
                    acc *= -1;
                }
                else if(acc < 0 && nums[numIdx] > 0){
                    //양수로 바꾸고
                    acc = acc * -1;
                    int temp = nums[numIdx];
                    acc /= temp;
                    acc *= -1;
                }
                else if(acc > 0 && nums[numIdx] > 0){
                    int temp = nums[numIdx];
                    acc /= temp;
                }
                break;
        }
        return acc;
    }
}

 

[스타트와 링크 _ 14889]

 

 

* 조건

1. 사람의 수(N)이 주어졌을 때, 2팀으로 나누어야한다 (ex. N=6 -> 스타트팀(3명), 링크(3명))
2. 두 팀에게 할당된 팀원 수는 항상 같아야한다
3. 각각 구성된 팀의 능력치의 차이가 최소인 값을 구해야한다

* 알고리즘

- 팀을 구성하는 모든 경우의 수, 그 팀 내에서 만들어낼 수 있는 팀 능력치 경우의 수: 브루트포스

 

* 로직(Logic)

- 팀을 만드는 경우의 수 -> 팀이 만들어지면 그 팀을 가지고 능력치를 구하기 -> 팀간의 최솟값을 구하기

- 재귀를 돌릴 때 부분집합을 구하는 방식처럼

현재 값을 저장하고 재귀 / 현재 값은 저장 안하고 다음값으로 재귀의 경우로 나눈다

- 진행중에 각 팀에 할당해야하는 인원이 꽉 차면 팀 능력치를 각각 구한다

- 이를 반복한다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Problem_14889 {

    static int n;
    static int[][] abilities;
    static int[] members;
    static int memberNum;

    static int min = Integer.MAX_VALUE;
    static boolean[] checked;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        abilities = new int[n][n];
        for(int i=0; i<n; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            for(int j=0; j<n; ++j){
                abilities[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //팀을 만드는 경우의 수 (브루트포스) -> 팀이 만들어지면 그 팀을 가지고 능력치를 구하기 -> 팀간의 최솟값을 구하기
        members = new int[n];
        checked = new boolean[n];
        ArrayList<Integer> pathLists = new ArrayList<>();
        memberNum = n/2;

        int index = 0;
        int count = 0;
        makeTeam(index, count, pathLists);

        System.out.println(min);

    }

    private static void makeTeam(int index, int count, ArrayList<Integer> pathLists) {

        if(index > n) return;

        if(count == memberNum){
            //팀 시너지 계산
            int value = doCalculate(pathLists);
            min = Math.min(min, value);
            return;
        }

        pathLists.add(index);
        makeTeam(index+1, count+1, pathLists);

        pathLists.remove(pathLists.size()-1);
        makeTeam(index+1, count, pathLists);

    }

    private static int doCalculate(ArrayList<Integer> pathLists) {
        for(int i=0; i<pathLists.size(); ++i){
            checked[pathLists.get(i)] = true;
        }

        int teamScoreA = 0;
        int teamScoreB = 0;
        for(int i=0; i<n; ++i){
            if(checked[i]){
                for(int j=0; j<n; ++j){
                    if(checked[j] && i != j){
                        teamScoreA += abilities[i][j];
                    }
                }
            }
            else{
                for(int j=0; j<n; ++j){
                    if(!checked[j] && i != j){
                        teamScoreB += abilities[i][j];
                    }
                }
            }
        }

        for(int i=0; i<pathLists.size(); ++i){
            checked[pathLists.get(i)] = false;
        }

        int value = Math.abs(teamScoreA - teamScoreB);

        return value;
    }
}

 

모든 경우의 수를 구할 때에 '순서를 고려할지 말지'에 따라 2가지의 큰 틀이 나뉘는 것 같다. 순서를 고려해야한다면 for문을 통해 계속 재귀로 넘기고, 고려하지 않아도 된다면 위와 같은 방식으로 진행하면 상대적으로 편리하게 경우의 수를 구할 수 있는 것 같다.

 

나만의 기준점이 만들어지는 것 같다는 느낌이 든다. 더 효율적인 사람들의 코드도 보면서 발전시켜나가야겠다.