[알고리즘] 배열과 리스트(백준 11720, 1546)

[알고리즘] 배열과 리스트(백준 11720, 1546)

알고리즘 공부를 계속 미루는 제 자신을 보고 이대로는 안되겠다 싶어 😇
본격적으로 코딩테스트를 준비(+알고리즘 공부) 해보려고 합니다.
물론 혼자하면 작심삼일이 될거 같아
무료 Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의
강의 커리큘럼에 맞춰 공부해보자!!

[무료] Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의

 

자 모든 준비와 마음이 섰으니 기초부터 차근차근 공부해보자!

---

 

오늘은 기본 자료구조인 배열과 리스트에 대해서 공부해보자!
배열과 리스트는 비슷한 점도 많지만 다른점도 많습니다.
벌써 이름부터 다르다는 것을 알수 있습니다… ㅎㅎ
두 자료구조에 대한 정확한 개념을 알아보자!

 

 

배열

배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 입니다.
배열의 값은 인덱스(index)를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있습니다.

배열의 구조는 매우 단순합니다.
int[] array = new int[3];식으로만 하면 배열이 생성된 거죠!
(주의해야 할 점은 인덱스(index)는 0부터 시작한다는 것 입니다.)
눈치 채신분도 있겠지만 배열은 한번 선언하면 배열의 크기를 줄이거나 늘릴수 없습니다.(런타임 시점에도 배열의 크기는 고정됩니다.)

배열은 인덱스를 통해 바로 값에 접근할 수 있습니다. (O(1)의 시간복잡도를 갖고 있습니다.)
배열은 새로운 값을 삽입하거나 삭제 하려면 해당 인덱스 주변에 있는 값을 이동시켜야 합니다.

int[] array = new int[4];
array[0] = 1; // 인덱스 0에 1 저장
array[1] = 2; // 인덱스 1에 2 저장
array[2] = 3; // 인덱스 2에 3 저장

/**
 * 1과 2 사이에 100이라는 숫자를 넣고 싶다면?
 * -> 인덱스1 부터 오른쪽으로 한칸씩 이동시킨다.
 */
array[3] = array[2];
array[2] = array[1];
array[1] = 100;

for (int i = 0; i < array.length; i++) {
    // 인덱스를 통해 바로 접근
    System.out.println("array["+i+"]="+array[i]);
}

배열의 특징

• 구조가 매우 단순
• 인덱스를 통해 값에 바로 접근
• 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어려움
  • 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요함
• 배열의 크기는 선언할 때 지정해야함
  • 한번 선언된 배열의 크기를 늘리거나 줄일수 없음

리스트(LinkedList)

리스트는 값과 포인터를 묶는 노드(값, 포인터를 쌍으로 갖는 기초 단위)라는 것을 포인터로 연결한 자료구조 입니다.
(여기서 설명하는 리스트는 java의 LinkedList를 의미합니다.)

 

리스트의 특징

• 인덱스가 없기 때문에 값에 접근하려면 Head 포인트부터 순서대로 접근해야함
  • 접근 속도가 느림
• 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠름
• 선언할 때 크기를 별도로 지정하지 않아도 됨
  • 리스트의 크기는 런타임 시점에 변경이 가능
• 배열보다 구조가 복잡
  • 포인터를 저장할 공간이 필요하기 때문

 

 

아마 ArrayList를 많이 사용할꺼 같은데, ArrayList 선언할때 크기를 별도로 지정하지 않아도 됩니다.

하지만, ArrayList는 배열을 사용하기 때문에 크기에는 한계가 있습니다.

어떻게 ArrayList는 어떻게 동적으로 사이즈가 늘어나는지 궁금하신 분들은 아래 블로그를 참조하면 좋을것 같습니다.^^

https://junghyungil.tistory.com/96

[Java] ArrayList는 어떻게 동적으로 사이즈가 늘어나는가? add() flow(동작 방식)

 

위 블로그의 내용의 결론은 다음과 같습니다. 

ArrayList 기본 생성자를 통해 사용 하고 있을 경우를 생각 해보면 element 배열 크기가 0 이기 때문에
첫 element 를 add 할때 배열의 resize 가 발생하고 배열 크기는 10 으로 설정 됩니다.
이후 ArrayList 에 10개의 데이터가 있고 데이터를 추가 하려고 하면 resize 가 발생하여 15 가 됩니다.
이렇게 임의의 capacity 를 설정하지 않는 일반적인 상황에서는 10 -> 15 -> 22 -> 33 -> 49 .... 로 배열 사이즈가 조정 된다.

일반적인 상황에서 기존의 용량 + 기존 용량/2 만큼 크기가 늘어난 배열에 기존 elementData를 copy한다.

실제로는 가지고 있던 용량이 꽉 찼을 때, 용량이 기존의 1.5배를 늘린 새로운 배열에 기존 배열을 copy하는 것이다. 

백준 11720

11720번: 숫자의 합

11720번: 숫자의 합

 

문제를 보면 N의 범위가 1 ~ 100 입니다.
이는 int, long 형과 같은 숫자형으로 담을수 없다는 것을 의미합니다.
(‘0’은 아스키코드로 48 입니다.)

public class Quiz11720 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        // N의 범위가 1 ~ 100(int, long 형 불가)
        // String으로 저장
        String num = br.readLine();

        // String을 char로 변환
        char[] chars = num.toCharArray();
        int sum = 0; // 결과

        for(int i = 0; i < size; i++) {
            sum += Integer.parseInt(Character.toString(chars[i]));
              // sum += (chars[i] - '0'); // 아스키코드를 알면 이렇게 해도 좋다.
              // sum += (chars[i] - 48); // 아스키코드를 알면 이렇게 해도 좋다.
        }

        System.out.println(sum);
    }
}

 

굳이 char[] chars = num.toCharArray();을 사용하지 않고
String의 charAt(index)을 사용해도 됩니다.
charAt(index)은 문자열의 index에 해당하는 값을 char로 반환 합니다.

for(int i = 0; i < size; i++) {
    sum += Integer.parseInt(String.valueOf(num.charAt(i)));
    // sum += (num.charAt(i) - '0 '); // 아스키코드를 알면 이렇게 해도 좋다.
}

 

결과

백준 1546

1546번: 평균
구현을 마치고 틀렸습니다로 확인되서 조금 헤맸는데 결과 값을 float로 해야하기 때문입니다.(모든 문제를 항상 주의깊게 보자!🧘🏻)

1546번: 평균

 

풀이
저는 stream을 활용하여 문제를 풀었습니다.
(size로 입력받은 값과 문자열을 나눈 배열의 길이와 다르면 IllegalArgumentException이 발생하도록 했습니다.)

public class Quiz1546 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        String score = br.readLine();

        // " "으로 문자열 나누기
        String[] scoreArr = score.split(" ");
        if(size != scoreArr.length) throw new IllegalArgumentException();
        System.out.println(getAVGNewScore(scoreArr));
    }

    public static float getAVGNewScore(String[] score) {
        // String to Integer
        List<Integer> intArrayScore = Arrays.stream(score)
                .map(Integer::parseInt)
                .collect(Collectors.toList());

        // 최댓값 구하기
        int maxScore = intArrayScore.stream()
                .mapToInt(Integer::intValue)
                .max()
                .orElseThrow(NoSuchElementException::new);

        // 합 구하기
        int sum = intArrayScore.stream()
                .mapToInt(Integer::intValue)
                .sum();

             // 일일이 변환 점수를 구하지 말고 총합을 이용해서 평균점수를 구함
        // 100f로 곱하여 float를 반환하게 한다.
        return  (sum * 100f / maxScore) / intArrayScore.size();
    }
}

 

하나의 루프에서 max값과 sum을 계산하는 방법도 있습니다.

public class Quiz1546 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        int[] score = new int[size];
        // StringTokenizer 객체 선언
        // "1 3 5 7" 식으로 공란 포함 String Line일시 StringTokenizer 이용
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < size; i++) {
            score[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(getAvgNewScore2(score));
    }

    public static float getAvgNewScore2(int[] score) {
        long sum = 0;
        long max = 0;

        // max와 sum 계산
        for(int i = 0; i < score.length; i++) {
            if(score[i] > max) {
                max = score[i];
            }
            sum += score[i];
        }

        return (sum * 100f / max) / score.length;
    }
}

 

결과
stream을 사용한것이 20ms 정도 더 느린것을 알수 있습니다.