[SWEA] 1208. [S/W 문제해결 기본] 1일차 - Flatten - (Java)

[SWEA] 1208. [S/W 문제해결 기본] 1일차 - Flatten - (Java)

제출일 : 2020-06-19

문제 풀이 시간 : 30M

난이도 : ★★★

---

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

문제

한 쪽 벽면에 다음과 같이 노란색 상자들이 쌓여 있다.

높은 곳의 상자를 낮은 곳에 옮기는 방식으로 최고점과 최저점의 간격을 줄이는 작업을 평탄화라고 한다.

평탄화를 모두 수행하고 나면, 가장 높은 곳과 가장 낮은 곳의 차이가 최대 1 이내가 된다.

평탄화 작업을 위해서 상자를 옮기는 작업 횟수에 제한이 걸려있을 때, 제한된 횟수만큼 옮기는 작업을 한 후 최고점과 최저점의 차이를 반환하는 프로그램을 작성하시오.

가장 높은 곳에 있는 상자를 가장 낮은 곳으로 옮기는 작업을 덤프라고 정의한다.

위의 예시에서 제1회 덤프를 수행한 이후 화면은 다음과 같다.

A부분의 상자를 가장 낮은 B부분에 덤프하였으며, A대신 A’부분의 상자를 사용해도 무방하다.

다음은 제2회 덤프를 수행한 이후의 화면이다.

A’부분의 상자를 옮겨서, C부분에 덤프하였다. 이때 C 대신 C’부분에 덤프해도 무방하다.

2회의 덤프 후, 최고점과 최저점의 차이는 8 – 2 = 6 이 되었다 (최초덤프 이전에는 9 – 1 = 8 이었다).

덤프 횟수가 2회로 제한된다면, 이 예시 문제의 정답은 6이 된다.

제약 사항

가로 길이는 항상 100으로 주어진다.

모든 위치에서 상자의 높이는 1이상 100이하로 주어진다.

덤프 횟수는 1이상 1000이하로 주어진다.

주어진 덤프 횟수 이내에 평탄화가 완료되면 더 이상 덤프를 수행할 수 없으므로 그 때의 최고점과 최저점의 높이 차를 반환한다 (주어진 data에 따라 0 또는 1이 된다).

입력

총 10개의 테스트 케이스가 주어지며, 각 테스트 케이스의 첫 번째 줄에는 덤프 횟수가 주어진다. 그리고 다음 줄에 각 상자의 높이값이 주어진다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스의 최고점과 최저점의 높이 차를 출력한다.

예제

입력

834
42 68 35 1 70 25 79 59 63 65 6 46 82 28 62 92 96 43 28 37 92 5 3 54 93 83 22 17 19 96 ...
617
16 40 59 5 31 78 7 74 87 22 46 25 73 71 30 78 74 98 13 87 91 62 37 56 68 56 75 32 53 ...
...

출력

#1 13
#2 32
...

문제 풀이 접근

문제를 2가지 방법으로 풀어보았다.

첫번째 방법은 주어진 입력을 그대로 map의 배열에 담은 뒤

1. 정렬을 수행한다
2. 맨앞의 값(map[0])은 +1, 맨 뒤의 값(map[99])은 +1의 연산을 수행한다.

위 과정을 dump 수 만큼 반복한 뒤 결과를 출력(map[99]-map[0])하였고

두번째 풀이는 입력을 받을 때 상자의 개수를 카운트 하는 형식으로 값을 담았고 입력을 받을때 min값과 max값을 구하였다.

1. min개의 개수를 가진 상자를 -1 하고 min+1개의 개수를 가진 상자를 +1
2. max개의 개수를 가진 상자를 -1 하고 max-1개의 개수를 가진 상자를 +1
3. map[min], map[max]값이 0이라면 min, max를 조정한다.

위 과정을 dump수만큼 반복한 뒤 결과를 출력(max-min)하였다.

처음 문제에서는 dump 수 만큼 정렬을 진행하기 때문에 속도가 느릴 것 같아 두번째 풀이로 문제를 한번 더 풀어보았다. 생각보다 속도측 면에서 많은 차이가 나지 않은 것이 조금 놀랐다.

코드 1

언어 : JAVA

메모리 : 24,804 kb

실행 시간 : 179 ms

import java.io.FileInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class Solution {
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int T = 10;
        int N = 100;
        for (int tc = 1; tc <= T; tc++) {
            int dump = sc.nextInt();
            int[] map = new int[N];
            for (int i = 0; i < N; i++) {
                map[i] = sc.nextInt();
            }
            for (int i = 0; i < dump; i++) {
                Arrays.sort(map);
                map[0]++;
                map[99]--;
            }
            Arrays.sort(map);
            System.out.println("#" + tc + " " + (map[99] - map[0]));
        } // end of TC
    }// end of Main
}

코드 2

언어 : JAVA

메모리 : 24,444 kb

실행 시간 : 160 ms

import java.io.FileInputStream;
import java.util.Scanner;

public class Solution {
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int T = 10;
        for (int tc = 1; tc <= T; tc++) {
            int dump = sc.nextInt();
            int[] map = new int[101];
            int max = 1;
            int min = 100;
            for (int i = 0; i < 100; i++) {
                int tmp = sc.nextInt();
                map[tmp]++;
                max = Math.max(max, tmp);
                min = Math.min(min, tmp);
            }
            for (int i = 0; i < dump; i++) {
                map[min]--;
                map[min + 1]++;

                map[max]--;
                map[max - 1]++;

                while (map[min] == 0) {
                    min++;
                }

                while (map[max] == 0) {
                    max--;
                }
            }

            System.out.println("#" + tc + " " + (max - min));
        } // end of TC
    }// end of Main
}