배열과 리스트

1. 배열

- 메모리의 연속적인 공간에 값이 채워져 있는 형태의 자료구조
- 인덱스를 통해 참조를 할 수 있음

- 특징
  - 인덱스를 통해 바로 접근
  - 값을 삽입 or 삭제가 어려움 _ 다른 값들을 이동하여 배열값을 변경 가능함 _ 즉, 특정 인덱스의 배열값을 변경하는 것은 어려움
  - 배열 크기를 선언한 후에는 수정이 불가능함
  - 구조가 간단하여 코딩테스트에 많이 사용된다.

- 데이터 크기가 고정되어 있는 경우
- 데이터 접근이 잦은 경우 사용

2. 리스트

- 값과 포인터를 묶어 노드라는 것을 포인터로 연결한 자료구조
- 자기 자신의 값 + 다음 값의 주소를 가리키는 포인터

- 특징 
  - 접근하려면 head 포인터부터 순서대로 접근해야해서 접근하는 속도가 느림
  - 데이터 삽입 삭제 연산 속도가 배열보다 빠름 -> 포인터만 수정하면 가능
  - 리스트의 크기는 정해져있지 않고 추후에 수정이 가능함
  - 포인터 저장 공간이 필요하기에 배열보다 구조가 복잡함
  - 실제로 코딩테스트에서 리스트를 구현하는 경우는 거의 없음 _ ArrayList 사용함, LinkedList 사용함

- 데이터의 크기가 가변적인 경우
- 데이터의 삽입, 삭제가 잦은 경우

3. 문제풀이

- 백준 배열 문제 11720번

시간 제한은 1초로 최대 n 값으로 100을 넣었을때 1억번 이하의 연산을 하는 알고리즘을 작성해야 한다.

문제를 보면 최대 100 자리 숫자를 입력받을 수 있다. 하지만 long 자료형도 최대 19자리까지 받을 수 있으므로 숫자형이 아닌 문자형으로 입력을 받는다.

---

1. string 으로 문자열 입력을 받음

2. toCharArray 함수로 문자열 배열로 변경함

3. 각 문자열을 숫자값으로 변환

4. sum 변수에 변환값을 더하여 정답을 구할 수 있다.

정답코드

 

import java.util.Scanner;

class No_11720 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long input = sc.nextInt();
        String num = sc.next();
        // input 수 이상 입력 시 error
        if (num.length() > input) {
            System.out.println("입력 수에 맞게 입력해주세요.");
            return ;
        } else {
            char[] numbers = num.toCharArray();
            long sum = 0;
            for (int i = 0; i < input; i++) {
                sum += numbers[i] - 48;
            }
            System.out.println(sum);
        }
    }
}

 

- 백준 배열 문제 1546번

기말고사 점수 컨셉으로 기말고사에서 가장 높은 점수 값으로 모든 기말고사 점수를 나누어 100을 곱한 값의 평균값을 구하는 것이다. 

수식으로 생각하면 이해하기 편해진다. 

즉, 기말고사 점수 A, B, C 값을 받았고 C 값이 최대값이라면 ((A / C * 100) + (B / C * 100) + (C / C * 100)) / 3 값을 구하는 문제이다. 해당 수식의 공통부분을 꺼내 수식을 간단히 만들면 (A + B + C) * 100 / C / 3 이다.

---

1. 총 기말고사의 점수 개수를 변수에 받은 후 해당 변수 값을 갖는 배열 생성

2. 입력 받은 기말고사 점수를 배열에 넣고 sum 값에 더함

3. 기말고사 점수들 중에서 가장 큰 값을 찾음

4. 수식에 맞는 값 계산

정답 코드

import java.util.Scanner;

class No_1546 {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();
        long scores[] = new long[(int) input];

        long sum = 0;
        for (int i = 0; i < input; i++) {
            scores[i] = sc.nextInt();
            sum += scores[i];
        }
        // 가장 큰 수 찾기
        long max = 0;
        for (int i = 0; i < input; i++) {
            if (scores[i] > max) { max = scores[i]; }
        }
        System.out.println(sum * 100.0 / max / input);

    }
}