[Greedy] Softeer(소프티어) level 2 진정한 효도 Java 풀이

https://softeer.ai/practice/7374

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

문제 풀이 방법

1. 입력 처리 및 데이터 저장

• 3×3 크기의 땅 높이 정보를 입력받아 ground라는 2차원 배열에 저장합니다.

2. 각 행에 대한 비용 계산:

• 해당 행의 세 개의 높이를 row 리스트에 추가합니다.
• row 리스트를 오름차순으로 정렬합니다.
• 만약 세 높이가 모두 같다면 (row.get(0) == row.get(2)), 이미 평탄하므로 비용은 0이며, 프로그램을 종료합니다.
• 그렇지 않다면, 가장 큰 높이로 다른 두 높이를 맞추는 데 필요한 비용을 계산합니다:
  • currentCost = (row.get(2) - row.get(0)) + (row.get(2) - row.get(1));
• 계산된 currentCost와 현재까지의 최소 비용 answer를 비교하여 더 작은 값을 answer에 저장합니다.
• row 리스트를 초기화합니다.

3. 각 열에 대한 비용 계산:

• 해당 열의 세 개의 높이를 row 리스트에 추가합니다.
• 이후의 과정은 행에 대한 계산과 동일합니다:
  1. 오름차순 정렬 후 높이가 모두 같다면 비용 0을 출력하고 종료합니다.
  2. 그렇지 않다면 currentCost를 계산하고 최소 비용을 업데이트합니다.
  3. row 리스트를 초기화합니다.

결과 출력

• 모든 행과 열에 대한 계산이 끝나면, 최종적으로 구한 최소 비용 answer를 출력합니다.

핵심 아이디어

• 평탄화 대상 선택: 각 행과 열별로 따로 계산하여, 그 중 최소 비용을 선택합니다.
• 비용 계산 방법: 가장 큰 높이로 다른 높이들을 맞추는 방식으로 비용을 계산합니다.
• 최적의 결과 도출: 모든 경우를 고려하여 최소 비용을 찾습니다.

코드

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

public class Main {

    public static final List<Integer> row = new ArrayList<>();

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

        int[][] ground = new int[3][3];
        int currentCost;
        int answer = 4;
        for (int i = 0; i < 3; i++) {
            st = new StringTokenizer(in.readLine());
            for (int j = 0; j < 3; j++) {
                int height = Integer.parseInt(st.nextToken());
                ground[i][j] = height;
                row.add(height);
            }
            Collections.sort(row);
            currentCost = 0;
            if (row.get(0) == row.get(2)) {
                System.out.println(0);
                return;
            } else {
                currentCost = (row.get(2) - row.get(0)) + (row.get(2) - row.get(1));
            }
            if (currentCost < answer) {
                answer = currentCost;
            }
            row.clear();
        }
        
        for (int i = 0; i < 3; i++) {
            currentCost = 0;
            for (int j = 0; j < 3; j++) {
                row.add(ground[j][i]);
            }
            Collections.sort(row);
            if (row.get(0) == row.get(2)) {
                System.out.println(0);
                return;
            } else {
                currentCost = (row.get(2) - row.get(0)) + (row.get(2) - row.get(1));
            }
            if (currentCost < answer) {
                answer = currentCost;
            }
            row.clear();
        }
        System.out.println(answer);   
    }
}