[JAVA] 알고리즘 문제풀이 기초 - 문자열 part.2
Array(1, 2차원 배열)
점수계산(2-7)
- 설명 : OX 문제는 맞거나 틀린 두 경우의 답을 가지는 문제를 말한다. 여러 개의 OX 문제로 만들어진 시험에서 연속적으로 답을 맞히는 경우에는 가산점을 주기 위해서 다음과 같이 점수 계산을 하기로 하였다. 1번 문제가 맞는 경우에는 1점으로 계산한다. 앞의 문제에 대해서는 답을 틀리다가 답이 맞는 처음 문제는 1점으로 계산한다. 또한, 연속으로 문제의 답이 맞는 경우에서 두 번째 문제는 2점, 세 번째 문제는 3점, …, K번째 문제는 K점으로 계산한다. 틀린 문제는 0점으로 계산한다. 예를 들어, 아래와 같이 10 개의 OX 문제에서 답이 맞은 문제의 경우에는 1로 표시하고, 틀린 경우에는 0으로 표시하였을 때, 점수 계산은 아래 표와 같이 계산되어, 총 점수는 1+1+2+3+1+2=10 점이다.
시험문제의 채점 결과가 주어졌을 때, 총 점수를 계산하는 프로그램을 작성하시오.
-
입력 : 첫째 줄에 문제의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 N개 문제의 채점 결과를 나타내는 0 혹은 1이 빈 칸을 사이에 두고 주어진다. 0은 문제의 답이 틀린 경우이고, 1은 문제의 답이 맞는 경우이다.
-
출력 : 첫째 줄에 입력에서 주어진 채점 결과에 대하여 가산점을 고려한 총 점수를 출력한다.
-
작성 답안
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];
for(int i=0; i<num; i++){
ns[i] = scan.nextInt();
}
System.out.print(t.solution(ns));
}
public int solution(int[] ns){
int result = 0;
int cnt = 0;
for(int i=0; i<ns.length; i++){
if(ns[i]==1) cnt++;
else cnt=0;
result += cnt;
}
return result;
}
}
등수구하기 (2-8)
-
설명 : N명의 학생의 국어점수가 입력되면 각 학생의 등수를 입력된 순서대로 출력하는 프로그램을 작성하세요. 같은 점수가 입력될 경우 높은 등수로 동일 처리한다. 즉 가장 높은 점수가 92점인데 92점이 3명 존재하면 1등이 3명이고 그 다음 학생은 4등이 된다.
-
입력 : 첫 줄에 N(3<=N<=100)이 입력되고, 두 번째 줄에 국어점수를 의미하는 N개의 정수가 입력된다.
-
출력 : 입력된 순서대로 등수를 출력한다.
-
작성 답안
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];
for(int i=0; i<num; i++){
ns[i] = scan.nextInt();
}
for (int i : t.solution(ns)) {
System.out.print(i+" ");
}
}
public int[] solution(int[] ns){
int[] result = new int[ns.length];
for(int i=0; i<ns.length; i++){
int cnt=1;
for (int j=0; j<ns.length; j++){
if(ns[j]>ns[i]) cnt++;
}
result[i] = cnt;
}
return result;
}
}
격자판 최대합 (2-9)
- 설명 : 5*5 격자판에 아래롸 같이 숫자가 적혀있습니다.
N*N의 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가 장 큰 합을 출력합니다.
-
입력 : 첫 줄에 자연수 N이 주어진다.(2<=N<=50) 두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는다.
-
출력 : 최대합을 출력합니다.
-
작성 답안
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][num];
for(int i=0; i<num; i++){
for(int j=0; j<num; j++){
ns[i][j] = scan.nextInt();
}
}
System.out.print(t.solution(ns));
}
public int solution(int[][] ns){
int result = 0;
int lt=0, rt=0;
for(int i=0; i<ns.length; i++){
int r=0, c=0;
for (int j=0; j<ns.length; j++){
r += ns[i][j];
c += ns[j][i];
}
lt += ns[i][i];
rt += ns[i][(ns.length-i)-1];
result = Math.max(result, Math.max(Math.max(r,c),Math.max(lt,rt)));
}
return result;
}
}
봉우리 (2-10)
- 설명 : 지도 정보가 N*N 격자판에 주어집니다. 각 격자에는 그 지역의 높이가 쓰여있습니다. 각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다. 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요. 격자의 가장자리는 0으로 초기화 되었다고 가정한다. 만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다.
-
입력 : 첫 줄에 자연수 N이 주어진다.(2<=N<=50) 두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는다.
-
출력 : 봉우리의 개수를 출력하세요.
-
작성 답안
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+2][num+2];
for(int i=1; i<=num; i++){
for(int j=1; j<=num; j++){
ns[i][j] = scan.nextInt();
}
}
System.out.print(t.solution(ns));
}
public int solution(int[][] ns){
int result = 0;
int max = 0;
for(int i=1; i< ns.length-1; i++){
for(int j=1; j<ns.length-1; j++){
max = Math.max(Math.max(ns[i][j-1], ns[i][j+1]), Math.max(ns[i-1][j], ns[i+1][j]));
if(ns[i][j]>max) 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);
int num = scan.nextInt();
int[][] ns = new int[num+2][num+2];
for(int i=1; i<=num; i++){
for(int j=1; j<=num; j++){
ns[i][j] = scan.nextInt();
}
}
System.out.print(t.solution(ns));
}
public int solution(int[][] ns){
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, -1, 0, 1};
int result = 0;
for(int i=1; i<ns.length-1; i++){
for(int j=1; j<ns.length-1; j++){
boolean flag = true;
for(int k=0; k<4; k++){
int nx = i+dx[k];
int ny = j+dy[k];
if(ns[nx][ny]>=ns[i][j]){
flag = false;
break;
}
}
if(flag) result++;
}
}
return result;
}
}
- 특징
- 개인적인 생각으로는 내가 작성한 답이 효율적이라고 생각하나
- 대각선 등의 조건이 붙는 경우 다른방법을 사용해야할 수도 있으니 풀이답안도 익혀둘것
- 개인적인 생각으로는 내가 작성한 답이 효율적이라고 생각하나
임시반장 정하기 (2-11)
- 설명 : 김갑동 선생님은 올해 6학년 1반 담임을 맡게 되었다. 김갑동 선생님은 우선 임시로 반장을 정하고 학생들이 서로 친숙해진 후에 정식으로 선거를 통해 반장을 선출하려고 한다. 그는 자기반 학생 중에서 1학년부터 5학년까지 지내오면서 한번이라도 같은 반이었던 사람이 가장 많은 학생을 임시 반장으로 정하려 한다. 그래서 김갑동 선생님은 각 학생들이 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 표를 만들었다. 예를 들어 학생 수가 5명일 때의 표를 살펴보자.
위 경우에 4번 학생을 보면 3번 학생과 2학년 때 같은 반이었고, 3번 학생 및 5번 학생과 3학년 때 같은 반이었으며, 2번 학생과는 4학년 때 같은 반이었음을 알 수 있다. 그러므로 이 학급에서 4번 학생과 한번이라도 같은 반이었던 사람은 2번 학생, 3번 학생과 5번 학생으로 모두 3명이다. 이 예에서 4번 학생이 전체 학생 중에서 같은 반이었던 학생 수가 제일 많으므로 임시 반장이 된다. 각 학생들이 1학년부터 5학년까지 속했던 반이 주어질 때, 임시 반장을 정하는 프로그램을 작성하시오.
-
입력 : 첫째 줄에는 반의 학생 수를 나타내는 정수가 주어진다. 학생 수는 3 이상 1000 이하이다. 둘째 줄부터는 1번 학생부터 차례대로 각 줄마다 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 5개의 정수가 빈칸 하나를 사이에 두고 주어진다. 주어지는 정수는 모두 1 이상 9 이하의 정수이다.
-
출력 : 첫 줄에 임시 반장으로 정해진 학생의 번호를 출력한다.
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][5];
for(int i=0; i<num; i++){
for(int j=0; j<5; j++){
ns[i][j] = scan.nextInt();
}
}
System.out.print(t.solution(ns));
}
public int solution(int[][] ns){
int result = 1;
int max = 0;
for(int i=0; i<ns.length; i++){
int cnt = 0;
for(int j=0; j<ns.length; j++){
if(i!=j){
for(int k=0; k<5; k++) {
if(ns[i][k]==ns[j][k]){
cnt++;
break;
}
}
}
}
if(cnt>max){
max = cnt;
result = i+1;
}
}
return result;
}
}
멘토링 (2-12)
-
설명 : 현수네 반 선생님은 반 학생들의 수학점수를 향상시키기 위해 멘토링 시스템을 만들려고 합니다. 멘토링은 멘토(도와주는 학생)와 멘티(도움을 받는 학생)가 한 짝이 되어 멘토가 멘티의 수학공부를 도와주는 것입니다. 선생님은 M번의 수학테스트 등수를 가지고 멘토와 멘티를 정합니다. 만약 A학생이 멘토이고, B학생이 멘티가 되는 짝이 되었다면, A학생은 M번의 수학테스트에서 모두 B학생보다 등수가 앞서야 합니다. M번의 수학성적이 주어지면 멘토와 멘티가 되는 짝을 만들 수 있는 경우가 총 몇 가지 인지 출력하는 프로그램을 작성하세요.
-
입력 : 첫 번째 줄에 반 학생 수 N(1<=N<=20)과 M(1<=M<=10)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 수학테스트 결과가 학생번호로 주어진다. 학생번호가 제일 앞에서부터 1등, 2등, …N등 순으로 표현된다. 만약 한 줄에 N=4이고, 테스트 결과가 3 4 1 2로 입력되었다면 3번 학생이 1등, 4번 학생이 2등, 1번 학생이 3등, 2번 학생이 4등을 의미합니다.
-
출력 : 첫 번째 줄에 짝을 만들 수 있는 총 경우를 출력합니다.
-
작성 답안
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 stu = scan.nextInt();
int test = scan.nextInt();
int[][] ns = new int[test][stu];
for(int i=0; i<test; i++){
for(int j=0; j<stu; j++){
ns[i][j] = scan.nextInt();
}
}
System.out.print(t.solution(ns, stu, test));
}
public int solution(int[][] ns, int stu, int test){
int result = 0;
int[][] param = new int[stu+1][stu+1];
for(int i=0; i<test; i++){
for(int j=0; j<stu-1; j++){
for(int k=j+1; k<stu; k++){
param[ns[i][j]][ns[i][k]] += 1;
}
}
}
for (int[] ints : param) {
for (int anInt : ints) {
if (anInt==test){
result++;
}
}
}
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 stu = scan.nextInt();
int test = scan.nextInt();
int[][] ns = new int[test][stu];
for(int i=0; i<test; i++){
for(int j=0; j<stu; j++){
ns[i][j] = scan.nextInt();
}
}
System.out.print(t.solution(ns, stu, test));
}
public int solution(int[][] ns, int stu, int test){
int result = 0;
for(int i=1; i<=stu; i++){ // 기준학생
for(int j=1; j<=stu; j++){ // 비교학생
int cnt=0;
for(int k=0; k<test; k++){ // 시험차수
int pi=0, pj=0;
for (int s=0; s<stu; s++){ // 학생수
if(ns[k][s]==i) pi = s;
if(ns[k][s]==j) pj = s;
}
if(pi<pj) cnt++;
}
if(cnt==test){
result++;
}
}
}
return result;
}
}
- 특징
- 내 풀이의 경우 기준학생과 비교학생의 결과를 담을 배열을 미리 만들어 두고, 삼중루프를 통해 비교한 후 조건에 일치하는 값을 미리 만들어둔 배열에 누적. 테스트 개수만큼 모두 일치한 내용을 단일 루프로 따로 체크하여 값 반환함
- 풀이의 경우 초기부터 사중루프를 돌고, 내 풀이와 달리 학생을 기준으로 시험차수별 체크를 함. 여기서 순위만 뽑아서 조건문을 통해 기준학생이 우위일때 카운트 집계. 카운트가 시험수와 일치할때만 결과값 누적. 반복을 더 돌기는하나 따로 저장데이터를 만들거나 따로 전체 반복을 돌지않아도 됨
- 내 풀이의 경우 기준학생과 비교학생의 결과를 담을 배열을 미리 만들어 두고, 삼중루프를 통해 비교한 후 조건에 일치하는 값을 미리 만들어둔 배열에 누적. 테스트 개수만큼 모두 일치한 내용을 단일 루프로 따로 체크하여 값 반환함