[JAVA] 알고리즘 문제풀이 기초 - Array(1,2차원 배열) part.1
Array(1, 2차원 배열)
큰 수 출력하기(2-1)
-
설명 : N개의 정수를 입력받아, 자신의 바로 앞 수보다 큰 수만 출력하는 프로그램을 작성하세요. (첫 번째 수는 무조건 출력한다)
-
입력 : 첫 줄에 자연수 N(1<=N<=100)이 주어지고, 그 다음 줄에 N개의 정수가 입력된다.
-
출력 : 자신의 바로 앞 수보다 큰 수만 한 줄로 출력한다.
-
작성 답안
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
Integer roof = scan.nextInt();
Integer[] num = new Integer[roof];
for(int i=0; i<roof; i++){
num[i] = scan.nextInt();
}
for(int a : t.solution(num)){
System.out.print(a+" ");
}
}
public List<Integer> solution(Integer[] num){
ArrayList<Integer> result = new ArrayList<>();
result.add(num[0]);
for(int i=1; i<num.length; i++){
if(num[i-1]<num[i]){
result.add(num[i]);
}
}
return result;
}
}
보이는 학생 (2-2)
-
설명 : 선생님이 N명의 학생을 일렬로 세웠습니다. 일렬로 서 있는 학생의 키가 앞에서부터 순서대로 주어질 때, 맨 앞에 서 있는 선생님이 볼 수 있는 학생의 수를 구하는 프로그램을 작성하세요. (앞에 서 있는 사람들보다 크면 보이고, 작거나 같으면 보이지 않습니다.)
-
입력 : 첫 줄에 정수 N(5<=N<=100,000)이 입력된다. 그 다음줄에 N명의 학생의 키가 앞에서부터 순서대로 주어진다.
-
출력 : 선생님이 볼 수 있는 최대학생수를 출력한다.
-
작성 답안
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
Integer roof = scan.nextInt();
Integer[] num = new Integer[roof];
for(int i=0; i<roof; i++){
num[i] = scan.nextInt();
}
System.out.print(t.solution(num));
}
public int solution(Integer[] num){
int result = 1;
int max = num[0];
for(int i=1; i<num.length; i++){
if(max<num[i]){
result++;
max=num[i];
}
}
return result;
}
}
가위 바위 보 (1-3)
- 설명 : A, B 두 사람이 가위바위보 게임을 합니다. 총 N번의 게임을 하여 A가 이기면 A를 출력하고, B가 이기면 B를 출력합니다. 비길 경우에는 D를 출력합니다. 가위, 바위, 보의 정보는 1:가위, 2:바위, 3:보로 정하겠습니다. 예를 들어 N=5이면
두 사람의 각 회의 가위, 바위, 보 정보가 주어지면 각 회를 누가 이겼는지 출력하는 프로그램을 작성하세요.
-
입력 : 첫 번째 줄에 게임 횟수인 자연수 N(1<=N<=100)이 주어집니다. 두 번째 줄에는 A가 낸 가위, 바위, 보 정보가 N개 주어집니다. 세 번째 줄에는 B가 낸 가위, 바위, 보 정보가 N개 주어집니다.
-
출력 : 각 줄에 각 회의 승자를 출력합니다. 비겼을 경우는 D를 출력합니다.
-
작성 답안
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
Integer roof = scan.nextInt();
Integer[] a = new Integer[roof];
Integer[] b = new Integer[roof];
for(int i=0; i<roof; i++){
a[i] = scan.nextInt();
}
for(int i=0; i<roof; i++){
b[i] = scan.nextInt();
}
for (String result : t.solution(a, b, roof)) {
System.out.println(result);
}
}
public List<String> solution(Integer[] a, Integer[] b, int roof){
List result = new ArrayList();
for(int i=0; i<roof; i++){
if(a[i] == b[i]){
result.add("D");
} else if(a[i]==1 && b[i]==2){
result.add("B");
} else if(a[i]==2 && b[i]==3){
result.add("B");
} else if(a[i]==3 && b[i]==1) {
result.add("B");
} else {
result.add("A");
}
}
return result;
}
}
- 특징
- 모든 경우를 쓰는게 아니라, 비기는 경우와 한가지 시점에서 이기는 경우만 조건을 걸고 나머지는 else 처리
- 모든 경우를 쓰는게 아니라, 비기는 경우와 한가지 시점에서 이기는 경우만 조건을 걸고 나머지는 else 처리
피보나치 수열 (1-4)
- 설명
1) 피보나키 수열을 출력한다. 피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다.
2) 입력은 피보나치 수열의 총 항의 수 이다. 만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다.
-
입력 : 첫 줄에 총 항수 N(3<=N<=45)이 입력된다.
-
출력 : 첫 줄에 피보나치 수열을 출력합니다.
-
작성 답안 -1
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
Integer num = scan.nextInt();
for (int result : t.solution(num)) {
System.out.print(result+" ");
}
}
public int[] solution(int num){
int[] result = new int[num];
result[0] = 1;
result[1] = 1;
for(int i=2; i<num; i++){
result[i] = result[i-1]+result[i-2];
}
return result;
}
}
- 작성 답안 -2 (배열 사용하지 못할경우)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
Integer num = scan.nextInt();
t.solution(num);
}
public void solution(int num){
int a = 1, b=1, c;
System.out.print(1+" "+1+" ");
for(int i=2; i<num; i++){
System.out.print(a+b+" ");
c=b;
b=a+b;
a=c;
}
}
}
- 특징
- 첫번째 두번째는 고정 수이기 때문에 수기로 반영하고 이후 출력부터 합산 (배열미사용시 tmp를 만들어 반영)
- 첫번째 두번째는 고정 수이기 때문에 수기로 반영하고 이후 출력부터 합산 (배열미사용시 tmp를 만들어 반영)
소수(에라토스테네스 체)
-
설명 : 자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요. 만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.
-
입력 : 첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.
-
출력 : 첫 줄에 소수의 개수를 출력합니다.
-
작성 답안
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
Integer num = scan.nextInt();
System.out.println(t.solution(num));
}
public int solution(int num){
int[] param = new int[num+1];
for(int i=2; i<=num; i++){
for(int j=2; i*j<=num; j++){
if(param[i*j]==0){
param[i*j] = i;
}
}
}
int result = 0;
for(int i=2; i<param.length; i++){
if(param[i]==0){
result++;
}
}
return result;
}
}
- 풀이 답안
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
Integer num = scan.nextInt();
System.out.println(t.solution(num));
}
public int solution(int num){
int result = 0;
int[] param = new int[num+1];
for(int i=2; i<=num; i++){
if(param[i]==0){
result++;
for(int j=i; j<=num; j=j+i){
param[j] = i;
}
}
}
return result;
}
}
- 특징
- 작은수 부터 반복을 돌며 아직 0의 값으로 되어있는 항목은 소수로 카운팅
- 작은수의 배수에 미리 인덱스에 값을 넣어줌
- 배수 체크가 끝나면 다음 수를 계속해서 체크
- 작은수 부터 반복을 돌며 아직 0의 값으로 되어있는 항목은 소수로 카운팅
### 뒤집은 소수 (2-6)
-
설명 : N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 소수를 출력하는 프로그램을 작성하세요. 예를 들어 32를 뒤집으면 23이고, 23은 소수이다. 그러면 23을 출력한다. 단 910를 뒤집으면 19로 숫자화 해야 한다. 첫 자리부터의 연속된 0은 무시한다.
-
입력 : 첫 줄에 자연수의 개수 N(3<=N<=100)이 주어지고, 그 다음 줄에 N개의 자연수가 주어진다. 각 자연수의 크기는 100,000를 넘지 않는다.
-
출력 : 첫 줄에 뒤집은 소수를 출력합니다. 출력순서는 입력된 순서대로 출력합니다.
-
작성 답안
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int[] ns = new int[num];
int max = 0;
for(int i=0; i<num; i++){
ns[i] = Integer.parseInt(new StringBuilder(scan.next()).reverse().toString());
max = Math.max(max,ns[i]);
}
for (Integer integer : t.solution(ns, max)) {
System.out.print(integer+" ");
}
}
public List<Integer> solution(int[] ns, int max){
int[] num = new int[max+1];
List<Integer> dummy = new ArrayList();
for(int i=2; i<=max; i++){
if(num[i]==0) {
dummy.add(i);
for(int j=i; j<=max; j=j+i){
num[j] = i;
}
}
}
List<Integer> result = new ArrayList();
for (int n : ns) {
for (Integer integer : dummy) {
if(n==integer){
result.add(n);
}
}
}
return result;
}
}
- 풀이 답안
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int[] ns = new int[num];
int max = 0;
for(int i=0; i<num; i++){
ns[i] = scan.nextInt();
}
for (Integer integer : t.solution(ns)) {
System.out.print(integer+" ");
}
}
public List<Integer> solution(int[] ns){
List<Integer> result = new ArrayList<>();
for(int i=0; i<ns.length; i++){
int tmp = ns[i];
int res = 0;
while(tmp>0){
int t = tmp%10;
res = res*10+t;
tmp = tmp/10;
}
if(isPrime(res)) result.add(res);
}
return result;
}
public boolean isPrime(int res){
if(res==0 || res==1) return false;
for (int i=2; i<res; i++){
if(res%i==0) return false;
}
return true;
}
}
- 특징
- 내가 작성한의 경우 스캔시 StringBuilder로 받아서 바로 리버스하고, 숫자로 변환. 풀이에서는 for문과 while문을 통해 수동으로 변환함. 변환 방법은 기존 풀이가 더 간단한듯 하나, 수동변환 방법도 익혀두면 좋으니 참고해둘 것
- 나의 경우 입력때 max값을 받아서 최대 기준을 만든 다음, 그 안에서 반복을 돌면서 소수를 구하고, 입력값과 또 비교해서 리스트에 있는 소수만 뽑도록 했는데, 풀이에서는 isPrime를 만들어 해당수보다 작은수로 나누고 mod가 0이 나오지 않는 수만 추림
- 기존 작성코드와 풀이의 방식이 많이 달라 두가지 모두 익혀둘것
- 내가 작성한의 경우 스캔시 StringBuilder로 받아서 바로 리버스하고, 숫자로 변환. 풀이에서는 for문과 while문을 통해 수동으로 변환함. 변환 방법은 기존 풀이가 더 간단한듯 하나, 수동변환 방법도 익혀두면 좋으니 참고해둘 것