1.Java로 LinkedList를 직접 구현해보고 블로그에 동작원리 정리
- 구현되어야 하는 LinkedList Class의 기능
- 새로운 노드 끝에 추가
- 특정 위치에 노드 삽입
- 특정 위치의 노드 삭제
- 특정 위치의 노드 가져오기
- 크기 반환
- 리스트 전체 출력
- main 메소드에서 사용자가 정의한 LinkedList Class를 선언하고, 각각의 기능 사용해보기
public class LinkedList {
static class Node<T>{ //static붙여야 main에서 객체 생성안하고 바로 접근가능
T data;
Node<T> next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
static public class CustomLinkedList<T> {
private Node<T> head;
private int size;
public CustomLinkedList() {
this.head = null;
this.size = 0;
}
public void add(T data) {
Node<T> newNode = new Node<>(data);
if (head == null) {
head = newNode;//노드가 없으면 새로운 노드가 헤드
} else {
Node<T> temp = head;//움직일 temp의 출발점을 맨앞 노드로 지정
while (temp.next != null) {//temp의 다음노드가 비어있지 않을떄까지(끝에서 두번째)이동
temp = temp.next;//맨 마지막으로 이동
}
temp.next = newNode;//맨 마지막 뒤에 위에서 만든 노드 추가
}
size++;
}
public T get(int index) {
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node <T> temp = head;//위랑 마찬가지
for (int i = 0; i<index; i++){//주어진 index전까지 이동
temp = temp.next;//다음칸으로 이동(인덱스가 이동하는게 아니라 다음칸으로 이동이 index만큼 반복)
}
return temp.data;//거기 값 읽어오기
}
public void insert(int index, T data){//return값 없음
Node<T> newNode = new Node<>(data);
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
if(index == 0){
newNode.next = head;//인덱스 0이면 맨앞에 추가하고
head = newNode;//새 노드가 헤드가 됨
}else{
Node <T> temp = head;
for (int i = 0; i<index-1; i++){//주어진 index전까지 이동
temp = temp.next; // 주어진 index의 전 노드
}
newNode.next = temp.next;//새노드의 다음을 원래노드의 다음으로 바꾸기
temp.next = newNode;//원래노드의 다음을 새노드로
}
size++;
}
public void delete(int index){//return값 없음,안비우고 끊기만 하면 됨
//Node<T> newNode = new Node<>(data);
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
if(index == 0){
head = head.next;//헤드 다음노드가 헤드됨
}else{
Node <T> temp = head;
for (int i = 0; i<index-1; i++){//주어진 index전까지 이동
temp = temp.next; // 주어진 index의 전 노드
}
temp.next = temp.next.next;
}
size--;
}
public void getSize(){
System.out.println(size);
}
public void getList() {
//CustomLinkedList<Integer> list = new CustomLinkedList<>();
for(int i=0;i<size;i++){
System.out.println(get(i));
}
}
}
public static void main(String[] args) {
CustomLinkedList<Integer> list = new CustomLinkedList<>();
System.out.println("--노드 추가--");
list.add(10);
list.add(20);
list.add(30);
list.getList();
System.out.println("--원하는 위치에 삽입--");
list.insert(2,50);
list.getList();
System.out.println("--삭제--");
list.delete(1);
list.getList();
System.out.println("--크기--");
list.getSize();
}
}
1)add
-새로운 노드 선언
-만약 노드가 없다면 새로운 노드가 헤드
-움직일 temp의 출발점을 맨앞 노드로 지정
-temp가 다음노드가 비어있지 않을때까지 이동(맨마지막)
-맨 마지막 뒤에 노드 추가
2)get
-add와 동일하게 맨마지막까지 이동
-그 값 읽어오기
3)insert
-인덱스 0이면 맨앞에 추가하고 새 노드가 헤드
-주어진 index의 전 노드까지 이동후 새노드의 다음을 원래 노드의 다음으로 ㅂ꾸기
-원래 노드의 다음을 새노드로
4)delete
-헤드 다음노드를 헤드로
-주어진 index전까지 이동
-원래 노드의 다음노드를 원래 노드와 원래노드의 다다음노드와 연결
5)getSize
-지금까지 사용한 size출력
6)getList
-get메소드로 반복문 이용하여 출력
문제 1 : 스택
- 링크 : https://www.acmicpc.net/problem/10828
문제 2 : 큐
- 링크 : https://www.acmicpc.net/problem/10845
문제 3 : 최소 힙
- 링크 : https://www.acmicpc.net/problem/1927
문제 4 : 듣보잡
- 링크 : https://www.acmicpc.net/problem/1764
문제 5 : 괄호
- 링크 : https://www.acmicpc.net/problem/9012
문제 2 : 큐_10845
import java.util.*;
public class Queue_10845 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
//Queue<Integer> queue= new LinkedList<>();
//이렇게 하면 리스트 기능에서 큐 기능만 쓸거라는 뜻
LinkedList<Integer> queue= new LinkedList<>();
//이렇게 해야 이따 reverse같은 형변환시 문제가 없음
for(int i = 0 ; i < n ; i++){
String order = scan.next();
switch (order){
case "push":
int x = scan.nextInt();
queue.offer(x);//add()
break;
case "pop":
if(queue.isEmpty()){
System.out.println(-1);
}else{
System.out.println(queue.poll());//poll:remove+값 반환
}
break;
case "size":
System.out.println(queue.size());
break;
case "empty":
if(queue.isEmpty()){
System.out.println(1);
}else{
System.out.println(0);
}
break;
case "front":
if(queue.isEmpty()){
System.out.println(-1);
}else{
System.out.println(queue.peek());//element()
}
break;
case "back":
if(queue.isEmpty()){
System.out.println(-1);
}else{
System.out.println(queue.getLast());
}
break;
}
}
}
}문제1의 스택문제와 유사하게 구현
back기능 구현할때 reverse를 두번 했는데 시간초과 -> getLast()메소드 사용
push : offer로 큐에 붙이기
pop : poll로 뒤에꺼 지우기
size : size메소드 사용
empty : isEmpty()메소드 사용
front : peek()메소드로 앞의 요소 확인
back : getLast()메소드로 마지막 요소확인
문제 4 : 듣보잡_1764
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.HashSet;
public class NotHeard2_1764 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();//못들어본 사람
int m = scan.nextInt();//못본사람
//배열 말고 HashSet-더빠름
HashSet<String> set = new HashSet<>();
//못들은사람저장
for(int i = 0; i < n; i++){
set.add(scan.next());
}
ArrayList<String> list_seen = new ArrayList<>();
for(int i = 0; i < m; i++){
String name = scan.next();
if(set.contains(name)){//contain으로 있는지만 확인
list_seen.add(name);
}
}
Collections.sort(list_seen);
System.out.println(list_seen.size());
for(String s : list_seen){
System.out.println(s);
}
}
}듣잡 먼저 배열에 저장하고 보잡으로 받은게 듣잡의 요소에 있으면 새로운 배열에 저장한 후 탐색하려 했으나 시간초과
->집합(set) 사용
hashset으로 듣잡 저장한 후 같은 방법으로 보잡으로 받은 이름이 집합에 있으면 리스트에 보잡 이름 리스트에 저장
배열은 처음부터 원하는 값까지 탐색해야하나 집합은 contain으로 존재하나 여부만 확인이 가능하기에 시간이 덜 걸림
문제 5 : 괄호_9012
import java.util.Scanner;
import java.util.Stack;
public class VPS2_9012 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt(); // 테스트 케이스 수 입력
scan.nextLine(); // 개행 문자 제거
for (int i = 0; i < n; i++) {
String VPS = scan.nextLine(); // 각 테스트 케이스 입력
Stack<Character> stack = new Stack<>(); // 스택 생성
boolean isValid = true; // 유효성을 확인할 변수
for (int j = 0; j < VPS.length(); j++) {
char ch = VPS.charAt(j);
if (ch == '(') {
stack.push(ch); // 열린 괄호는 스택에 푸시
} else if (ch == ')') {
if (stack.isEmpty()) {
isValid = false; // 닫힌 괄호가 나왔지만 스택이 비어있으면 잘못된 VPS
break;
} else {
stack.pop(); // 스택이 비어있지 않으면 열린 괄호와 짝이 맞으므로 팝
}
}
}
// 문자열을 다 처리한 후 스택이 비어있어야 올바른 VPS
if (isValid && stack.isEmpty()) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
scan.close();
}
}
-열린괄호가 나오면 스택에 넣고 닫힌괄호가 나오면 스택에서 빼면서 검사
닫힌 괄호가 나왔으나 스택이 비어있으면 에러
문자열 처리 후 스택이 비어있으면 vps,그렇지 않으면 no출력
'백엔드' 카테고리의 다른 글
| [백엔드]-4주차 과제 (0) | 2026.02.02 |
|---|