알고리즘매일매일

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

이 문제는 학생수 1000명, 점수는 0점에서 100점으로 고정되어 있다.

주의할 점은 최빈수가 여러 개 일 때에는 가장 큰 점수를 출력해야 한다.

풀이

1. 점수를 세기 위한 count배열을 만들어 놓는다. 0점부터 100점이므로 크기는 101로 해야 한다.
2. 각 학생의 점수를 입력받아서 해당 점수를 index 값으로 count배열의 값을 1씩 증가시킨다.
3. 학생의 점수를 모두 입력받았으면 count배열에 최댓값과 그때의 index(점수)를 구해준다.
4. 이때 max값을 구하는 부분에서 <가 아닌 <= 를 사용해서 최빈수 중 가장 큰 점수가 저장되게 한다. (max 값이 같은 경우에 더 뒤의 값(더 큰 점수)으로 바뀌도록 해준다.)

import java.util.StringTokenizer;
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 num = Integer.parseInt(br.readLine());
			int[] count = new int[101];
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			int score = 0;
			for(int i=0; i<1000; i++) {
				score = Integer.parseInt(st.nextToken());
				count[score] += 1;
			}
			
			int max = 0; //최댓값을 저장
			int ans = 0; //최댓값을 가지고 있는 index(점수)
			for(int i=0; i<101; i++) {
				if(max <= count[i]) {
					max = count[i];
					ans = i;
				}
			}
			
			System.out.println("#"+tc+" "+ans);
		}
	}

}

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

이 문제는 Code Attack 문제이다. 다른 사람이 내 코드를 보고 input값을 넣어서 오류를 일으키면 공격에 성공한다.

그 말은 내 코드에 잘못된 부분이 있다는 뜻이므로 아직까지는 정확한 정답이 아닐 수도 있다...

풀이

1. 먼저 입력을 모두 받고 A사를 선택한 경우와 B사를 선택한 경우의 수도요금을 각각 계산해준다.
2. A사는 간단히 리터당 요금 P와 사용한 양 W를 곱해준 값이다.
3. B사는 내가 사용한 양 W가 R보다 작거나 같을 경우에는 기본 요금기본요금 Q이고, 그렇지 않을 경우에는 기본요금 Q + 추가로 사용한 양(W-R) * 추가 요금 S이다.
4. A사와 B사의 계산한 요금 중 더 작은 값을 출력한다.

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

public class Solution {

	static int P,Q,R,S,W;
	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());
			P = Integer.parseInt(st.nextToken());
			Q = Integer.parseInt(st.nextToken());
			R = Integer.parseInt(st.nextToken());
			S = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			
            
			int chargeA = W*P; //A사의 수도요금
			int chargeB;
			
            
            //B사의 수도요금 계산
			if(W <= R) {
				chargeB = Q; // 기본요금
			} else {
				int extra = W-R;
				chargeB = Q + extra*S;
			}
			
			if(chargeA > chargeB) {
				System.out.println("#"+tc+" "+chargeB);
			} else {
				System.out.println("#"+tc+" "+chargeA);
			}
		}
	}

}

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

}