[알고리즘]병사 배치하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

/**
 * packageName    : org.example.병사배치하기
 * fileName       : Main
 * author         : ipeac
 * date           : 2023-08-31
 * description    :
 * ===========================================================
 * DATE              AUTHOR             NOTE
 * -----------------------------------------------------------
 * 2023-08-31        ipeac       최초 생성
 */
public class Main {
    public static void main(String[] args) {
        try (
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ) {
            int n = Integer.parseInt(br.readLine());
            if (!(1 <= n && n <= 2000)) {
                String errorMessage = String.format("n 의 범위는 1 <= n <= 2000 입니다. n = %d", n);
                throw new IllegalArgumentException(errorMessage);
            }
            String[] input = br.readLine()
                               .split(" ");
            
            List<Soldier> soldiers = new ArrayList<>();
            
            for (int i = 0; i < n; i++) {
                soldiers.add(Soldier.from(i, input[i]));
            }
            
            int[] dp = new int[n];
            
            // 자체 dp 에서 최대 카운트를 각자 1씩은 가질 수 있음
            Arrays.fill(dp, 1);
            
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    Soldier targetSoldier = soldiers.get(i);
                    Soldier comparableSoldier = soldiers.get(j);
                    if (comparableSoldier.isStrongerThan(targetSoldier)) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
            int maxLength = Arrays.stream(dp)
                                  .max()
                                  .getAsInt();
            int answer = n - maxLength;
            System.out.println(answer);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    
    public static class Soldier {
        private final int index;
        private final int power;
        
        public Soldier(int index, int power) {
            if (!(0 <= index && index <= 2000)) {
                String errorMessage = String.format("index 의 범위는 0 <= index <= 2000 입니다. index = %d", index);
                throw new IllegalArgumentException(errorMessage);
            }
            if (!(1 <= power && power <= 1000000000)) {
                String errorMessage = String.format("power 의 범위는 1 <= power <= 1000000000 입니다. power = %d", power);
                throw new IllegalArgumentException(errorMessage);
            }
            
            this.index = index;
            this.power = power;
        }
        
        public int getIndex() {
            return index;
        }
        
        public int getPower() {
            return power;
        }
        
        public boolean isStrongerThan(Soldier other) {
            Objects.requireNonNull(other, "other 는 null 이 될 수 없습니다.");
            return this.power > other.power;
        }
        
        public static Soldier from(int index, String power) {
            Objects.requireNonNull(power, "power 는 null 이 될 수 없습니다.");
            int powerValue = Integer.parseInt(power);
            return new Soldier(index, powerValue);
        }
    }
}

• DP → LIS 문제 였다고 한다.
  • LIS란?
    • Longest Increasing Subsequence
    • 주어진 수열에서 가장 긴 증가하는 수열을 찾는 문제
    • 두 가지 방식이 있다고 한다.
      1. O(n^2) 의 로직과
      2. O(n log n) 의 로직
    • n log n 로직은 솔직히 이해하기가 좀 난해하여 O(n^2) 로직을 적용하였다.

  int[] dp = new int[n];
      
  // 자체 dp 에서 최대 카운트를 각자 1씩은 가질 수 있음
  Arrays.fill(dp, 1);

• 일단 본인값을 포함한다면 항상 최소 1의 길이는 모든 수열을 기준으로 해도 가지게 된다.

• dp 배열을 전부 1로 설정함.

for (int i = 1; i < n; i++) {
  for (int j = 0; j < i; j++) {
      Soldier targetSoldier = soldiers.get(i);
      Soldier comparableSoldier = soldiers.get(j);
      if (comparableSoldier.isStrongerThan(targetSoldier)) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
      }
  }
}

• 기준되는 솔저를 하나 잡고

• 비교되는 솔저도 하나 잡는다.
  • 기준되는 솔저 왼쪽의 솔저들을 순회해야하기에
  • 결국 이중 반복문인 O(n^2) 이 될 수 밖에 없다.

• 기준이 되는 솔저의 power 가 항상 비교되는 솔저의 power보다 작아야한다.
  • 그리고 비교되는 솔저의 값보다 작다면 해당 비교되는 솔저가 가진 최장길이 값에 + 1 이 되어야하고, 별도로 기준의 되는 솔저 의 최장길이 값이 더 크다면 그 값을 그대로 두어야하기에
  • dp[i] 도 별도로 필요하다.

    Math.max(dp[i], dp[j] + 1);

int maxLength = Arrays.stream(dp)
                                  .max()
                                  .getAsInt();

• dp 배열에서 최댓값을 결국 순회하면서 최댓값을 찾아와서

• 솔저의 수에 해당 maxLength 를 빼주면 된다.

---

• 별도로 dp에 값을 담기만하고, maxCount 를 별도로 이중 for문 > if 문 안에서 구해줘도 될 것 같다.

• 굳이 stream을 돌아서 O(n) 을 수행할 필요는 없는 것 같다.

int maxCount = 1;
  for (int i = 1; i < n; i++) {
      for (int j = 0; j < i; j++) {
          Soldier targetSoldier = soldiers.get(i);
          Soldier comparableSoldier = soldiers.get(j);
          if (comparableSoldier.isStrongerThan(targetSoldier)) {
              dp[i] = Math.max(dp[i], dp[j] + 1);
              maxCount = Math.max(maxCount, dp[i]);
          }
      }
  }

하지만 입력 데이터 자체가 모수가 적어서

별 차이는 없었다.

Uploaded by N2T