[알고리즘] 2-1. 배열과 리스트

1. 배열과 리스트

(1) 배열

1. 인덱스를 통해 값에 바로 접근
2. 새로운 값의 추가나, 특정 위치의 값이 삭제가 어렵다 -> 직접 이동시켜서 넣어야한다. [우측 시프트 연산]
3. 배열의 크기를 변경 불가능하다.

 

(2) 리스트

1. 값과 포인터를 묶은 노드를, 포인터로 연결한 자료구조
2. 인덱스가 없다 -> 순서대로 접근 -> 조회가 느림
3. 포인터로 연결되어있어서, 데이터 삽입과 삭제가 빠름
4. 크기 별도 지정없이, 데이터 추가 및 삭제 가능
5. 포인터 저장 공간이 필요

---

문제 1. 숫자의 합 구하기

N개의 숫자가 공백 없이 써 있다. 이 숫자를 모두 합해 출력하는 프로그램을 작성하시오.

 

입력
1번째 줄에 숫자의 개수 N(1 <= N <= 100) ,2번째 줄에 숫자 N개가 공백 없이 주어진다.

출력
입력으로 주어진 숫자 N개의 합을 출력한다.

 

예제 입력 1

1 //숫자의개수
1 //공백없이주어진 N개의숫자

 

예제 출력 1

1

 

예제 입력 2

5
54321

 

예제 출력 2

15

 

예제 입력 3

25
7000000000000000000000000

 

예제 출력 3

7

예제 입력 4

11
10987654321

 

예제 출력 4

46

---

1단계. 문제 분석하기

: N의 범위가 1부터 100이므로, int형이나 long형인 숫자형으로 담을 수 없다

-> 문자열로 받아 배열로 변환 후 -> 순서대로 숫자형으로 변환해 더한다

 

2단계. 손으로 풀어보기

1. 숫자의 개수만큼 입력받은 값을 String 형으로 저장
2. String형으로 입력받은 값을 char[]형으로 변환
3. 인덱스 0부터 끝까지 배열을 탐색해, 각 값을 정수형으로 변환하고 결괏값에 더해 누적

3단계. 슈도코드 작성하기

N값 입력받기
길이 N의 숫자를 입력받아 String형 변수 sNum에 저장하기
sNum을 다시 char □형 변수 eNum에 변환하여 저장하기
int형 변수 sum 선언하기

for（cNum 길이만큼 반복하기）
{
	배열의 각 자릿값을 정수형으로 변환하며 sum에 더하여 누적하기
}
sum 출력하기

 

package datastructure.ch03;

import java.util.Scanner;

public class ds_q01 {
	public int solution(int n,String str) {
		//StringBuilder sb = new StringBuilder();
		int answer=0;
		char[] arr = str.toCharArray();
		
		for(int i=0;i<n;i++) answer+=Integer.parseInt(Character.toString(arr[i])); 
		
		return answer;
	}
	public static void main(String[] args) {
		ds_q01 T = new ds_q01();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		String str= kb.next();
		System.out.println(T.solution(n, str));
	}

}

 

+) 세련된 풀이

---

문제 2. 평균 구하기

세준이는 기말고사를 망쳤다. 그래서 점수를 조작해 집에 가져가기로 결심했다. 일단 세준이는 자기 점수 중 최댓값을 골랐다. 그런 다음 최댓값을 M이라 할 때 모든 점수를 점수/M*100으로 고쳤다. 예를 들어 세준이의 최고점이 70점，수학 점수가 50점이라면 수학 점수는 50/70*100이므로 71.43점이다. 세준이의 성적을 이 방법으로 계산했을 때 새로운 평균을 구하는 프로그램을 작성하시오.

 

입력
1 번째 줄에 시험을 본 과목의 개수 비이 주어진다. 해당 값은 1，000보다 작거나 같다. 2번째 줄에 세준이의 현재 성적이 주어진다. 해당 값은 100보다 작거나 같은，음이 아닌 정수이고，적어도 1 개의 값은 0보다 크다.

출력
1 번째 줄에 새로운 평균을 출력한다. 실제 정답과 출력값의 절대 오차 또는 상대 오차가 10^-2 이하이면 정답이다.

 

 

예제 입력 1

3 //시험을본 과목의개수
40 80 60 // 각 과목의 시험 성적

 

예제 출력 1

75.0

 

예제 입력 2

3
10 20 30

 

예제 출력 2

66.666667

 

예제 입력 3

4
1 100 100 100

 

예제 출력 3

75.25

 

예제 입력 4

5
1 2 4 8 16

 

예제 출력 4

38.75

 

예제 입력 5

2
3 10

예제 출력 5

65.0

---

1단계. 문제 분석하기

: 최고 점수 기준 전체 점수 다시 계산해야한다 -> 모든 점수 입력 후에 최고점을 저장

+) 일일이 변환하지 않고 한번에 변환한 점수의 평균 점수 구할 수 있다.

(A / M * 100 + B / M * 100 + C / M * 100) / 3 = (A + B + C) * 100 / M / 3

 

2단계. 손으로 풀어보기

1. 점수를 1차원 배열에 저장
2. 배열을 탐색하면서 최고 점수와 점수 총합을 구한다
3. 평균값 = 총합 * 100 / 최고 점수 / 과목의 수

3단계. 슈도코드 작성하기

변수 N에 과목의 수 입력받기
길이가 N인 1차원 배열 A[] 선언하기

for（A[] 길이만큼 반복하기） {
	A[i]에 각 점수 저장하기
}
for（A[] 길이만큼 반복하기） {
	최고점은 변수 max에, 총점은 변수 sum에 저장하기
}
sum * 100 / max / N 출력하기

 

 

package datastructure.ch03;

import java.util.Scanner;

public class ds_q02 {
	public float solution(int n, int[] arr) {
		float [] output = new float[n];
		int max =Integer.MIN_VALUE;
		float sum=0;
		
		for(int x : arr)  max=Math.max(max, x);
		for(int i=0;i<n;i++) {
			
			output[i]=Float.valueOf(arr[i])/Float.valueOf(max)*100;
		}
		for(float x:output) sum+=x;
		
		return sum/n;
	}
	public static void main(String[] args) {
		ds_q02 T = new ds_q02();
		Scanner kb= new Scanner(System.in);
		int n=kb.nextInt();
		int[] arr = new int[n];
		for(int i=0;i<n;i++) arr[i]=kb.nextInt();
		System.out.println(T.solution(n, arr));
	}
}

 

+) 세련된 풀이