[알고리즘]한줄로 서기

import java.io.*;
import java.text.MessageFormat;
import java.util.*;

/* ***
 *
 *
 *
 *
 *
 *  */
public class Main {
    static int n;
    
    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)))) {
            n = Integer.parseInt(br.readLine());
            // 이미 배열의 길이가 정해져있다.
            List<Person> people = new ArrayList<>();
            String input = br.readLine();
            String[] split = input.split(" ");
            
            for (int i = 0; i < n; i++) {
                int height = i + 1;
                String order = split[i];
                Person person = Person.of(height, order);
                people.add(person);
            }
            
            Collections.reverse(people);
            
            // person 의 연결의 맺음과 끊음이 잦기에 LinkedList를 사용한다.
            List<Person> answers = new LinkedList<>();
            
            for (int i = 0; i < n; i++) {
                Person targetPerson = people.get(i);
                answers.add(targetPerson.getLeftSideCount(), targetPerson);
            }
            
            answers.stream()
                   .mapToInt(Person::getHeight)
                   .forEach(height -> pw.print(height + " "));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    public static class Person implements Comparable<Person> {
        private final int height;
        private final int leftSideCount;
        
        public Person(int height, int leftSideCount) {
            if (!(1 <= height && height <= n)) {
                String errorMessage = MessageFormat.format("키는 1 이상 {0} 이하 여야합니다. (현재 키 = {1})", n, height);
                throw new IllegalArgumentException(errorMessage);
            }
            this.height = height;
            this.leftSideCount = leftSideCount;
        }
        
        public int getHeight() {
            return height;
        }
        
        public int getLeftSideCount() {
            return leftSideCount;
        }
        
        public static Person of(int height, String order) {
            Objects.requireNonNull(order, "order must be provided.");
            int orderInt = Integer.parseInt(order);
            return new Person(height, orderInt);
        }
        
        @Override
        public int compareTo(Person o) {
            return this.height - o.height;
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Person)) return false;
            
            Person person = (Person) o;
            
            if (height != person.height) return false;
            return leftSideCount == person.leftSideCount;
        }
        
        @Override
        public int hashCode() {
            int result = height;
            result = 31 * result + leftSideCount;
            return result;
        }
        
        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer("Person{");
            sb.append("height=")
              .append(height);
            sb.append(", leftSideCount=")
              .append(leftSideCount);
            sb.append('}');
            return sb.toString();
        }
    }
}

• 문제에서 왼쪽에 몇명의 더 키큰 사람이 있는지를 주요한 사항으로 보았다.

• 단순히 키가 작은순의 배열에서 반대로 뒤집기
  • Collection.sort
    • Tim sort 를 사용
    • 최악의 경우 O(n log n)

• 키큰순으로 각 객체의 leftSideCount 에 맞는 index 에 해당하는 값을 넣게 되면

• 각 요소의 처음 insert 된 요소의 위치가 배열에서 상대적으로 변해도, 어차피 상대적으로 키가 작은 객체만 앞이나 뒤에 추가가 되기 때문에, 정합성을 위배하지 않는다.

• 처음에 값의 추가와 삭제가 종종 되기에, LinkedList 를 사용하려고했다. …
  • 하지만, 찾아보니까 LinkedList 도 중간 인덱스에 값을 추가하는 경우에는 결국 최악 O(n) 의 성능을 보인다고 한다.
  • 어차피 순회를 해야하기 때문이다.
  • 그러면 사실상 ArrayList 나 LinkedList 사용하나 별 차이가 없다고도 생각할 수 있다.

  굳이 LinkedList 를 사용할 필요가 없었다는 의미이다.

Uploaded by N2T