[코딩 테스트 RUN] SWEA 수업 : 1208. Flatten

 

⚠️ 주의!
SWEA에서 낸 코딩 문제에 대한 해답이 들어있습니다.
열람 시 주의해주세요.

 

 

[SW Expert Academy] 1208. Flatten

SW Expert Academy

그러니까 한마디로 최대값에서 빼어서 최소값에 넣어 정렬하는 것이다. 중요한 건 최대값과 최소값은 매 루프마다 바뀔 수 있다는 것. '재정렬'하는 방법도 있지만(Array.sort 등 사용) 정렬 자체가 꽤 오랜 비용이 드는터라(처음부터 순회해야한다). 좋지는 않다. (for문을 사용한 메서드 분리 등의 방법도 있긴하다!)

max와 min의 index값을 갱신하는 방향으로 해두는 쪽이 연산이나 메모리상으로는 더 낫다(그것만 있으면 되기 때문에). 그리고 마지막으로 끝났을 때도 한 차례 정렬한 뒤에 값을 반환할 것. 하지 않으면 max값과 min값이 안 맞을 수도 있다.

 

참고로 2중 for문은 거의 반드시 사용해야 한다.

 

 

 

정답

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

public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = 10;
        for(int test_case = 1; test_case <= T; test_case++) {

            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] arr = new int[st.countTokens()];
            int answer = 0, maxValue = 0, minValue = 0;

            for (int i = 0; i < arr.length; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            //dump
            for(int i = 0; i < n; i++){
                int maxIndex = 0;
                int minIndex = 0;

                //최대 및 최소를 2중for로 구해야한다.
                for(int j = 0; j < arr.length; j++) {
                    if(arr[j] > arr[maxIndex]) maxIndex = j;
                    if(arr[j] < arr[minIndex]) minIndex = j;
                }

                // 값이 같을 경우 이미 종료된 상황이기 때문에 break; 처리한다.
                if(arr[maxIndex] == arr[minIndex]) {
                    break;
                }
                arr[maxIndex] = arr[maxIndex] - 1;
                arr[minIndex] = arr[minIndex] + 1;

                answer = arr[maxIndex] - arr[minIndex];
            }


            // dump가 끝난 뒤에 다시한번 카운팅
            // 하지 않으면 max와 min이 안 맞을 수 있음.
            for(int i = 0; i < arr.length; i++){
                if(arr[i] > arr[maxValue]) maxValue = i;
                if(arr[i] < arr[minValue]) minValue = i;
            }

            answer = arr[maxValue] - arr[minValue];

            System.out.println("#" + test_case + " " + answer);

        }
    }
}

 

강사님의 경우는 정렬 메서드를 분리하는 방식을 사용하셨다. 내 쪽은 "정렬"보다는 그리디(Greedy)에 가까운 풀이 방식이다.