[백준] 2605번 : 줄 세우기 -JAVA

문제 분석 :
- 학생들이 한 줄로 선 후, 첫번째 학생부터 차례로 번호를 뽑는다.
- 첫 번째로 줄을 선 학생은 무조건 0번 번호를 받아 제일 앞에 줄을 선다.
- 두 번째로 줄을 선 학생은 0번 또는 1번 둘 중 하나의 번호를 뽑는다.
- 0번을 뽑으면 그자리에 있고, 1번을 뽑으면 바로 앞의 학생 앞으로 가서 줄을 선다.
- 세 번째로 줄을 선 학생은 0,1 또는 2 중 하나의 번호를 뽑는다.
- 각자 뽑은 번호는 자신이 처음에 선 순서보다는 작은 수이다.
- 줄을 선 학생들이 차례로 뽑은 번호가 주어질 때 학생들이 최종적으로 줄을 선 순서를 출력

제약 조건
- 학생의 수가 100 이하이고, 학생들이 뽑는 번호는 0 또는 자연수이며
- 학생들이 뽑은 번호 사이에는 빈 칸이 하나씩 있다.
- 각자 뽑은 번호는 자신이 처음에 선 순서보다는 작은 수이다.

의사 결정
- BufferedReader, readLine() 를 통해 입력을 받는다
- 입력 받은 학생 수와, 뽑은 번호를 계산한다.
- 줄을 선 순서를 번호를 출력한다.

예제대로 5명이 한줄로 선 상태를 그림으로 그려보면, 아래와 같다.

학생들이 0 1 1 3 2 를 뽑았을때,

즉 1번 학생은 0을 뽑고, 2번학생은 1을 뽑고, 3번학생은 1을 뽑고, 4번 학생은 4을 뽑고 , 5번 학생은 2 를 뽑은 상황을 가정해보면

한 줄로 선 후, 첫번째 줄 학생은 무조건 0번 번호를 받아 제일 앞에 줄을 선다.

학생들이 한 줄로 선 후, 첫번째 맨 앞의 학생은 무조건 0번 번호를 받아 제일 앞에 줄을 선다.

순서는 그대로 1 2 3 4 5 가 된다.

2번 학생이 1번을 뽑으면 바로 앞으로 이동하게 되어 순서는 변경되어 2 1 3 4 5 가 된다.

3번 학생이 1번을 뽑으면 바로 앞으로 이동하게 되어 순서는 2 3 1 4 5 가 된다.

4번째 학생이 3번을 뽑은 후에, 3명 앞으로 이동해서, 순서는 4 2 3 1 5 가 된다.

5번째 학생이 2번을 뽑은 후에, 2명 앞으로 이동해서

최종 순서는 4 2 5 3 1 이 된다.

문제의 핵심은 학생들이 줄을 서는 순서 에서 ,

i 번째 학생이 뽑은 번호를 뺀  인덱스 값과 , 

i + 1 (첫번째 학생은 무조건 1이기 때문에) 값을

줄서는 순서를 저장할 리스트를 만들어 반복문을 통해 넣어 주는 것이다.

---

3가지 방식으로 풀이

1. - BufferedReader, InputSreamReader , StringBuilder 사용

문제 분석 :
- 학생들이 한 줄로 선 후, 첫번째 학생부터 차례로 번호를 뽑는다.
- 첫 번째로 줄을 선 학생은 무조건 0번 번호를 받아 제일 앞에 줄을 선다.
- 두 번째로 줄을 선 학생은 0번 또는 1번 둘 중 하나의 번호를 뽑는다.
- 0번을 뽑으면 그자리에 있고, 1번을 뽑으면 바로 앞의 학생 앞으로 가서 줄을 선다.
- 세 번째로 줄을 선 학생은 0,1 또는 2 중 하나의 번호를 뽑는다.
- 각자 뽑은 번호는 자신이 처음에 선 순서보다는 작은 수이다.
- 줄을 선 학생들이 차례로 뽑은 번호가 주어질 때 학생들이 최종적으로 줄을 선 순서를 출력

제약 조건
- 학생의 수가 100 이하이고, 학생들이 뽑는 번호는 0 또는 자연수이며
- 학생들이 뽑은 번호 사이에는 빈 칸이 하나씩 있다.
- 각자 뽑은 번호는 자신이 처음에 선 순서보다는 작은 수이다.

의사 결정
- BufferedReader, readLine() 를 통해 입력을 받는다.
- 입력 받은 학생 수와, 뽑은 번호를 계산한다.
- StringBuilder를 사용, 줄을 선 순서를 번호를 출력한다. ( 저장해두었다가 한번에 출력하여 불필요한 객체 생성을 하지 않아서 메모리 효율이 좋다 )

- 3가지 방법중 가장 빠른것이 확인되었는데 , BufferedReader 와 InputSreamReader를 같이 사용하여 효율을 높였고

BufferdReader는 덩어리째로 읽어 들여서 속도가 Scanner 보다 빠르다.

StringBuilder를 사용해서 저장해 두었다가 한번에 출력하여, 불필요한 객체를 생성하는 횟수를 줄였다.

결과 : 메모리 14240 KB , 시간 108 ms

package com.doosane.study01.week01.day4.bronze;

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



/*
메모리 14240 KB
시간 108 ms
 */

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

        int n = Integer.parseInt(br.readLine()); 
        // 학생 수 입력 받기
        
        String[] input = br.readLine().split(" "); 
        // 학생이 뽑은 번호 입력 받기

        int[] selectedNum = new int[n];
        for (int i = 0; i < n; i++) {
            selectedNum[i] = Integer.parseInt(input[i]);
        }

        List<Integer> studentLineOrder = new ArrayList<>(); 
         // 학생들이 줄을 서는 순서 저장할 리스트
         
        for (int i = 0; i < n; i++) {
            int num = selectedNum[i]; 
            // i번째 학생이 뽑은 번호

            studentLineOrder.add(studentLineOrder.size() - num, i + 1);
            // 학생들이 줄을 서는 순서 - i 번째 학생이 뽑은 번호 , i + 1 (첫번째 학생 무조건 1)

        }

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int student : studentLineOrder) {
            sb.append(student).append(" ");
        }
        System.out.println(sb.toString().trim());
    }

}

---

2. 같은 문제 : Scanner  사용

문제 분석 :
- 학생들이 한 줄로 선 후, 첫번째 학생부터 차례로 번호를 뽑는다.
- 첫 번째로 줄을 선 학생은 무조건 0번 번호를 받아 제일 앞에 줄을 선다.
- 두 번째로 줄을 선 학생은 0번 또는 1번 둘 중 하나의 번호를 뽑는다.
- 0번을 뽑으면 그자리에 있고, 1번을 뽑으면 바로 앞의 학생 앞으로 가서 줄을 선다.
- 세 번째로 줄을 선 학생은 0,1 또는 2 중 하나의 번호를 뽑는다.
- 각자 뽑은 번호는 자신이 처음에 선 순서보다는 작은 수이다.
- 줄을 선 학생들이 차례로 뽑은 번호가 주어질 때 학생들이 최종적으로 줄을 선 순서를 출력

제약 조건
- 학생의 수가 100 이하이고, 학생들이 뽑는 번호는 0 또는 자연수이며
- 학생들이 뽑은 번호 사이에는 빈 칸이 하나씩 있다.
- 각자 뽑은 번호는 자신이 처음에 선 순서보다는 작은 수이다.

의사 결정
- Scanner nextInt() 를 통해 학생수 n , 각 학생이 뽑은 번호를 입력을 받는다.
- 학생이 번호를 뽑고 해당 번호 만큼 앞에 삽입 하도록 for문으로 최종 결과를 넣을 리스트에 담는다.
- 최종 출력한다.

결과 : 메모리 18372 KB , 시간 200 ms

package com.doosane.study01.week01.day4.bronze;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/*
결과
메모리 18372 KB
시간 200 ms
 */
public class BOJ2605_Scanner {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // Scanner로 입력 받아서
        int n = sc.nextInt(); // 학생수 n 입력 받아서

        int[] selectedNum = new int[n]; // 각 학생이 뽑은 번호 입력 받아서
        for(int i = 0; i < n; i ++) {
            selectedNum[i] = sc.nextInt();
        }

        List<Integer> studentLineOrder = new ArrayList<>(); // 결과를 담을 리스트 (1부터 n까지의 학생 번호)

        for(int i = 0; i < n; i++) { // 각 학생에 대해 번호를 뽑고, 해당 번호만큼 앞에 삽입
            int num = selectedNum[i]; // 학생이 뽑은 번호
            studentLineOrder.add(studentLineOrder.size() - num, i + 1); // i + 1은 학생 번호
        }

        for (int student : studentLineOrder) {
            System.out.print(student + " ");
        }

    }
}

---

3. 같은 문제 :  가독성 높일 수 있도록 메소드 분리 

문제 분석 :
- 학생들이 한 줄로 선 후, 첫번째 학생부터 차례로 번호를 뽑는다.
- 첫 번째로 줄을 선 학생은 무조건 0번 번호를 받아 제일 앞에 줄을 선다.
- 두 번째로 줄을 선 학생은 0번 또는 1번 둘 중 하나의 번호를 뽑는다.
- 0번을 뽑으면 그자리에 있고, 1번을 뽑으면 바로 앞의 학생 앞으로 가서 줄을 선다.
- 세 번째로 줄을 선 학생은 0,1 또는 2 중 하나의 번호를 뽑는다.
- 각자 뽑은 번호는 자신이 처음에 선 순서보다는 작은 수이다.
- 줄을 선 학생들이 차례로 뽑은 번호가 주어질 때 학생들이 최종적으로 줄을 선 순서를 출력

제약 조건
- 학생의 수가 100 이하이고, 학생들이 뽑는 번호는 0 또는 자연수이며
- 학생들이 뽑은 번호 사이에는 빈 칸이 하나씩 있다.
- 각자 뽑은 번호는 자신이 처음에 선 순서보다는 작은 수이다.

의사 결정
- Scanner nextInt() 를 통해 입력을 받는다
-  가독성이 더 좋도록 , 확장하여 사용하기 쉽도록
   getStudentLineOrder(), printStudentLineOrder() 메소드를 작성하여 분리한다.
- 최종 줄을 선 순서를 번호를 출력한다.

결과 : 메모리 18260 KB , 시간 200ms

package com.doosane.study01.week01.day4.bronze;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/*
결과 :
메모리 18260
시간 200ms
 */
public class BOJ2605_shortMethod {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // Scanner 사용
        int n = sc.nextInt(); // 학생수 입력 받기
        
        // 각 학생이 뽑은 번호 입력 받기 (selectedNum 배열)
        int[] selectedNum = new int[n]; 
        for (int i=0; i< n; i++) {
            selectedNum[i] = sc.nextInt();
        }

        // 최종 순서를 계산하는 getStudentLineOrder()메소드 호출 
        List<Integer> studentLineOrder = getStudentLineOrder(n, selectedNum);

		// 결과 출력
        printStudentLineOrder(studentLineOrder);
    }
    
    // 최종 순서 구하는 메소드
    public static List<Integer> getStudentLineOrder(int n , int[] selectedNum) {
       
       // 결과를 담을 리스트 ( 1부터 n까지의 학생 번호를 관리)
        List<Integer> studentLineOrder = new ArrayList<>();
        
        for (int i= 0; i < n; i++) {
            int num = selectedNum[i];
            // 학생이 뽑은 번호
            studentLineOrder.add(studentLineOrder.size() -  num, i + 1); 
             //  i + 1 은 학생 번호 ( 1부터 시작)
        }
        return studentLineOrder;
    }
    
    // 최종 순서를 출력하는 메소드
    public static void printStudentLineOrder(List<Integer> studentLineOrder) {
        for (int student : studentLineOrder) {
            System.out.print(student + " ");
        }
    }
}