알고리즘매일매일

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

시뮬레이션 문제. D2 치고는 조금 생각해야 하는 문제였다. (앞에서 푼 시각 덧셈이랑 난이도 차이가 꽤 있다.)

풀이

1. 입력을 모두 받은 후에 값이 1인 곳에 대해서만 모두 검색을 해준다.
2. 가로를 검사하는 경우와 세로를 검사하는 경우를 나누어 주었다.
   1. 세로를 검사하는 경우
      • 시작칸이 첫 번째 칸이거나 바로 앞의 칸 값이 0이어야 한다.
      • 현재 칸을 포함해서 아래로 K칸만큼이 범위를 벗어나면 안 된다.
      • 위의 조건을 만족한다면 현재 칸을 포함한 K칸만큼 동안 하나라도 0을 가지면 false
      • 현재 칸을 포함한 K칸 이후의 바로 다음 칸이 범위를 벗어나지 않는다면 0 값을 가지는지 확인해준다. (1 값을 가지면 false)
   2. 가로를 검사하는 경우도 똑같은 방식으로 j열에 대해서 검사해주면 된다.
3. check함수를 통해 true 값을 count 값을 증가시킨다.

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

public class Solution {

	static int N,K;
	static int[][] puzzle;
	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());
			K = Integer.parseInt(st.nextToken());
			puzzle = new int[N][N];
			
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<N; j++) {
					puzzle[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			int count = 0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(puzzle[i][j] == 0) continue; //단어가 들어갈수 없는 칸
					
					if(i == 0 || puzzle[i-1][j] == 0) { //첫번째 칸이거나 바로 앞에 칸이 0
						if(i+K <= N) { //범위를 넘어가지 않는 경우에만 검사
							if(checkSero(i,j)) {
								count += 1;
							}
						}
					}
					
					
					if(j == 0 || puzzle[i][j-1] == 0) { //첫번째 칸이거나 바로 앞에 칸이 0
						if(j+K <= N) { //범위를 넘어가지 않는 경우에만 검사
							if(checkGaro(i,j)) {
								count += 1;
							}
						}
					}
				}
			}
			
			System.out.println("#"+tc+" "+count);
			
		}
	}
	
	static boolean checkSero(int x, int y) {
		boolean flag = true;
		int n = x+K;
		for(int i=x; i<n; i++) {
			if(puzzle[i][y] == 0) {
				flag = false; //하나라도 0값이 있으면 false (단어를 넣을 수 없으면)
				break;
			}
		}
		if(x+K < N) {
			if(puzzle[x+K][y] == 1)
				flag = false; //넣을 단어보다 칸이 길면 false
		}
		
		return flag;
	}
	
	static boolean checkGaro(int x, int y) {
		boolean flag = true;
		int n = y+K;
		for(int j=y; j<n; j++) {
			if(puzzle[x][j] == 0) {
				flag = false; //하나라도 0값이 있으면 false (단어를 넣을 수 없으면)
				break;
			}
		}
		if(y+K < N) {
			if(puzzle[x][y+K] == 1)
				flag = false; //넣을 단어보다 칸이 길면 false
		}
		
		return flag;
	}

}

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

시 단위는 12가 넘어가면 12를 빼주고, 분 단위는 60을 넘어가면 분에서 60을 빼주는대신 시 단위에 1을 더해준다.

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

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 h1 = Integer.parseInt(st.nextToken());
			int m1 = Integer.parseInt(st.nextToken());
			int h2 = Integer.parseInt(st.nextToken());
			int m2 = Integer.parseInt(st.nextToken());
			
			int hour = h1+h2;
			if(hour > 12) hour -= 12;
            
			int minute = m1+m2;
			if(minute > 60) {
				minute -= 60;
				hour += 1;
			}
			
			System.out.println("#"+tc+" "+hour+" "+minute);
		}
	}

}

문제

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

지도의 한 변의 길이 N은 3 이상 8 이하의 정수이다. (3 ≤ N ≤ 8)
최대 공사 가능 깊이 K는 1 이상 5 이하의 정수이다. (1 ≤ K ≤ 5)
지도에서 가장 높은 봉우리는 최대 5개이다.
-> 이 조건들을 통해 완전 탐색을 해도 되겠다고 생각했다.

예전에 BFS로 길이를 배열에 저장해가며 풀었다가 메모리를 너무 많이 사용해서 DFS로 다시 풀었다.

DFS로 푸는 게 최대 depth를 저장하면 되므로 BFS보다 더 효율적인 듯하다.

BFS로도 잘 처리해주면 될 것 같지만 문제 맥락상(?) DFS가 더 맞는 것 같다.

문제를 잘 생각하고 알고리즘 사용하자!!

풀이

1. 값을 처음에 입력받으면서 가장 큰 값을 top 변수에 저장한다.
2. 배열을 탐색하며 top값과 같은 곳의 좌표를 ArrayList에 저장한다.
3. 모든 위치에 대해서 0번에서 K번 깎는 경우까지 모든 길이를 구해서 최댓값을 max에 저장한다.
4. max 출력.

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

public class Solution {
	static class Pair {
		int x;
		int y;
		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
    
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static int N, K, max;
	static int[][] map;
	static boolean[][] check;
	static ArrayList<Pair> topList;
    
	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());
			K = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			topList = new ArrayList();
			
			int top = 0; //가장 높은 봉우리의 값을 저장
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if(top < map[i][j]) top = map[i][j];
				}
			}
			
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(map[i][j] == top) topList.add(new Pair(i,j));
				}
			}
            
			max = 0;
			construct();
			System.out.println("#"+tc+" "+max);
		}
	}
	
	static void construct() {
		for(int k=0; k<=K; k++) {
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					map[i][j] -= k;
					for(int l=0; l<topList.size(); l++) { //가장 높은 봉우리들에서부터 경로 탐색
						int x = topList.get(l).x;
						int y = topList.get(l).y;
						if(x == i && y == j) continue; //현재 탐색할 가장 높은 봉우리를 공사한 경우
						check = new boolean[N][N];
						check[x][y] = true;
						int tmp = dfs(x,y,1);
						if(tmp > max) max = tmp;
						
					}
					map[i][j] += k;
				}
			}
		}
	}
	
	static int dfs(int x, int y, int depth) {
		int d = depth;
        
		for(int i=0; i<4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			if(check[nx][ny]) continue;
			if(map[nx][ny] >= map[x][y]) continue;
            
			check[nx][ny] = true;
			d = Math.max(d,dfs(nx,ny,depth+1));
			check[nx][ny] = false;
			
		}

		return d;
	}

}

문제

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=AWXRUN9KfZ8DFAUo

문제

각 변에 다음과 같이 16진수 숫자(0~F)가 적혀 있는 보물상자가 있다.

보물 상자의 뚜껑은 시계방향으로 돌릴 수 있고, 한 번 돌릴 때마다 숫자가 시계방향으로 한 칸씩 회전한다.

각 변에는 동일한 개수의 숫자가 있고, 시계방향 순으로 높은 자리 숫자에 해당하며 하나의 수를 나타낸다.

보물상자에는 자물쇠가 걸려있는데, 이 자물쇠의 비밀번호는 보물 상자에 적힌 숫자로 만들 수 있는 모든 수 중, K번째로 큰 수를 10진 수로 만든 수이다.

N개의 숫자가 입력으로 주어졌을 때, 보물상자의 비밀 번호를 출력하는 프로그램을 만들어보자.

(서로 다른 회전 횟수에서 동일한 수가 중복으로 생성될 수 있다. 크기 순서를 셀 때 같은 수를 중복으로 세지 않도록 주의한다.)

 풀이

1. 상자의 변은 4개 이므로 N/4 만큼 회전을 하면 처음과 같은 상태가 되므로 N/4번 동안 각 변을 16진수 정수로 만들어주고(findPWD) 회전해주는(Rotate) 과정을 반복한다.
   1. 문자열을 N/4 크기만큼 잘라서 16진수 정수로 변환하여 box배열에 저장한다.
   2. box 배열에 들어있는 값이 현재 list에 존재하지 않는다면 list에 추가(중복 제거)
   3. 문자열의 마지막 문자를 맨 앞에 붙여줘서 회전을 해준다.
2. 모든 가능한 16진수를 만들어줬으면 정렬해준 후 K번째 큰 수를 구한다.
   1. K번째 큰 수를 10진수로 변환하기 위해 먼저 String으로 변환한다.
   2. String을 다시 10진수로 변환해서 출력.

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

public class Solution {
	static int N;
	static String s;
	static ArrayList&ltInteger> list;
	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());
			int K = Integer.parseInt(st.nextToken());
			s = br.readLine();
			list = new ArrayList&ltInteger>();

			for(int i=0; i<N/4; i++) {
				findPWD();
				rotate();
			}
			
			Collections.sort(list);
			String tmp = Integer.toString(list.get(list.size()-K));
			int ans = Integer.parseInt(tmp, 10);
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static void findPWD() {
		int[] box = new int[4];
		int k = N/4;
		
		int index = 0;
		for(int i=0; i<N; i+=k) {
			String tmp = s.substring(i, i+k);
			box[index++] = Integer.parseInt(tmp,16);
		}
		
		for(int i=0; i<4; i++) {
			if(!list.contains(box[i])) {
				list.add(box[i]);
			}
		}
	}
	
	static void rotate() {
		String last = s.substring(N-1);
		s = last+s.substring(0, N-1);
	}
}

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);
		}
	}

}