알고리즘매일매일

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

풀이

1. 먼저 처음 N값을 문자열로 저장(s) 받은 후에 정수형(n)으로도 따로 저장해줬다.
2. 0부터 9까지의 숫자를 모두 보았는지 확인하기 위해 check 배열과 count 변수를 사용하였다.
3. 문자열을 한칸씩 정수로 변환하여 check배열에 있는지 확인하였고 없으면 count 변수를 증가하고 true값으로 바꿔준다.
4. count 변수가 10이 되면 10개의 숫자를 모두 봤다는 의미이므로 break해준다.
5. 10개를 모두 보지 못했다면 xN번 숫자를 확인하기 위해 x * n 값을 문자열로 변환하여 s에 저장해준다.
6. 10개의 숫자를 모두 봐서 반복문을 빠져나왔다면 그때의 문자열(s)을 출력해준다.

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();
			int n = Integer.parseInt(s);
            
            
            //0-9까지의 숫자를 모두 봤는지 확인
			boolean check[] = new boolean[10];
			int count = 0;
			
            
			int x=1; //입력받은 n에 계속 곱해줄 변수
			while(true) {
				for(int i=0; i<s.length(); i++) {
                	//한글자씩 정수로 변환하여 확인
					int tmp = Integer.parseInt(s.substring(i,i+1));
					if(check[tmp] == false) {
						count++;
						check[tmp] = true;
					}
				}
				
                //10개를 모두 봤다
				if(count == 10) break;
				
				x++;
				s = Integer.toString(n*x);
			}
			
			System.out.println("#"+tc+" "+s);
			
			
		}
	}

}

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

java에서는 Base64 라이브러리가 있어서 쉽게 구현할 수 있었다.

한 번 직접 구현해봐도 좋을 것 같다.

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

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 encoded = br.readLine();
            String decoded = new String(Base64.getDecoder().decode(encoded));
            System.out.println("#"+tc+" "+decoded);
           
		}
	}

}

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

D2문제 중 가장 맨 앞에 있지만 아껴뒀던 문제이다. 문제를 처음 봤을 때 어떻게 풀어야 될지 감이 안 왔고 정답률도 낮았기 때문이다.

먼저 처음에 완전 탐색을 해야 하나? 했지만 N 범위가 너무 커서 포기했다.

어떻게 풀어야 하나 고민하다가 다른 분들이 뒤에서부터 풀면 된다고 쓴 댓글을 보고 힌트를 얻고 풀었다ㅠㅠ

풀이

1. 먼저 N 을 입력받으면 N크기의 배열 생성 후에 매매가를 저장한다.
2. 뒤(N-1)부터 계산을 해준다.
3. 밑의 코드에서 i 변수는 파는 날, j 변수는 사는 날이 된다.
4. 앞의 날의 매매가가 현재 매매가보다 작은 동안 계속 tmp(임시 변수)에다가 현재 매매가를 더해주고 앞의 매매가는 빼준다.(파는 값은 더해주고 사는 값은 빼줌)
5. j가 0보다 작아지거나(첫 날 보다 앞) 현재 매매가보다 큰 값을 발견하면 while문을 종료
6. tmp를 ans(최대 이익)에 더해주고 i값을 j+1 값으로 바꿔준다.
   • (파는 날짜를 바꿔준다)
   • (j값이 되어야 하는데 for문에서 바로 i--가 되므로 +1을 해줌)
7. 모든 날짜에 대해 계산을 해줬으면 ans 출력.

여기서 주의할 점은 ans 는 long 타입을 사용하여야 한다. 매매가는 최대 10,000이고 날짜는 최대 1,000,000이므로 최대치를 계산했을 때 int 형의 범위를 넘어갈 수 있다.

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());
		StringTokenizer st;
        
		for(int tc=1; tc<=T; tc++) {
			int N = Integer.parseInt(br.readLine());
			int[] price = new int[N];
            
            
            //매매가를 저장
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<N; i++) {
				price[i] = Integer.parseInt(st.nextToken());
			}
			
            
			long ans = 0; //long 타입 사용!
            
            //맨 마지막 날짜부터 계산
            //i 날짜가 파는 날, j 날짜가 사는 날이 된다.
			for(int i=N-1; i>=0; i--) {
				
				int j = i-1; //현재 파는 날짜보다 바로 앞의 날짜들을 검사
				int tmp = 0;
				while(j >= 0 && price[i] > price[j]) {
					tmp += price[i]; //파는 날의 매매가를 더해준다.
					tmp -= price[j]; //사는 날의 매매가를 빼준다.
					j--; //앞의 날짜로 이동
				}
                
				ans += tmp; //이익에 더해준다.
				i = j+1; //파는 날을 옮겨준다.
			}
			
			System.out.println("#"+tc+" "+ans);
		}
	}

}

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

풀이

1. 먼저 각 자석의 자성 정보를 배열에 저장한다.
2. 입력받은 K번만큼 실행
   1. 회전시킬 자석 번호와 방향을 입력받는다.
   2. 처음 상태에 따라서 회전할지 안 할지가 결정되므로 미리 회전방향을 배열에 저장해놓는다.
   3. 회전시킬 자석의 오른쪽과 왼쪽의 자석들을을 각각 순차적으로 검사한다.
   4. 앞의 자석의 2번째 날과 뒤의 자석의 6번째 날을 비교한다.
   5. 같으면 그쪽 방향의 자석들은 회전하지 않을 것이므로 break
   6. 다르면 현재 회전하는 자석의 반대 방향으로 회전 방향을 저장한다.
   7. 각 자석을 위에서 저장한 회전 정보를 이용하여 회전시켜준다.
      1. 0인 경우는 회전하지 않는 자석
      2. 1인 경우는 시계방향 회전
      3. -1인 경우는 반시계 방향 회전
3. K번만큼의 회전이 끝난 후에 총점을 계산해준다.
4. 1,2,4,8 순으로 점수가 늘어나므로 left shift (<<) 연산을 사용해서 sum 변수에 더해줬다.

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());
		StringTokenizer st;
		for(int tc=1; tc<=T; tc++) {
			int K = Integer.parseInt(br.readLine());
			int[][] info = new int[4][8];
			for(int i=0; i<4; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<8; j++) {
					info[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
            //명령을 K번 실행
			for(int i=0; i<K; i++) {
				st = new StringTokenizer(br.readLine());
				int num = Integer.parseInt(st.nextToken())-1;
				int dir = Integer.parseInt(st.nextToken());
                
				int[] rotation = new int[4]; //회전할 방향을 저장
				rotation[num] = dir;
				
                
                //오른쪽 자석들을 검사
				for(int j=num+1; j<4; j++) {
					if(info[j-1][2] == info[j][6]) //자성이 같으면 회전하지 않는다.
						break;
					else
						rotation[j] = -rotation[j-1];
				}
				
                
                //왼쪽 자석들을 검사
				for(int j=num-1; j>=0; j--) {
					if(info[j][2] == info[j+1][6]) //자성이 같으면 회전하지 않는다.
						break;
					else
						rotation[j] = -rotation[j+1];
				}
				
				
                //각 자석을 회전시킨다.
				for(int j=0; j<4; j++) {
					if(rotation[j] == 0) continue; //회전하지 않는 경우
					else if(rotation[j] == 1) { // 시계방향 회전
						int tmp = info[j][7];
						for(int k=7; k>0; k--) {
							info[j][k] = info[j][k-1];
						}
						info[j][0] = tmp;
					} else if(rotation[j] == -1) { // 반시계방향 회전
						int tmp = info[j][0];
						for(int k=0; k<7; k++) {
							info[j][k] = info[j][k+1];
						}
						info[j][7] = tmp;
					}
				}
				
			}
			
            
            //모든 실행이 끝난 후 총합을 계산
			int sum = 0;
			for(int i=0; i<4; i++) {
				if(info[i][0] == 1) {
					sum += 1<<i;
				}
			}
			
			System.out.println("#"+tc+" "+sum);
		}	
	}

}

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

풀이

1. command를 입력받아서 0이 아닌 경우(1이나 2인 경우) 에만 따로 처리를 해준다.
   1. 1 인경우(가속) 기존 속도에 가속도를 더해준다.
   2. 2 인경우(감속) 기존 속도에서 가속도를 빼준다. (문제의 조건에 따라 가속도가 기존 속도보다 클경우에는 속도는 0이 된다.)
2. 매 초마다 속도만큼을 거리에 더해준다(초속이므로)
3. 시간이 모두 끝난 후 거리를 출력

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++) {
			int time = Integer.parseInt(br.readLine()); //시간
			int rc = 0; //속도
			int dis = 0; //거리
            
			for(int i=0; i<time; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int command = Integer.parseInt(st.nextToken());
				
				if(command != 0) {
					int accel = Integer.parseInt(st.nextToken()); //가속도
                    
					if(command == 1) { //가속
						rc += accel;
					} else { //감속
						if(rc < accel) {
							rc = 0;
						} else {
							rc -= accel;
						}
					}
                    
				}
                
				dis += rc;
			}
			System.out.println("#"+tc+" "+dis);
		}
	}

}

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

풀이

1. 2,3,5,7,11이 계속 나누어 떨어질 때까지 각 변숫값(a, b, c, d, e)을 증가시킨다.

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 a = 0;
			int b = 0;
			int c = 0;
			int d = 0;
			int e = 0;
			
			int tmp = N;
			while(tmp%2 == 0) {
				a++;
				tmp /= 2;
			}
			
			tmp = N;
			while(tmp%3 == 0) {
				b++;
				tmp /= 3;
			}
			
			tmp = N;
			while(tmp%5 == 0) {
				c++;
				tmp /= 5;
			}
			
			tmp = N;
			while(tmp%7 == 0) {
				d++;
				tmp /= 7;
			}
			
			tmp = N;
			while(tmp%11 == 0) {
				e++;
				tmp /= 11;
			}
			
			System.out.println("#"+tc+" "+a+" "+b+" "+c+" "+d+" "+e);
		}
	}

}

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

풀이

1. 알파벳과 개수를 각각 char배열과 Int배열에 저장한다.
2. 알파벳과 숫자 쌍의 개수(N)만큼 반복
   1. 각 알파벳의 숫자 만큼 알파벳을 출력한다.
   2. 출력을 10번할때마다 한 줄 띄어준다.

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++) {
        
			int n = Integer.parseInt(br.readLine());
			char[] c = new char[n]; //알파벳을 저장
			int[] num = new int[n]; // 알파벳 개수를 저장
			
            
			for(int i=0; i<n; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				c[i] = st.nextToken().charAt(0);
				num[i] = Integer.parseInt(st.nextToken());
			}
			
            
			System.out.println("#"+tc);
			int cnt=0; // 출력 횟수
			for(int i=0; i<n; i++) {
				for(int j=0; j<num[i]; j++) {
					System.out.print(c[i]);
					cnt++;
					if(cnt == 10) {
						System.out.println();
						cnt = 0;
					}
				}
				
			}
			System.out.println();
			
		}
	}

}

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

풀이

1. 월별로 일수를 배열에 미리 저장해둔다.
2. 첫 번째 달 일수를 미리 합에 저장
3. 두 번째 달부터 마지막 달까지의 합을 모두 합에 더하고
4. 마지막 달 전체 일수에서 입력받은 일수를 빼준값을 다시 합에서 빼준다.

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());
		int[] date = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; //월별 일수를 미리 저장
		
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int m1 = Integer.parseInt(st.nextToken())-1;
			int d1 = Integer.parseInt(st.nextToken());
			int m2 = Integer.parseInt(st.nextToken())-1;
			int d2 = Integer.parseInt(st.nextToken());
			
			
			int sum = date[m1]-d1+1; //첫 번째 달을 합에 미리 저장
            
            //두 번째 달부터 마지막 달까지 모두 합해준다.
			for(int i=m1+1; i<=m2; i++) {
				sum += date[i];
			}
            
            //마지막 달의 일수에서 입력받은 두 번째 일수를 빼준 값을 총 합에서 빼준다.
			sum -= date[m2]-d2;
            
			System.out.println("#"+tc+" "+sum);
		}
	}

}