자바 코딩 테스트 - 배열과 리스트, 백준 11720, 1546 문제

'Do it! 알고리즘 코딩테스트 자바 편' 교재로 공부한 내용을 정리했습니다.

 

배열과 리스트

배열

• 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조

https://jenkov.com/tutorials/java/arrays.html

배열의 특징

• Index 을 사용하여 값에 바로 접근할 수 있다.
• 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입/삭제 하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.
• 배열의 크기는 선언할 때까지 지정할 수 없으며 한 번 선언하면 크기를 늘리거나 줄일 수 없다.
• 구조가 간단하여 코딩 테스트에서 많이 사용한다.

 

리스트

• 값과 포인터를 묶은 ‘노드’를 포인터로 연결한 자료구조

https://www.careerride.com/page/linked-list-for-computer-science-and-mca-students-624.aspx

리스트의 특징

• 인덱스가 없어서 값에 접근하려면 Head Pointer 에서부터 순서대로 접근해야 한다.
• 포인터로 연결되어 있으므로 데이터 삽입/삭제 하는 연산 속도가 빠르다.
• 선언할 때 크기를 별도로 지정하지 않아도 된다. 즉, 크기가 정해져 있지 않으며 크기가 변하기 쉬운 데이터를 다룰 때 사용하는 것이 적합하다.
• 포인터를 저장할 별도의 공간이 필요하고 배열보다 구조가 복잡하다.

자료 구조 배열, 리스트에 관한 백준 문제 11720번, 1546 번을 풀어봅시다.

백준 11720번: 숫자의 합

11720번: 숫자의 합

1. 문제 분석
   • N개의 범위 → 1 ~ 100 ⇒ 값을 int 나 long 형 등의 숫자 타입으로 담을 수 없다.
   • 그렇기 때문에 먼저 문자열 형태로 입력값을 받은 후 이를 문자 배열로 변환하자, 그 후 문자 배열값을 순서대로 읽으면서 숫자형으로 변환하고 누적하여 더하자!
   • Ex) “1234”(문자열) → ‘1’, ‘2’, ‘3’, ‘4’(문자 배열) → 1, 2, 3, 4 (숫자) → 10 (덧셈)
2. 손으로 풀기
   1. 숫자의 개수만큼 입력받은 값을 String 타입으로 저장. String sNum = 10987654321
   2. sNum 을 char[] 형으로 변환.
   3. Index 0 부터 끝까지 배열을 탐색하며 각 값을 정수형으로 변환하고 결과값에 더하여 누적 덧셈하자.
3. 슈도 코드 작성

N 값 입력 받기
길이가 N인 값을 숫자로 입력받아서 String sNum 에 저장.
sNum 을 char[] cNum 에 변환하여 저장.
int sum = 0;
for(cNum 길이만큼 반복){
	배열의 각 자리값을 정수형으로 변환.
	sum에 더하여 누적하기
}
sum 출력.

 

4. 구현

public class BaekJoon11720 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 수 개수

        String sNum = sc.next(); // 수 문자열
        char[] cNum = sNum.toCharArray(); // 문자 배열로 변환
        int sum = 0;

        for (int i = 0; i < cNum.length; i++) {
            // 아스키 코드에서 문자 0 ~ 9 는 48 ~ 57 이다. 즉, 문자 '0' 의 아스키코드를 빼주면 문자형인 숫자가 정수형으로 변환된다.
            sum += (cNum[i] - '0'); // 정수로 변환해서 더하기
//            자바의 라이브러리중의 Character.getNumericValue() 함수를 사용하여 문자형인 숫자를 정수형으로 변환
//            sum += Character.getNumericValue(cNum[i]);

        }
        System.out.println(sum);
    }
}

 

 

백준 1546번 평균

1546번: 평균

1546번: 평균

1. 문제 분석
   • 모든 점수를 입력받은 후에 최고점을 별도 저장. → 반복문
   • 한 과목의 점수 계산식이 원래 → 점수 / M *100 
     그런데 모든 과목 조작 점수의 계산식도 만들 수 있다.
   • 만약 점수가 10, 20, 30 이면
     • ( 10 / M * 100 + 20 / M * 100 + 30 / M * 100 ) / 3 = (10 + 20 + 30) * 100 / M / 3
     • 조작된 각 과목의 점수를 따로 구할 필요가 없으니까 이렇게 합쳐서 하자.
2. 손으로 풀기
   1. 점수를 1차원 배열에 저장.
   2. 배열에서 최고점, 점수 총합 찾기
   3. 총합 * 100 / 최고점 / 과목 수 구하기
3. 슈도 코드

변수 N 에 과목 수 입력받기
길이가 N 인 1차원 배열 iArr[]

for ( iArr[] 길이만큼 반복){
	M 과 iArr[] 비교 -> 최고점 저장
	sum 에 총점 저장
}
sum * 100 / M / N 출력.

 

 4. 구현

public class BaekJoon1436 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 과목 수
        float iArr[] = new float[N];
        long M = 0; // 최고점
        float sum = 0; // 원래 점수 총합

        // 각 과목 점수 저장
        for (int i = 0; i < N; i++) {
            iArr[i] = sc.nextInt();
        }

//        최고점 M 찾고 sum 에 과목 점수 총합 저장
        for (int i = 0; i < N; i++) {
            if (iArr[i] > M) {
                M = (int) iArr[i];
            }
            sum += iArr[i];
        }

        float result = (sum * 100 / M / N);
        System.out.println(result);

    }

}