자바 알고리즘 Datastructure

1. List

 

: 데이타를 저장한 순서대로 저장해 준다.

데이타의 Index는 0부터 size()-1

 

중간 삽입할 수 있는 Index는 0부터 size()까지 이다.

 

범위를 벗어나면 IndexOutOfBoundsException이 발생한다.

 

데이타를 중복해서 저장할 수 있다.

 

inndexOf(Object o), lastIndexOf(Object o), contains(Object o)

remove(Object o)에서 해당 기능을 수행하기 위해

=> equals(Object o)를 호출해서 객체가 같은지 비교후 처리한다.

     equals함수가 구현 할려면 해당 타입인지 검사  

public boolean equals(Object obj) {
		if (obj instanceof Employee) { //instanceof가 null검사도 한다 
			Employee emp = (Employee) obj;
			if( empno != null && empno.equals(emp.empno)) {
				return true;
			}
		}
		return false;

 

2. ArrayList

 

-List 배열로 구성

- 데이터를 추가, 삭제시 내부에서 동적으로 배열의 길이를 조절 해준다

-연속적인 데이터의 리스트

- 중간에 빈 공간이 생기지 않도록 요소들의 위치를 앞뒤로 이동

: 순서대로 하나씩 추가한다면 상관이 없지만, 중간에 삽입이 들어가면 맨끝에서 부터 하나씩 이동하면서 공간을 마련

삽입이 일어난 공간부터 맨 아래까지 이동이 나타남

삭제도 동일하게 비워진 공간에 대하여 다시 아래서 공간이 채워지고 아래서 다시 채워지고 반복

 

- 삽입 삭제 하기 전 Overhead 발생!!

- 배열로 구성했기 때문에 원하는 것을 탐색하고 순서대로 삽입하는 것은 빠름

 

일반적인 크기를 알고 있다면 intialCapacity를 통해 버리는 메모리가 없게 활용 가능

=>크기를 알고 있을 때 활용하기 좋음

 

 *요소삽입

ArrayList<Integer> members = new ArrayList<>();

 

 

!Array의 경우 처음 선언한 배열의 크기를 변경 할 수 없고,

데이터를 삭제하더라도 해당 index에는 빈공간으로 계속 남는다.

 

3. LinkedList

: ArrayList와 다르게 LinkedList는 각각의 노드를 연결하는 방식을 사용

 

LinkedList는 Node라는 객체로 이루어져 있으며

Node는 데이터를 저장하는 field와 다음 노드를 가리킬 수 있는 next pointer field로 구성이 되어있다

 

이 노드들이 연결된 형태의 자료구조를 바로 LinkedList 이다

 

삽입 삭제의 경우 노드가 가리키는 포인터만 바꾸어주면 되기 때문에

배열처럼 데이터를 이동하기 위해 복사하는 과정 없이 삽입/삭제가 매우 빠르게 가능하다.

 

하지만 순차접근만 가능하기 때문에 요소를 받아오는 속도가 매우 느립니다.

 

 ArrayList의 경우 원하는 것을 탐색하고 순서대로 삽입을 진행할 때

LinkedList의 경우 삽입과 삭제를 진행할 때 효율성입 높다.

 

4. Set

: 값들의 순서를 보장하지않고 중복되지 않는 자료구조

 

 동일한 객체를 저장하지 않음

=> 데이타의 유니크성을 보장

 

- add(Object o), contains(Object o), remove(Object o)에서

equals(Object o)와 hashCode()를 호출하여 객체가 같은지 비교한다.

 

-객체의 주소값을 리턴(hashCode)

 - 데이타를 저장한 순서대로 저장하지 않는다.

-  index가 없다.!!!!!

 

=> 순서에 상관없이, 어떤 데이터가 존재하는지를 확인하는 용도로 활용

 

5. treeset

 - set과 동일하게 유니크성을 보장하면서 tree를 이용해서 정렬을 유지한다.

==> 정렬시 Comparable interface의 compareTo()를 이용하므로

저장할 객체에 Comparable interface 구현해야 된다.

 

6. Map

- 유일한 key값으로 value를 관리하는 자료구조

- 검색이 가장 빠른 자료구조

 

7.Stack

 - 마직막에 저장한 데이타를 먼저 꺼내는 방식의 자료 구조(LIFO:Last Input First Out)

 ex) 쌓아 놓은 접시를 맨 위에부터 사용하는 방식

 

 - 컴퓨터의 연산 처리시 사용, 메서드 호출 처리에서 사용

- push(arg) : 맨 끝에 저장

 - pop() : 맨 끝에 있는 데이타를 제거 후 리턴

- peek() : 맨 끝에 있는 데이타를 제거 없이 리턴

- isEmpty() : 저장된 데이타가 있으면 false 없으면 true

 - size() : 저장된 데이타의 개수를 리턴

 - contains(데이타) : 해당 데이타가 stack에 저장되어 있으면 true, 없으면 false

 

8. Stack을 활용한 문제풀이

 

 

 

package boj.bronze;

import java.util.Scanner;
import java.util.Stack;

public class Main_g5_1141_불쾌한날 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // N: 배열의 크기
        int N = sc.nextInt();
        int[] data = new int[N];

        // 입력 받기
        for (int i = 0; i < N; i++) {
            data[i] = sc.nextInt();
        }

        // 스택을 사용하여 문제 해결
        Stack<Integer> stack = new Stack<>();
        stack.push(0); // 초기값으로 0을 넣어줌
        long count = 0;

        // 각 데이터에 대해 처리
        for (int i = 0; i < N; i++) {
            int a = data[i];

            // 스택의 top 값이 현재 값보다 작거나 같으면 pop
            while (!stack.isEmpty() && stack.peek() <= a) {
                stack.pop();
            }

            // 현재 스택의 크기만큼 count 증가
            count += stack.size();
            
            // 현재 값을 스택에 추가
            stack.push(a);
        }

        // 결과 출력
        System.out.println(count);

        sc.close();
    }
}

 

package boj.bronze;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main_2493_g5_탑_ {
    
    public static void main(String[] args) throws Exception {
        // 입력을 위한 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 탑의 개수 N
        int N = Integer.parseInt(br.readLine());

        // 탑의 높이 정보 입력받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] tower = new int[N];
        for (int i = 0; i < N; i++) {
            tower[i] = Integer.parseInt(st.nextToken());
        }

        // 결과를 저장할 배열
        int[] arr = new int[N];
        
        // 스택 초기화 (탑의 인덱스를 저장)
        Stack<Integer> stack = new Stack<>();
        
        // 각 탑에 대해 처리
        for (int i = 0; i < N; i++) {
            int a = tower[i];

            // 스택이 비어 있지 않고, 현재 탑의 높이가 스택의 top에 있는 탑보다 크면 pop
            while (!stack.isEmpty() && tower[stack.peek()] < a) {
                stack.pop();
            }

            // 스택에 탑이 남아있으면 그 탑의 인덱스를 arr[i]에 저장
            if (!stack.isEmpty()) {
                arr[i] = stack.peek() + 1; // 1-based index
            } else {
                arr[i] = 0; // 스택이 비어 있으면 0 저장
            }

            // 현재 탑의 인덱스를 스택에 push
            stack.push(i);
        }

        // 결과 출력
        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}