[1일1커밋 4D] LeetCode SQL & 백준 JAVA 11723, 9655 (비트 뭐시기와 DP)

사실 어제 올렸어야했는데🙃 어제 중요한 모임 이슈로 인해 밀려서 올리는 4일차 1일1커밋 기록

 

LeetCode SQL 50

Basic Joins | 581. Customer Who Visited but Did Not Make Any Transactions

select customer_id, count(*) as count_no_trans
from Visits v
left outer join Transactions t
on v.visit_id = t.visit_id
where transaction_id is null
group by customer_id

 

Basic Aggregate Functions | 1075. Project Employees I

select project_id, round(sum(experience_years)/count(*),2) average_years
from Project p
join Employee e
on p.employee_id = e.employee_id
group by project_id

 

Advanced Select and Joins | 1731. The Number of Employees Which Report to Each Employee

select
    e2.employee_id
    , e2.name
    , count(*) reports_count
    , round(sum(e1.age)/count(*)) average_age
from Employees e1 # employees
join Employees e2 # reports_to
on e1.reports_to = e2.employee_id
where e2.employee_id is not null
group by employee_id
order by employee_id

 

---

 

BaekJoon 백준 

11723. 집합 https://www.acmicpc.net/problem/11723

실버5 | 구현, 비트마스크

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int m = sc.nextInt();
		
		Set<Integer> s = new HashSet<Integer>(); 
		String input;
		int x = 0;
		
		for(int i=0; i<m; i++) {
			input = sc.next();
			if(!input.equals("all") && !input.equals("empty")) {
				x = sc.nextInt();
			}
			
			switch(input) {
			case "add" : 
				s.add(x);
				break;
			case "remove" : 
				s.remove(x);
				break;
			case "check" :
				if(s.contains(x)) System.out.println("1");
				else System.out.println("0");
				break;
			case "toggle" :
				if(s.contains(x)) s.remove(x);
				else s.add(x);
				break;
			case "all" :
				List<Integer> newList = new ArrayList<>(
						Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20));
				s = new HashSet<>(newList);
				break;
			case "empty" :
				s.clear();
				break;
			}
		}
	}
}

문제 제목에 걸맞게 당당하게 집합으로 풀었지만 시간초과 나온 답안

 

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

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int m = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		
		Set<Integer> s = new HashSet<Integer>(); 
		String input;
		int x = 0;
		
		for(int i=0; i<m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			input = st.nextToken();
			if(st.hasMoreTokens()) {
				x = Integer.parseInt(st.nextToken());
			}
			
			switch(input) {
			case "add" : 
				s.add(x);
				break;
			case "remove" : 
				s.remove(x);
				break;
			case "check" :
				if(s.contains(x)) sb.append("1\n");
				else sb.append("0\n");
				break;
			case "toggle" :
				if(s.contains(x)) s.remove(x);
				else s.add(x);
				break;
			case "all" :
				List<Integer> newList = new ArrayList<>(
						Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20));
				s = new HashSet<>(newList);
				break;
			case "empty" :
				s.clear();
				break;
			}
		}
		
		System.out.println(sb);
	}
}

결국 BufferedReader와 StringBuilder 사용해서 시간통과 해결

일단 문제 푸는 것이 중요하기에 수행 시간은 나한테 고려 요소가 아니였다. 그래서 항상 Scanner로 문제를 풀었었는데.. 위 두 클래스도 꼭 알아둬야할거같다.

• BufferedReader

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
String input = st.nextToken();
if(st.hasMoreTokens()) {
	Integer input = Intger.parseInt(st.nextToken);
}

• StringBuilder

StringBuilder sb = new StringBuilder();
sb.append("출력할 내용\n");
System.out.println(sb);

• BuffredWriter & StringBuilder

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringBuilder sb = new StringBuilder();
sb.append("출력할 내용\n");
bw.write(sb.toString());

 

⭐️ 다른 풀이들 찾아보니 해당 문제는 비트 마스크로 푸는 문제라고 한다. 그게 몬데..

정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라고 한다. 비스 마스크를 사용하면 수행 시간이 더 빠르고 메모리 사용을 적게 한다.

참고 - [알고리즘] 비트마스킹(bitmasking)이란 https://travelbeeee.tistory.com/451

[알고리즘] 비트마스킹(bitmasking) 이란

참고 - [백준 11723 : JAVA] 집합 / 비트마스크 https://dragon-h.tistory.com/28

[백준 11723 : JAVA] 집합 / 비트마스크

별로.. 알고싶지않아요..

 

9655. 돌게임 https://www.acmicpc.net/problem/9655

실버5 | 수학, 다이나믹 프로그래밍

고민을 좀 했지만 규칙을 찾고 나면 쉬웠던 문제(살짝 다른 사람 코드 참고하긴 함)

import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		System.out.println((n%2)==1 ? "SK" : "CY");
	}
}

1개 또는 3개를 가져감으로 SK와 CY가 돌을 가져갈 수 있는 경우의 수는 다음과 같다.

• (SK, CY) / (1, 1), (1,3), (3, 1), (3,3) 

둘이 한번씩 돌을 가지고 가면 모두 짝수개로 끝난다. 즉 돌이 총 짝수개이면 마지막으로 CY가 가져가는 것이고, 홀수개라면 다음 타자인 SK가 가져가게 된다.

 

문제 유형이 DP인 만큼 DP(Dynamic Programming)로 풀수있다고 한다. 

⭐️ DP(다이나믹 프로그래밍, 동적 계획법)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘이다. 문제 해결을 위한 알고리즘 설계 방법이나 접근 방식을 말한다.

 

import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		int[] dp = new int[1001];
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 3;
		
		for(int i=0; i<=n; i++) {
			dp[i] = Math.min(dp[i-1], dp[i-3]) + 1;
		}
		
		if(dp[n]%2 == 0) System.out.println("CY");
		else System.out.println("SK");
	}
}

• n=1 : 상근이가 승
• n=2 :  상근이가 1개 가져간 뒤 창영이가 남은 1개 가져가면 창영이가 승
• n=3 : 상근이가 처음 3개 가져가면 상근이가 승
• n=4 : 상근이가 처음 1개를 가져가든 3개를 가져가든, 돌이 남음으로 창영이가 승
• n=5 : 상근이가 승
  • 상근이가 1개 가져간 경우, 4개가 남고 창영이가 1개 또는 3개를 가져가도 남음으로 상근이가 승
  • 상근이가 3개 가져간 경우, 2개 중 창영이는 1개만 가져갈 수 있음으로 상근이가 승
• n이 4 이후부터는 한 턴에 상근이와 창영이가 4개씩 가져갈 수 있게 되어 패턴이 반복된다.
• n개의 돌 중 1개를 뺀 n-1개의 돌에서 완벽한 게임을 해 이긴 승리자가 dp에 저장된다. 1개의 돌이 남아 한 번의  순서가 더 돌면(+1) 반대의 사람이 승리자가 된다.

이해가 될듯말듯.. 동적 계획법 문제좀 풀어봐야겠다.

 

 

하나 더 풀고같이 올리고 싶었지만 시간 관계상 + 피곤 이슈로 일단 4일차 여기서 마무리