자료구조
1. 배열과 리스트
001 숫자의 합 구하기(백준11720)
N개의 숫자가 공백 없이 써 있다. 이 숫자률 모두 합해 출력하는 프로그램올 작성하시오.
입력
1번째 줄에 숫자의 개수 N(1 < N < 10이，2번째 줄에 숫자 N개가 공백 없이 주어진다.
출력
입력으로 주어진 숫자 N개의 합을 출력한다.
예제
예제 1
입력
1 // 숫자의 개수
1 // 공백 없이 주어진 N개의 숫자
출력
1
예제 2
입력
5
12345
출력
15
예제 3
입력
25
7000000000000000000000000
출력
7
예제 4
입력
11
10987654321
출력
46
코드
import java.util.Scanner;
public Class P11720_숫자의합 { 서 백준 온라인 처지에서는 공래스잇울 MAin으로 상적하세요!
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextlnt();
// 입력값율 String형 변수 sNum에 저장한 후 charU형 변수로 변환하기
String sNum = sc.next();
char[] eNum = sNum.toCharArray();
int sum = 0;
for (int i = 0; i < eNum.length; i++) {
sum += cNumfi] - *0*; // cNum[i]* 정수형으로 변환하면서 sum에 더하여 누적하기
}
System.out.print(sum);
}
}문자열을 string.toCharArray() 로 배열로 변환
해당 char에 - '0'을 하여 정수형으로 변환 후 sum 에 누적
자주 쓰이는 형변환
- String형 -> 숫자형(int, double, float, long, short)
String sNum = "1234"; // string형 변수
int il = Integer.parselnt(sNum);
int i2 = Integer.valueOf(sNum);
double dl = Double.parseDouble(sNum);
double d2 = Double.valueOf(sNum);
float fl = Float.parseFloat(sNum);
float f2 = Float.valueOf(sNum);
long 11 : Long.parseLong(sNum);
long 12 = Long.valueOf(sNum);
short si = Short.parseShort(sNum);
short s2 = Short.valueOf(sNum);- 숫자형(int, double, float, long, short) —> String형
int i = 1234;
String il = String.valueOf(i);
String i2 = Integer.toString(i);
double d = 1.23;
String dl = String.valueOf(d);
String d2 = Double.toString(d);
float f = (float) 1.23;
String fl = String.valueOf(f);
String f2 = Float.toString(f);
long I = 1234;
String 11 = String.valueOf(I);
String 12 = Long.toString(l);
short s = 1234;
String si = String.valueOf(s);
String s2 = Short.toString(s);002 평균 구하기(1546)
세준이는 기알고사룹 망쳤다. 그래서 점수률 조작해 집에 가져가기로 결심했다. 일단 세준이는 자기 정수
중 최댓값을 골랐다. 그런 다옹 최댓값을 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 // 각 과목의 시험 성적
출력
75.0
예제 2
입력
3
10 20 30
출력
66.666667
예제 3
입력
4
1 100 100 100
출력
75.25
예제 4
입력
5
1 2 4 8 16
출력
38.75
예제 5
입력
2
3 10
출력
65.0
코드
public class P1546 평균 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextlnt();
int A[] = new int[N];
for (int i = 0; i < N; i++) {
A[i] = sc.nextlnt();
}
long sum = 0;
long max = 0;
for (int i = 0; i < N; i++) {
if (A[i] max) max = A[i];
sum = sum + A[i];
}
// 한 과목과 관련된 수식율 총합한 후 관련된 수식으로 변환해 로직이 간단해징
System.out.println(sum • 100.0 / max / N);
}
}하나 하나 계산할 필요 없이
(A + B +... + Z) * 100 / 최댓값 / N 을 하면 된다
2. 구간 합
003 구간 합 구하기(11659)
수 어개가 주어졌올 때 i 번째 수에서 j 번째 수까지의 합올 구하는 프로그램올 작성하시오.
입력
1 번째 줄에 수의 개수 N(1 <= N <= 100,000). 합을 구해야 하는 횟수 M(1 <= M <= 100,000)，
2번째 줄
에 N개의 수가 주어진다. 각 수는 1,000보다 작거나 같은 자연수다.
3번째 줄부터는 M개의 줄에 합을 구해야하는 구간 i와 j가주어진다.
출력
총 M개의 줄에 입력으로 주어진 i 번째 수에서 j 번째 수까지의 합을 출력한다.
예제 1
입력
5 3 // 데이터의 개수, 질의 개수
5 4 3 2 1 // 구간 합을 구할 대상 배열
1 3
2 4
5 5
출력
12
9
1
코드
package cdTest;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Test {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n1 = Integer.parseInt(st.nextToken());
int n2 = Integer.parseInt(st.nextToken());
long[] S = new long[n1 +1];
st = new StringTokenizer(br.readLine());
for(int i=1; i<=n1; i++) {
S[i] = S[i-1] + Integer.parseInt(st.nextToken());
}
for(int i=0; i<n2; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
System.out.println(S[e] - S[s-1]);
}
}
}
일반 배열은 따로 만들 필요가 없음
합배열만 만들어서 바로 계산
합배열의 0번 인덱스는 0으로 필요하지 않음
문제에 인덱스는 1부터 시작임
004 구간 합 구하기 2(11660)
N x N개의 수가 N x N 크기의 표에 채워져 있다. 표 안의 수 중 (Xi. Yi)에서 (X2, Y2)까지의 합을 구하려 한다. X는 행, Y는 열을 의미한다. 예를 들어 N = 4이고, 표가 다음과 같이 채워져 있을 때를 살펴보자. (2, 2)에서 (3, 4)까지의 합을 구하면 3 + 4 + 5 + 4 + 5 + 6 = 27이고, (4,4)에서 (4,4)까지의 합을 구하면 7이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을때 이를 처리하는 프로그램을 작성하시오.
입력
1번째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다 (1 <= N <= 1024, 1 <= M <= 100,000 )
2번째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 4개의 정수 X1m Y1, X2, Y2 가 주어지며, (X1, Y1)에서 (X2, Y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000 보다 작거나 같은 자연수다 (X1 <= X2, Y1 <= Y2).
출력
총 M줄에 걸쳐 (X1, Y1)에서 (X2, Y2)까지 합을 구해 출력한다.
예제 1
입력
4 3 // 2차원 배열의 크기, 구간 합 질의의 개수
1 2 3 4 // 원본 배열 1번째 줄
2 3 4 5 // 원본 배열 2번째 줄
3 4 5 6 // 원본 배열 3번째 줄
4 5 6 7 // 원본 배열 4번째 줄
2 2 3 4 // 구간 합 (X1, Y1), (X2, Y2) 1번째 질의
3 4 3 4 // 구간 합 (X1, Y1), (X2, Y2) 1번째 질의
1 1 4 4 // 구간 합 (X1, Y1), (X2, Y2) 1번째 질의
출력
27
6
64
예제 2
입력
2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2
출력
27
6
64
슈도코드
N(배열 크기) M(질의 수) 저장
for(N만큼 반복) {
for(N만큼 반복하기){
원본 배열 저장
}
}
for(N만큼 반복) {
for(N만큼 반복하기){
합 배열 저장
D[ i ][ j ] = D[ i ][ j-1 ] + D[ i-1 ][ j ] - D[ i-1 ][ j-1 ] + A[ i ][ j ];
}
}
for(M만큼 반복) {
질의 계산 및 출력
결과 = D[X2][Y]- D[Xi-1][Y2]- D[X2][Yi-1] + D[Xi-1][Yi-1];
}코드
package cdTest;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Test {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] A = new int[N+1][N+1];
for(int i=1; i<=N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=1; j<=N; j++) {
A[i][j] = Integer.parseInt(st.nextToken());
}
}
int D[][] = new int[N+1][N+1];
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
D[i][j] = D[i][j-1] + D[i-1][j] -D[i-1][j-1] + A[i][j];
}
}
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
int res = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1];
System.out.println(res);
}
}
}
D[ i ][ 1 ] = D[ i-1 ][ 1 ] + A[ i ][ 1 ]
전 예제와 같은 방식
D[ i ][ j ] 구하는 구간 합 공식
D[ i ][ j ] = D[ i ][ j-1 ] + D[ i-1 ][ j ] - D[ i-1 ][ j-1 ] + A[ i ][ j ]예제와 같은 문제의 답을 구하는 방법
D[X2][Y]- D[Xi-1][Y2]- D[X2][Yi-1] + D[Xi-1][Yi-1]
005 나머지 합 구하기(10986)
N개의 수 A1, A2, ... An 이 주어졌을 때 연속된 부분의 합이 M으로 나누어떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj ( i <= j ) 쌍의 개수를 구하시오.
입력
1번째 줄에 N과 M(1 <= N <= 106, 1 <= M <= 103)
2번째 줄에 N개의 A1, A2,..., An 이 주어진다.(0 <= Ai <= 109).
출력
첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.
예제1
입력
5 3
1 2 3 1 2
출력
7
핵심 아이디어
-
(A + B) % C 은 ((A % C) + (B % C)) % C 와 같다. 다시 말해 특정 구간 수들의 나어지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나어지 연산을 한 값은 동일하다.
-
구간 합 배열을 이용한 식 S[ i ] - S[ j ]는 원본 배열의 j + 1 부터 i까지의 구간 합이다.
-
S[ i ] % M의 값과 S[ j ] % M의 값이 같다면 (S[ i ] - S[ j ]) % M은 0이다. 즉. 구간 함 배영의 원소S M으로
나눈 나어지로 업데이트하고 S[ i ]와 S [ j ]가 같은 (i. j)쌍을 찾으면 원본 배열에서 j + 1부터 i까지의 구간 합이 M으로 나누어떨어진다는 것을 알 수 있다.
참고 블로그
https://banwolcode.tistory.com/47
슈도코드
N 입력 // 수열 개수
M 입력 // 나누어떨어져야 하는 수
S // 합 배열
C // 같은 나머지의 인덱스를 카운트하는 배열
for(i -> 1 ~ N ){
S[i] = S[i -1] + A[i] // 합 배열 저장
}
for(i -> 0 ~ N ){
remainder = S[i] % M // 합 배열을 M으로 나눈 나머지 값
if(remainder ==0) 정답 ++
C[remainder] ++
}
for(i -> 0 ~ N ){
// i가 나머지인 인덱스의 개수
C[i] 에서 2가지를 뽑는 경우의 수 정답에 +
// C[i] 개 중 2개를 뽑는 경우의 수 계산 공식
// C[i] * (C[i] -1) / 2
}
결과 출력코드
package cdTest;
import java.io.IOException;
import java.util.Scanner;
public class Test {
public static void main(String[] args) throws IOException{
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
long[] S = new long[N];
long[] C = new long[M];
long answer = 0;
S[0] = sc.nextInt();
for(int i=0; i<N; i++) {
S[i] = S[i-1] + sc.nextInt();
}
for(int i=0; i<N; i++) {
int remainder = (int) (S[i] % M);
if(remainder == 0) answer ++;
C[remainder]++;
}
for(int i=0; i<M; i++) {
if(C[i] > 1) {
answer = answer + (C[i] * (C[i] - 1) / 2);
}
}
System.out.println(answer);
}
}
