[자료구조] 배열과 리스트

배열이란?

• 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조
• 인덱스를 통해 참조할 수 있고, 선언한 자료형의 값만 저장 가능
• 새로운 값을 "중간"에 삽입하거나, 특정 인덱스 값 없앤 후 땡기기 어려움 (나머지 모든 값을 하나씩 밀거나 땡겨야함)
• 크기를 선언할 때 지정하기에 이후에 늘리거나 줄일 수 없음

---

리스트란?

• 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조
• 인덱스가 없어서 값에 접근하려면 head 포인터부터 순서대로 접근해야함 (=접근속도 느림)
• 포인터로 연결되어 있으므로 데이터 삽입, 삭제 연산은 빠름
• 크기를 별도로 지정하지 않기에 크기가 변하기 쉬운 데이터를 다룰 때 적절하다
• 포인터를 저장할 공간이 따로 필요해서 배열에 비해 구조가 조금 복잡함

직접 리스트를 구현하는 경우는 드물다.
자바에선 ArrayList나 LinkedList등 이미 구현되어있는 리스트 사용하는 경우가 다수

---

그래서 코딩테스트에선 무슨 둘 중 무슨 자료구조 써야하는지 어떻게 정하는데?

• 크기 fix && 데이터 접근하는 경우가 많다? => 배열
• 크기가 변하는 경우나 || 데이터 삽입, 삭제가 많다? => 리스트

---

실전! 문제 풀이(백준 11720)

import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner scanner= new Scanner(System.in);
        int n = scanner.nextInt();
        String input = scanner.next();
        char[] inputToCharArray = input.toCharArray();
        int sum=0;
    
        for(int i=0; i<n ;i++){
            sum += inputToCharArray[i]-'0';
        }
        System.out.println(sum);
    }
}

얻어갈 점:

• 문제보고 로직이 바로 떠오른다고 바로 코드 작성하지 말고, 문제 꼼꼼히 읽어보고 빠트린 점은 없는지 등 체크하기!(n범위가 100까지이므로, int형,long형과 같은 숫자형으로 담을 수 없었다!)

• 문자열로 받고 그걸 문자형 배열(toCharArray)로 바꿔서 풀어볼까?

• 문자열을 받을땐 scanner.next() / 숫자를 받을땐 scanner.nextInt()

• 아스키 코드: 문자형을 숫자형으로 변경하려면 아스키코드를 이해해야한다. 아스키코드에서 같은 의미의 문자와 숫자의 코드 값 차이는 48
  ex) 문자 '1'은 아스키 코드 값이 49이므로 문자 '1'을 숫자 1로 변환하려면 '1'-48 or '1'-'0'으로 연산해야함

---

실전! 문제 풀이(백준 1546)

import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        double[] score = new double[n];
        double maxScore = 0.0;
        
        for(int i=0; i<n; i++){
            score[i] = sc.nextDouble();
            if(maxScore<score[i]){
                maxScore = score[i];
            }
        }
        
        double sum = 0.0;
        double average = 0.0;
        for(int i=0; i<n ;i++){
           score[i]= (score[i] / maxScore * 100);
            sum += score[i];
        }
        average = sum/n;
        System.out.print(average);
        
    } 
}

얻어갈 점: 값을 입력받고 최대값을 구하는 로직을 따로 둘 것이 아니라, 값을 입력받고 그때 입력받은 값과 최대값을 비교해서 한 번에 저장해놓는 것이 코드가 간결해진다.