[백준] 10431번 : 줄세우기

---

풀이 방법

내가 선택한 해결 방법은

1. 두 번째 학생부터 순차적으로 선택
2. 선택된 학생의 앞에 있는 학생들의 키를 순차적으로 검사
3. 선택된 학생보다 키가 큰 학생이 존재한다면 그 앞 자리에 넣고, 둘 사이의 거리를 계산.
   • 둘 사이의 거리 = 뒤로 물러난 학생 수

막상 적어놓고 보니 주어진 문제대로 착실하게 구현한 것 같다..!

다른 풀이를 보니 굳이 정렬하지 않고, 선택된 학생 앞에 키가 큰 학생의 수를 더해서 간단하게 해결한 풀이도 있었다.

for(int i=1;i<20;i++) {
	for(int j=i-1;j>=0;j--) {
    	if(students[j] > students[i])
        	result++;
    }
}

처음엔 내가 생각보다 어렵게 푼건가 싶긴 했는데, 걸린 시간과 메모리를 비교해보니 2배정도 차이나는 것으로 보아 내 방식도 나쁘지 않은 방법이였구나 생각했다.

• 정렬하지 않고, 비교만 한 코드
  

• 내 코드
  

이러한 간단한 문제에서는 짧은 코드로 빠르게 푸는것이 중요하지만, 후에 어려운 문제에서는 시간과 메모리를 줄이는 것이 중요하지 않을까 위로했다..

한 문제를 풀더라도, 여러 코드를 보면서 접근 방식을 다양하게 넓혀가는게 중요하다 생각한다.
오늘도 지식이 늘었다!!

코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        for(int i=0;i<n;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            sb.append(st.nextToken()).append(" ");

            LinkedList<Integer> students = new LinkedList<>();
            for(int j=0;j<20;j++) {
                students.add(Integer.parseInt(st.nextToken()));
            }

            int result = Sort(students);
            sb.append(result).append("\n");
        }

        System.out.println(sb);
    }

    private static int Sort(LinkedList<Integer> students) {
        int result=0;
        for(int i=1;i<20;i++) {
            for(int j=0;j<i;j++){
                if(students.get(j) > students.get(i)){
                    // 앞으로 이동
                    int temp = students.remove(i);
                    students.add(j, temp);

                    // i와 j의 차이가 물러난 학생 수가 됨
                    result += (i-j);
                    break; // 앞에 있는 키가 큰 학생 중 맨 앞 학생만 체크.
                }
            }
        }
        return result;
    }
}