[Java] 백준 10431 - 줄 세우기

백준 10431 줄 세우기

문제 링크

문제 이해 및 접근

• 뒤로 물러나는 걸음 수 계산하기

따라서 배열에 삽입하는 방식으로 접근. 삽입 후 인덱스를 이용, 뒤로 물러나는 걸음 수를 계산

ArrayList 활용

• 크기가 동적임
• 삽입시 자동으로 요소를 밀어냄 (문제에서 말하는 줄 세우기랑 같음!)

코드 구현

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    int P = Integer.parseInt(br.readLine());

    for (int t = 1; t <= P;t++ ) {
      String line = br.readLine();
      StringTokenizer st = new StringTokenizer(line, " ");

      int tc = Integer.parseInt(st.nextToken());

      // 학생 수는 20명
      ArrayList<Integer> heights = new ArrayList<>();

      // 걸음 수 초기화
      int totalSteps = 0;

      for (int i = 0; i < 20; i++) {
        int curHeight = Integer.parseInt(st.nextToken());
        boolean isInserted = false;
        for (int j = 0; j < heights.size(); j++) {
          if (heights.get(j) > curHeight) {
            // 키가 더 큰 경우 - 이 앞에 들어가야 함.
            heights.add(j, curHeight);
            totalSteps += heights.size() - 1 - j ;
            isInserted = true;
            break;
          }
        }
        if (!isInserted) {
          heights.add(curHeight);
        }
      }
      sb.append(tc).append(" ").append(totalSteps).append('\n');
    }
    br.close();
    System.out.println(sb.toString());
  }
}

고민 내용과 결론

• 총 걸음수를 어떻게 계산할 것인가.
  • 일단 집어넣고, 전체 크기에서 (1 - j)를 해준다. j는 들어간 자리.
• 만약 큰 사람이 없다면 -> 그냥 add

아무래도 이번 문제는 node로 풀었다면 splice 무한 반복으로 귀찮았을지도 모르겠다.