[코딩테스트] 백준 2605: 줄 세우기 - 자바(JAVA)

https://www.acmicpc.net/problem/2605

문제

점심시간이 되면 반 학생 모두가 한 줄로 줄을 서서 급식을 탄다. 그런데 매일 같이 앞자리에 앉은 학생들이 앞에 줄을 서 먼저 점심을 먹고, 뒷자리에 앉은 학생들은 뒤에 줄을 서 늦게 점심을 먹게 된다. 어떻게 하면 이러한 상황을 바꾸어 볼 수 있을까 고민하던 중 선생님이 한 가지 방법을 내놓았다. 그 방법은 다음과 같다.

학생들이 한 줄로 줄을 선 후, 첫 번째 학생부터 차례로 번호를 뽑는다. 첫 번째로 줄을 선 학생은 무조건 0번 번호를 받아 제일 앞에 줄을 선다. 두 번째로 줄을 선 학생은 0번 또는 1번 둘 중 하나의 번호를 뽑는다. 0번을 뽑으면 그 자리에 그대로 있고, 1번을 뽑으면 바로 앞의 학생 앞으로 가서 줄을 선다. 세 번째로 줄을 선 학생은 0, 1 또는 2 중 하나의 번호를 뽑는다. 그리고 뽑은 번호만큼 앞자리로 가서 줄을 선다. 마지막에 줄을 선 학생까지 이와 같은 방식으로 뽑은 번호만큼 앞으로 가서 줄을 서게 된다. 각자 뽑은 번호는 자신이 처음에 선 순서보다는 작은 수이다.

예를 들어 5명의 학생이 줄을 서고, 첫 번째로 줄을 선 학생부터 다섯 번째로 줄을 선 학생까지 차례로 0, 1, 1, 3, 2번의 번호를 뽑았다고 하자, 첫 번째 학생부터 다섯 번째 학생까지 1부터 5로 표시하면 학생들이 줄을 선 순서는 다음과 같이 된다.

• 첫 번째 학생이 번호를 뽑은 후 : 1
• 두 번째 학생이 번호를 뽑은 후 : 2 1
• 세 번째 학생이 번호를 뽑은 후 : 2 3 1
• 네 번째 학생이 번호를 뽑은 후 : 4 2 3 1
• 다섯 번째 학생이 번호를 뽑은 후 : 4 2 5 3 1

따라서 최종적으로 학생들이 줄을 선 순서는 4, 2, 5, 3, 1이 된다.

줄을 선 학생들이 차례로 뽑은 번호가 주어질 때 학생들이 최종적으로 줄을 선 순서를 출력하는 프로그램을 작성하시오.

 

해결 

문제분석

• 공정한 줄 세우기를 위한 문제이다.
• 번호표를 뽑은 학생들이 뽑은 번호에 따라 특정 위치에 삽입된다.
  • 단, 가장먼저 온 학생은 무조건 0을 받아 제일 앞에서 시작한다.
  • 두 번째 학생은 0,1 세 번째 학생은 0,1,2 식으로 뽑을 수 있으며 나온 숫자만큼 앞으로 가서 줄을 서게 된다.

문제풀이

• ArrayList 자료구조를 활용해 문제를 접근하였다.
• ArrayList.add(index, element) 메서드를 이용해 중간 삽입을 처리하였다.
• 현재 자기의 순서 i 에서 나온 input 값을 빼서 특정 위치의 값을 구하였다. (문제에 주어진 입력이 0부터 시작하는 인덱스 값 형태이기 때문에 특별한 처리 없이 계산 가능)
• 출력값의 경우 1부터 시작해야되므로 i+1 형태로 값을 넣어줬다.

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

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());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int input = Integer.parseInt(st.nextToken());
            list.add(i - input, i + 1);
        }

        for (Integer output : list) {
            System.out.print(output + " ");
        }
    }
}

메모리 시간

14192

108

 

회고 

중간 삽입이 일어나는 문제이기 때문에 LinkedList가 더 적합해 보였는데 난이도가 낮은 문제다 보니 둘의 속도차이가 크지 않아 그냥 ArrayList를 사용했다. 

 

ArrayList

• 내부적으로 배열로 구현되어 있습니다.
• 삽입/삭제 시, 요소를 이동해야 하는 경우가 발생합니다.
  • 삽입: 특정 위치에 삽입하려면 그 위치 이후의 모든 요소를 한 칸씩 뒤로 이동.
  • 시간 복잡도: O(N) (평균 및 최악의 경우, 특정 위치에 삽입 시)
  • 특이점: 삽입이 빈번할수록 성능이 저하됨.

LinkedList

• 내부적으로 이중 연결 리스트로 구현되어 있습니다.
• 삽입/삭제 작업은 노드 간의 링크만 수정하면 되므로 빠릅니다.
  • 삽입: 특정 위치를 탐색한 후, 노드 링크 변경.
  • 시간 복잡도:
    • 탐색: O(N) (인덱스를 찾기 위해 노드를 순회해야 함)
    • 삽입: O(1) (탐색 후 노드 삽입 작업)