💥 배열 알고리즘
유형
1.큰 수 출력하기
//입력
6
7 3 9 5 6 12
//출력
7 9 6 12public class Array1 {
public static ArrayList<Integer> solution(int n, int[] number){
ArrayList<Integer> answer = new ArrayList<>();
answer.add(number[0]);
for(int i=1; i<number.length; i++){
if(number[i] > number[i-1]) {
answer.add(number[i]);
}
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] number = new int[n];
for(int i=0; i<n; i++){
number[i] = sc.nextInt();
}
for(int x : solution(n, number)){
System.out.print(x + " ");
}
}
}풀이
1.동적배열로 answer를 초기화한다.
2.첫 숫자는 무조건 포함하는 조건이기 때문에 .add()를 이용해서 삽입
3.answer[i]인덱스보다 answer[i-1]인덱스가 더 크면 .add()를 이용해서 삽입
[ 주요 기능 ]
answer.add(number[i]) : add를 이용해서 number 배열의 i인덱스를 answer 동적배열에 삽입하는 메서드
2.보이는 학생
//입력
8
130 135 148 140 145 150 150 153
//출력
5public class Array2 {
public static int solution(int n, int[] number){
int answer = 1;
int p = number[0];
for(int i=1; i<number.length; i++){
if(number[i] > p) {
p=number[i];
answer++;
}
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] number = new int[n];
for(int i=0; i<n; i++){
number[i] = sc.nextInt();
}
System.out.println(solution(n,number));
}
}풀이
1.제일 앞에서 봤을 때 보이는 사람은 몇명인지 맞추는 문제
2.for문을 이용해서 배열의 끝까지 돌고 제일 앞사람은 어차피 보이니까 i=1부터 시작
3.최댓값 알고리즘 적용. p변수 선언 후에 number[i]가 p변수 보다 크면 asnwer++; 해준다.
[ 주요기능 ]
최댓값 알고리즘 : 기준이 되는 변수(최솟값)를 선언해주고 비교하는 방식
3.가위바위보
//입력
5
2 3 3 1 3
1 1 2 2 3
//출력
A B A B Dpublic class Array3 {
public static ArrayList<String> solution(int n, int[] A,int[] B){
ArrayList<String> answer = new ArrayList<>();
for(int i=0; i<n; i++){
if(A[i] == B[i])answer.add("D");
else if(A[i] == 1 && B[i] == 3) answer.add("A");
else if(A[i] == 2 && B[i] == 1) answer.add("A");
else if(A[i] == 3 && B[i] == 2) answer.add("A");
else answer.add("B");
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] A = new int[n];
int[] B = new int[n];
for(int i=0; i<n; i++){
A[i] = sc.nextInt();
}
for(int i=0; i<n; i++){
B[i] = sc.nextInt();
}
for (String s : solution(n, A, B)) {
System.out.println(s);
}
}
}풀이
1.가위=1 , 바위=2 , 보=3 이다. 이기는 사람이 출력되고 비기면 D가 출력된다.
2.주어지는 값에 따라 배열 크기가 바뀌기 때문에 동적배열로 선언. (그냥배열을 넘어오는 n 값 만큼 만들어도 됨)
3.for문으로 인덱스 길이 만큼 돌면서 조건을 추가한다.
비기면 'D'출력 , A가 이기면 'A'출력 , B가 이기면 'B'출력
4.동적 배열이기 때문에 값은 .add()로 배열에 추가
[ 주요 기능 ]
x
4.피보나치 수열
//입력
10
//출력
1 1 2 3 5 8 13 21 34 55public class Array4 {
public static int[] solution(int n){
int[] answer = new int[n];
answer[0] = 1;
answer[1] = 1;
for(int i=2; i<answer.length; i++){
answer[i] = answer[i-1] + answer[i-2];
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int x : solution(n)){
System.out.println(x + " ");
}
}
}풀이
1.피보나치 수열은 앞의 두 숫자를 더한 값이 다음 숫자랑 같은 배열이다.
2.0번,1번 인덱스는 무조건 1 고정.
3.i=2부터 인덱스 길이까지 answer[i]=answer[i-1]+answer[i-2] 으로 값을 구해서 리턴
[ 주요 기능 ]
피보나치 수열 : 0번 1번 인덱스는 무조건 1 고정.
5.소수
//입력
20
//출력
8public class Array5 {
public static int solution(int n){
int answer = 0;
int[] arr = new int[n+1];
for(int i=2; i<arr.length; i++) {
if (arr[i] == 0) {
answer++;
//i의 배수에 다 1 체크
for (int j=i; j<arr.length; j=j+i) {
arr[j] = 1;
}
}
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(solution(n));
}
}풀이
1.에라토스테네스의 체 : 소수를 찾는 방법이다. 초반에 숫자를 체크하면서 그에 해당하는 배열의 숫자도 다 체크하면서 소수를 찾아나가는 방식이다.
2.인덱스 0,1은 볼 필요가 없기 때문에 i=2부터 for문으로 돌린다.
3.우선 answer을 0으로 둔다. i=2일 때 arr[i]가 0이면 answer++(소수 카운트) 시키고 아니면 for문을 이용해서 해당하는 숫자의 배수 위치에 1을 체크한다.
[ 주요 기능 ]
에라토스테네스의 체 : 소수를 찾는 방법이다.
6.뒤집은 소수
//문제
n 과 n크기 만큼의 배열을 입력하여 뒤집은 다음 새로운 소수의 배열을 리턴하는 문제이다. 뒤집었을 때 200 -> 002 가 되면 2로 처리한다.
//입력
9
32 55 62 20 250 370 200 30 100
//출력
23 2 73 2 3public class Array6 {
public static boolean isPrime(int num){
if(num==1) return false;
for(int i=2; i<num; i++){
if(num%i==0) return false;
}
return true;
}
public static ArrayList<Integer> solution(int n, String[] arr){
ArrayList<Integer> answer = new ArrayList<>();
int[] array = new int[n];
for(int i=0; i<arr.length; i++) {
String tmp = new StringBuilder(arr[i]).reverse().toString();
array[i] += Integer.valueOf(tmp);
}
for(int i=0; i<array.length; i++){
if(isPrime(array[i])) answer.add(array[i]);
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String[] arr = new String[n];
for(int i=0; i<n; i++){
arr[i] = sc.next();
}
for(int x : solution(n,arr)){
System.out.print(x + " ");
}
}풀이
1.우선 입력할 개수n의 크기만큼 문자열 배열을 만든다
2.입력 받은 문자열의 요소를 Stringbuilder or String buffer를 이용해서 리버스 한 후에, Integer.valueOf()를 이용해서 int [] array 배열에 담는다.
3.이제 이 array배열에 담겨 있는 숫자를 소수인지 검증해야한다. isPrime() 이라는 내부 클래스를 하나 만든다.
4.요소의 값이 1이면 return false, 요소 n의 값이 1~n까지 돌렸을 때 나머지가 0이 나오면 return false, 이 경우도 아니면 true를 반환해준다.
5.true가 반환되면 answer.add(array[i])를 해준다.
[ 주요 기능 ]
1.내부 클래스 isPrime()
2.Intenger.value()
3.Stringbuilder,Stringbuffer 의 reverse().toString()
7.점수 계산
//문제
앞에서 부터 1인 숫자를 결과에 더한다.
연달아 1이 나오는 경우에는 1씩 증가하고, 0이 나오면 다시 1부터
//입력
10
1 0 1 1 1 0 0 1 1 0
//출력
10public class Array7 {
public static int solution(int n, int[] arr){
int answer = 0;
int p =0;
for(int i=0; i<arr.length; i++){
if(arr[i]==1){
p++;
answer += p;
}
else p=0;
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
System.out.println(solution(n,arr));
}
}풀이
1.answer에 값을 저장할 변수 p 선언, 입력받은 배열의 끝까지 for문.
2.arr[i] ==1인 경우에 p++ , answer += p; 이렇게 해준다
3.1이 아닌 경우에는 p=0으로 만든다.
[ 주요 기능 ]
x
8.등수 구하기
//문제
입력된 배열의 점수마다 몇등인지 새로운 배열로 리턴하는 문제.
점수가 겹치면 공동 높은 순위로 하고 다음 순위는 공동순위 다 빼고 친다.
//입력
5
87 89 92 100 76
//출력
4 3 2 1 5 public static int[] solution(int n, int[] arr){
int[] answer = new int[n];
for(int i=0; i<arr.length; i++){
int p = 1;
for(int j=0; j<arr.length; j++){
if(arr[j] > arr[i]) p++;
}
answer[i] = p;
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
for(int x : solution(n,arr)){
System.out.print(x + " ");
}
}풀이
1.2중 for문을 이용해서 한 점수에 대해서 모든 점수를 돈다.
2.변수 p를 둬서 i=* 일때 arr[j] > arr[i] 인 경우에 p++
3.answer[i] = p 저장 후 리턴
[ 주요 기능 ]
x
9.격자판 최대합
//문제
모든 행,열,대각선 의 합 중에서 가장 큰 값을 리턴하라.
//입력
5
10 13 10 12 15
12 39 30 23 11
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19
//출력
155public class Array9 {
public static int solution(int n, int[][] arr){
int answer = 0;
int sum1, sum2; //행,열의 합
for(int i=0; i<n; i++){
sum1=sum2=0;
for(int j=0; j<n; j++){
sum1+=arr[i][j];
sum2+=arr[j][i];
}
answer=Math.max(answer,sum1);
answer=Math.max(answer,sum2);
}
sum1=sum2=0; //양 대각선
for(int i=0; i<n; i++){
sum1+=arr[i][i];
sum2+=arr[i][n-i-1];
}
answer=Math.max(answer,sum1);
answer=Math.max(answer,sum2);
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] arr = new int[n][n];
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
arr[i][j]=sc.nextInt();
}
}
System.out.println(solution(n,arr));
}
}풀이
1.우선 Scanner 입력 받는 것 부터 까다롭다. 몇개의 행과 열을 만들 것인지에 대해 정수 n을 입력 받고 2중 for문으로 arr[i][j]를 각각 n개 만큼 입력 받는다.
2.행과 열, 그리고 양 쪽 대각선의 값을 저장할 변수 sum1,sum2를 선언한다.
3.2중 for문을 돌면서 sum1+=arr[i][j] , sum2+=arr[j][i]를 저장한다
4.Math.max()를 이용해서 더 큰 값을 asnwer에 저장한다.
5.양 쪽 대각선을 구한다. 그냥 for문에서 한 쪽은 arr[i][i], 반대쪽은 arr[i][n-i-1] 해주면 된다. -1은 배열길이에서 -1해야 인덱스 위치랑 같기 때문에.
6.똑같이 Math.max로 더 큰값 저장 후 리턴
[ 주요 기능 ]
Math.max('a','b') : 두 값을 비교해서 더 큰 값을 저장
10.봉우리
//문제
각 배열의 상하좌우를 비교해서 가장 큰수인 경우의 개수를 출력하는 문제.
상하좌우가 없으면 0으로 간주
//입력
5
5 3 7 2 3
3 7 1 6 1
7 2 5 3 4
4 3 6 4 1
8 7 3 5 2
//출력
10public class Array10 {
public static int solution(int n, int[][] arr){
int answer = 0;
for(int i=1; i<arr.length-1; i++){
for(int j=1; j<arr.length-1; j++){
if(arr[i][j] > arr[i-1][j] && arr[i][j] > arr[i+1][j] && arr[i][j] > arr[i][j-1] && arr[i][j] > arr[i][j+1]){
answer ++;
}
}
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] arr = new int[n+2][n+2];
for(int i=1; i<n+1; i++){
for(int j=1; j<n+1; j++){
arr[i][j]=sc.nextInt();
}
}
System.out.println(solution(n,arr));
}
}풀이
1.배열의 행과열의 개수는 입력받는 n개의 개수만큼 생성한다.
2.하지만 상하좌우를 비교하기 위해서 0으로 간주해야하기 때문에 배열을 생성할 때 new int [n+2][n+2] 씩 생성 한 후에 for문으로 입력 받을 때 5개의 입력이 중간에 가도록 i=1부터 n+1까지 입력 받는다.
3.그 후에 배열의 각 요소에 대하여 상하좌우를 비교하는 if문을 작성하고 조건을 만족하면 answer++;
[ 주요 기능 ]
배열 생성시에 new int[n+2][n+2]
11.임시반장 정하기
//문제
학생들 끼리 가장 여러 학생과 같은 반을 많이 한 학생을 반장으로 선발한다. 그 학생은? 학생번호를 출력하라.
//입력
5
학년
A : 2 3 1 7 3
B : 4 1 9 6 8
C : 5 5 2 4 4
D : 6 5 2 6 7
E : 8 4 2 2 2
//출력
4public class Array11 {
public static int solution(int n, int[][] arr){
int answer = 0;
int max =0;
for(int i=1; i<=n; i++){
int cnt = 0;
for(int j=1; j<=n; j++){
for(int k=1; k<=5; k++){
if(arr[i][k] == arr[j][k]){
cnt++;
break;
}
}
}
if(cnt > max){
max = cnt;
answer = i;
}
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
//무조건 5학급이니까 6으로 고정 학생 수는 늘어날 수 있으니까
//n으로 하고 1번학생부터 시작 -> +1
int[][] arr = new int[n+1][6];
for(int i=1; i<=n; i++){
for(int j=1; j<=5; j++){
arr[i][j]=sc.nextInt();
}
}
System.out.println(solution(n,arr));
}
}풀이
1.5학급이기 때문에 new int[n+1][6] 으로 생성한다. [n+1]을 했기 때문에 for문은 i=1부터 입력
2.2중 for문으로 학생들 끼리의 경우를 다 돈다.
3.for문을 추가하여 1~5학년까지의 i학생과 j학생이 같은반을 한적이있는지 없는지 체크한다. 있다면 break; -> 한 번이라도 같은 반을 한 친구가 있는 횟수가 많은 것을 체크하는 것이기에 n학년에 2명이상랑 같은 반을 했다고 카운트가 올라가지 않는다.
4.최댓값 알고리즘을 이용하여 가장 카운트가 큰 i학생을 정답으로 리턴.
[ 주요 기능 ]
3중 for문이 핵심이다.
배열 생성 시에 학급은 5학급으로 고정이기 때문에 6(1학급 부터 시작하기 위해서) 으로 고정한다.
💥 12.멘토링 (어려움)
//문제
학생들 끼리 서로 멘토,멘티를 이루어 팀을 만들 수 있는 경우의 수를 구하라.
멘토는 모든 테스트의 경우에서 멘티보다 성적이 높아야 한다.
//입력
4 3 -> 4명의 학생과 3개의 테스트를 뜻한다.
3 4 1 2 -> 1번 테스트 : 3번학생이 1등 4번학생이 2등 1번학생이 3등 2번학생이 4등.
4 3 2 1
3 1 4 2
//출력
3public class Array12 {
public static int solution(int n, int m, int[][] arr) {
int answer = 0;
//학생 수를 1~4로 할거라서 1부터 i<=n까지
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
int cnt=0;
for(int k=0; k<m; k++){
int pi=0,pj=0;
for(int s=0; s<n; s++){
//몇번 테스트에서 i,j가 몇등씩 했는지 등수 체크
if(arr[k][s]==i) pi=s;
if(arr[k][s]==j) pj=s;
}
if(pi<pj) cnt++; //s가 더 작으면 더 높은 등수
}
if(cnt==m){
//cnt(등수 더 높은 경우)가 테스트 횟수랑 같으면
answer++;
}
}
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] arr = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = sc.nextInt();
}
}
System.out.println(solution(n, m, arr));
}
}풀이
1.학생 수와 몇가지의 테스트를 할 것인지에 대해서 각 테스트에 대한 학생들의 등수를 입력한다.
2.우선 학생들끼리 2중 for문을 돌려서 학생들 끼리의 모든 경우를 돈다.
3.테스트 경우의 수까지 k for문을 돌린다. 그 안에서 또 for문을 이용해서 해당 학생이 몇 번 테스트에서 몇등인 지 일치하는 지 if문으로 확인하고 pi,pj변수에 등수를 저장한다. for문을 하나 빠져나오면서 k for문에서 각 테스트마다 작을 수록 더 높은 등수이기 때문에 pi<pj인 지 확인 후에 그 조건의 횟수가 테스트의 횟수와 같다면 그 학생들은 멘토멘티가 가능하다. -> answer ++;
[ 주요 기능 ]
4중 for문을 이용하여 문제를 푼다. 문제를 이해 하는 것이 핵심이다.
문제에서는 이미 학생끼리 비교하는데 학생은 빼고 테스트경우와 해당하는 학생 등수만 준다. -> 4중 for문 문제라는 뜻
