알고리즘매일매일

문제

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PwGK6AcIDFAUq&categoryId=AV5PwGK6AcIDFAUq&categoryType=CODE

풀이

1. 평점을 미리 배열에 저장한다.
2. 한 학생의 점수들이 주어질 때마다 총점을 구해서 배열에 저장한다.
3. K번째 학생의 점수를 따로 저장해놓는다.
4. 학생들의 점수를 저장한 배열을 정렬한 후에 K번째 학생의 점수를 찾아서 해당 index를 따로 저장한다.
5. 위에서 저장한 index값을 (N/10)으로 나누면 평점 배열의 index가 된다. (N/10 만큼씩 동일한 평점을 받기 때문)
6. 위에서 구한 평점 배열의 index값으로 평점 배열 값을 출력.

import java.io.*;
import java.util.*;

public class Solution {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		String[] grade = {"D0","C-","C0","C+","B-","B0","B+","A-","A0","A+"};
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken())-1;
			int[] total = new int[N];
            
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				int midScore = Integer.parseInt(st.nextToken());
				int finalScore = Integer.parseInt(st.nextToken());
				int homework = Integer.parseInt(st.nextToken());
				total[i] = midScore*35 + finalScore*45 + homework*20; //총점의 값 자체는 중요하지 않으므로 정수형으로 곱해줬다.
			}
            
			int score = total[K];
			Arrays.sort(total);
			int index = -1;
			for(int i=0; i<N; i++) {
				if(total[i] == score) {
					index = i; //K번째 학생의 성적 위치
					break;
				}
			}
            
			int ans = index/(N/10);
			System.out.println("#"+tc+" "+grade[ans]);
			
		}
	}

}

문제

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5Pw_-KAdcDFAUq&categoryId=AV5Pw_-KAdcDFAUq&categoryType=CODE

풀이

1. 10개의 수라고 정해져 있으므로 10개를 입력받은 후에 정렬해준다.
2. 맨 앞과 맨 뒤를 제외한 값들을 모두 더해서 평균을 구한다.
3. 반올림을 위해서 실수형에서 연산한 뒤에 반올림해준 후 정수형으로 출력.
4. 최대 수, 최소 수가 여러개 있는 경우를 고려해주지 않아도 Pass 했다.

주의할 점

소수점 첫째 자리에서 반올림한 정수를 출력한다.

import java.io.*;
import java.util.*;

public class Solution {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int[] arr = new int[10];
			for(int i=0; i<10; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			Arrays.sort(arr);
			int sum = 0;
			for(int i=1; i<9; i++) {
				sum += arr[i];
			}
			float tmp = (float)sum/8;
			int ans = Math.round(tmp); //반올림
			System.out.println("#"+tc+" "+ans);
		}
	}

}

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PxmBqAe8DFAUq

문제

1부터 N까지의 숫자에서 홀수는 더하고 짝수는 뺐을 때 최종 누적된 값을 구해보자.

풀이

1부터 N까지의 숫자를 순차적으로 짝수인 경우(2로 나누어 떨어지는 경우) 빼주고, 홀수인 경우에는 더해준다.

import java.io.*;

public class Zigzag {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			int n = Integer.parseInt(br.readLine());
			int ans = 0;
			for(int i=1; i<=n; i++) {
				if(i%2 == 0)
					ans -= i;
				else
					ans += i;
			}
			System.out.println("#"+tc+" "+ans);
		}
	}

}

https://www.swexpertacademy.com/main/code/problem/problemSolver.do?contestProbId=AV5PyTLqAf4DFAUq

문제

"level"과 같이 거꾸로 읽어도 제대로 읽은 것과 같은 문장이나 낱말을 회문(回文, palindrome)이라 한다.
단어를 입력받아 회문이면 1을 출력하고, 아니라면 0을 출력하는 프로그램을 작성하라.

풀이

입력받은 문자열의 뒷부분부터 새로운 문자열에 붙여주고, 입력받은 문자열과 새로 만든 문자열이 같으면 1을 출력.

import java.io.*;

public class Solution {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1;tc<=T;tc++) {
			String s = br.readLine();
			String pel = "";
			for(int i=s.length()-1; i>=0; i--) {
				pel += s.substring(i,i+1);
			}
			if(s.equals(pel)) System.out.println("#"+tc+" "+1);
			else System.out.println("#"+tc+" "+0);
		}
	}

}

문제

N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개수를 의미한다.
M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다.
죽은 파리의 개수를 구하라!

[제약 사항]
1. N 은 5 이상 15 이하이다.
2. M은 2 이상 N 이하이다.
3. 각 영역의 파리 갯수는 30 이하 이다.

풀이

1. n과 m의 범위가 작기 때문에 모든 경우를 해줘도 될 것 같다.
2. i <= (n-m), j<=(n-m) 의 범위에서 모든 (i,j)에 대하여 (i,j)를 시작점으로 하는 M X M 크기의 사각형 내의 파리의 합을 구해준다.
3. 합을 매번 최대 값과 비교하여 최댓값을 구한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	static int max, n, m;
	static int[][] area;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			area = new int[n][n];
			for(int i=0; i<n; i++) {
				st = new StringTokenizer(br.readLine()," ");
				for(int j=0; j<n; j++) {
					area[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			max = 0;
            //모든 경우의 수를 구한다.
			for(int i=0; i<=n-m; i++) {
				for(int j=0; j<=n-m; j++) {
					getMax(i,j);
				}
			}
			System.out.println("#"+tc+" "+max);
		}
	}
	
	static void getMax(int x, int y) {
		int sum = 0;
		for(int i=x; i<x+m; i++) {
			for(int j=y; j<y+m; j++) {
				sum += area[i][j];
			}
		}
		if(max < sum) max = sum;
	}

}

문제

크기가 N인 파스칼의 삼각형을 만들어야 한다.
파스칼의 삼각형이란 아래와 같은 규칙을 따른다.
1. 첫 번째 줄은 항상 숫자 1이다.
2. 두 번째 줄부터 각 숫자들은 자신의 왼쪽과 오른쪽 위의 숫자의 합으로 구성된다.
N이 4일 경우,
 

N을 입력받아 크기 N인 파스칼의 삼각형을 출력하는 프로그램을 작성하시오.

풀이

1. n*n 배열에 저장하여 푼다.
2. (0,0)부터 시작하여 행이 i번째 일 때, 열(j)은 i번째 까지 존재한다.
   1. 각 행에서 0번 index 이거나 마지막 index(i번째)인 경우에는 1.
   2. 그 외의 i행 j열의 값은 i-1행의 j-1열값과 i-1행의 j열 값을 더한 값이다.

import java.io.*;

public class Solution {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			int n = Integer.parseInt(br.readLine());
			int[][] arr = new int[n][n];
			arr[0][0] = 1;
			for(int i=1; i<n; i++) {
				for(int j=0; j<=i; j++) {
					if(j==0 || j==i) {
						arr[i][j] = 1;
					} else {
						arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
					}
				}
			}
			System.out.println("#"+tc);
			for(int i=0; i<n; i++) {
				for(int j=0; j<=i; j++) {
					System.out.print(arr[i][j]+" ");
				}
				System.out.println();
			}
		}
	}

}

문제

패턴에서 반복되는 부분을 마디라고 부른다. 문자열을 입력받아 마디의 길이를 출력하는 프로그램을 작성하라.

풀이

1. 반복되는 패턴을 저장할 String 변수 pattern의 길이를 하나씩 늘려주며 비교한다.
2. i-1번째까지를 pattern 변수에 넣었을때 기존에 입력받은 문자열의 i번째부터 길이 i만큼을 잘라서 새로 tmp 만큼에 넣는다.
3. pattern과 tmp 가 같으면 pattern변수의 길이를 출력하고 종료.

import java.io.*;
public class Solution {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			String s = br.readLine();
			for(int i=1; i<=s.length(); i++) {
				String pattern = s.substring(0, i);
				String tmp = s.substring(i,i+i);
				if(pattern.equals(tmp)) {
					System.out.println("#"+tc+" "+pattern.length());
					break;
				}
			}			
		}	
	}
}

문제

입력으로 정수 N 이 주어졌을 때, 1~N 까지의 숫자를

게임 규칙에 맞게 출력하는 프로그램을 작성하라.

박수를 치는 부분은 숫자 대신, 박수 횟수에 맞게 “-“ 를 출력한다.

여기서 주의해야 할 것은 박수 한 번 칠 때는 - 이며, 박수를 두 번 칠 때는 - - 가 아닌 -- 이다. 

N은 10이상 1,000이하의 정수이다. (10 ≤ N ≤ 1,000)

풀이

1.  먼저 3,6,9를 포함하는지 확인하기 위해 1부터 n까지의 숫자를 String으로 변환한다.
2. String s에 3이나, 6, 9가 포함되어 있는 경우에 3,6,9 는 - 로 바꿔주고, 나머지 숫자는 없애준다.

import java.util.*;
import java.io.*;
public class Solution {
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i=1; i<=n; i++) {
            String s = Integer.toString(i);
            if(s.contains("3") || s.contains("6") || s.contains("9")) {
                s = s.replace("3", "-");
                s = s.replace("6", "-");
                s = s.replace("9", "-");
                s = s.replace("1", "");
                s = s.replace("2", "");
                s = s.replace("4", "");
                s = s.replace("5", "");
                s = s.replace("7", "");
                s = s.replace("8", "");
                s = s.replace("0", "");
            }
            System.out.print(s+" ");
        }
    }
}