LinkedList: 유연하고 동적인 데이터 구조
자바에서 제공하는 LinkedList는 데이터를 연결하여 유연하고 동적인 구조를 제공하는 자료구조 중 하나이다.
LinkedList의 특징
-
연결 구조
LinkedList는 데이터를 노드(Node)로 나누어 각 노드가 이전 노드와 다음 노드에 대한 참조를 갖고 있는 연결 구조를 가지고 있다. 이로써 데이터의 삽입 및 삭제가 배열에 비해 효율적으로 이루어질 수 있다. -
크기의 동적 조절
배열과는 달리 LinkedList는 크기를 동적으로 조절할 수 있다. 데이터의 추가 및 삭제에 따라 리스트의 크기가 유연하게 변할 수 있다. -
노드 간의 참조
LinkedList는 각 노드가 이전 노드와 다음 노드에 대한 참조를 가지고 있기 때문에 특정 위치의 데이터에 빠르게 접근할 수 있다.
LinkedList 사용법 예시
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
// LinkedList 생성
LinkedList<String> linkedList = new LinkedList<>();
// 데이터 추가
linkedList.add("Apple");
linkedList.add("Banana");
linkedList.add("Cherry");
// 데이터 출력
System.out.println("LinkedList: " + linkedList);
// 데이터 삽입
linkedList.add(1, "Orange");
System.out.println("After inserting Orange: " + linkedList);
// 데이터 삭제
linkedList.remove("Banana");
System.out.println("After removing Banana: " + linkedList);
// 데이터 접근
String fruit = linkedList.get(2);
System.out.println("Accessing element at index 2: " + fruit);
}
}위 예시에서는 LinkedList를 생성하고 데이터를 추가, 삽입, 삭제하는 기본적인 동작을 보여준다. 또한 get 메서드를 사용하여 특정 인덱스의 데이터에 접근하는 방법도 확인할 수 있다.
LinkedList는 데이터의 삽입 및 삭제가 빈번하게 일어나는 상황에서 유용하게 사용될 수 있다. 그러나 데이터 검색에는 배열에 비해 상대적으로 느릴 수 있으므로 사용 시 주의가 필요하다.
이렇게 LinkedList는 자바에서 유연하고 동적인 데이터 구조를 구현할 수 있도록 도와주는 중요한 자료구조 중 하나이다.
백준 1158 요세푸스
문제 이해
주어진 문제인 백준 1158번은 Josephus problem을 다루는 문제이다. Josephus problem은 n명의 사람이 원을 이루고, 특정 순서로 m번째 사람을 계속해서 제거하는 과정을 나타낸다. 마지막으로 남는 사람들의 순서를 출력하는 문제이다.
예를 들어, n이 7이고 m이 3이라면 다음과 같은 과정이 진행된다.
1 2 3 4 5 6 7 (처음에는 1부터 n까지의 숫자가 원을 이룸)
1 2 4 5 6 7 (3이 제거됨)
1 2 5 6 7 (4가 제거됨)
1 2 6 7 (5가 제거됨)
1 2 7 (6이 제거됨)
1 2 (7이 제거됨)
1 (마지막으로 2가 제거됨)이 문제에서는 마지막에 남는 숫자들을 <와 >로 감싸서 출력해야 한다.
문제 해결 계획
-
큐 초기화: 1부터 n까지의 숫자를 큐에 넣어서 초기화한다. 이때 LinkedList를 사용하여 순환 큐를 구현한다.
-
순회하며 제거: 큐가 비어있을 때까지 반복하면서, 현재 위치(index)에서 m-1만큼 이동한 위치를 계산한다. 해당 위치에 있는 숫자를 큐에서 제거하고 출력한다.
-
결과 출력: 큐에 마지막 숫자만 남았을 경우에는 쉼표 없이 출력하고, 결과를 <와 >로 감싸서 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
// 입력 받기 위한 Scanner 객체 생성
Scanner sc = new Scanner(System.in);
// 인원 수와 제거될 순서의 간격 입력 받기
int n = sc.nextInt();
int m = sc.nextInt();
// 현재 제거될 순서의 위치를 나타내는 변수
int index = 0;
// LinkedList를 사용하여 원형 큐 구현
LinkedList<Integer> list = new LinkedList<>();
// 1부터 n까지의 숫자를 큐에 추가
for (int i = 1; i <= n; i++) {
list.offer(i);
}
// 결과 출력을 위한 초기화
System.out.print("<");
// 큐가 비어있을 때까지 반복
while (!list.isEmpty()) {
// 현재 위치(index)에서 m-1만큼 이동한 위치 계산
index = (index + (m - 1)) % list.size();
// 큐에서 해당 위치의 숫자를 제거하고 출력
if(list.size() != 1) {
System.out.print(list.remove(index) + ", ");
} else {
// 큐에 마지막 숫자만 남았을 경우에는 쉼표 없이 출력
System.out.print(list.remove(index));
}
}
// 결과 출력을 마무리
System.out.print(">");
}
}이러한 과정을 통해 Josephus problem을 해결할 수 있다. 큐를 사용하여 위치를 이동하고, 숫자를 제거하며 원형 구조를 시뮬레이션하는 방식으로 문제를 해결했다.
