728x90

36번 잃어버린 괄호


내가 떠올린 풀이 해설

가장 작은 최솟값을 만들기 위해서는 가능한 큰 수를 빼야 된다. 수식이 더하기 빼기로만 되어있기 때문에 더하기 부분에 괄호를 쳐서 먼저 모두 계산한 후 빼기를 실행한다.


정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1541 {
	static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String st = br.readLine();
		String []str = st.split("-");
		
		for(int i = 0; i < str.length; i++) {
			int tmp = mySum(str[i]);
			if(i == 0) {
				answer = answer + tmp;
			}
			else {
				answer = answer - tmp;
			}
		}
		System.out.println(answer);
	}
	private static int mySum(String a) {
		int sum = 0;
		String temp[] = a.split("[+]");
		for(int i = 0; i < temp.length; i++) {
			sum += Integer.parseInt(temp[i]);
		}
		return sum;
	}
}

46번 특정 거리의 도시 찾기


내가 떠올린 풀이 해설

모든 도로 거리가 1이므로 가중치 없는 인접리스트로 표현할 수 있다. 도시의 개수가 300,000, 도로의 최대 크기가 1,000,000이므로 BFS 탐색으로 해결할 수 있다. 최초에는 방문 도시가 1이고, 이동하지 않았으므로 방문 배열에 0을 저장한다. 이후 방문하는 도시는 이전 도시의 방문 배열 값 +1을 방문 배열에 저장한다. 탐색 종료 후 방문 배열에 값이 k와 같은 도시의 번호를 출력한다.


정확한 풀이

import java.io.*;
import java.util.*;
public class Baek18352 {
	static int [] visit;
	static ArrayList<Integer>[] list;
	static List<Integer> answer;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[n + 1];
		visit = new int[n + 1];
		answer = new ArrayList<>();
		
		for(int i = 1; i <= n; i++) {
			list[i] = new ArrayList<>();
		}
		
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			list[s].add(e);
		}
		for(int i = 1; i <= n; i++) {
			visit[i] = -1;
		}
		BFS(x);
		for(int i = 1; i <= n; i++) {
			if(visit[i] == k) {
				answer.add(i);
			}
		}
		if(answer.isEmpty()) {
			System.out.println(-1);
		}
		else {
			Collections.sort(answer);
			for(int b : answer) {
				System.out.println(b);
			}
		}
	}
	private static void BFS(int x) {
		Queue<Integer> que = new LinkedList<>();
		que.add(x);
		visit[x]++;
		while(!que.isEmpty()) {
			int now = que.poll();
			for(int i : list[now]) {
				if(visit[i] == -1) {
					visit[i] = visit[now] + 1;
					que.add(i);
				}
				
			}
		}
		
	}
}

47번 효율적인 해킹


내가 떠올린 풀이 해설

모든 노드를 각각 BFS 탐색 알고리즘을 적용해 탐색한다. 탐색을 수행하면서 탐색되는 노드들의 신뢰도를 증가시켜 준다. 탐색 종료후 신뢰도 배열을 탐색해 신뢰도의 최댓값을 Max값으로 지정하고, 신뢰도 배열을 다시 탐색하면서 Max값을 가진 노드를 오름차순으로 출력한다.


정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1325 {
	static int []answer;
	static ArrayList<Integer>[] list;
	static boolean []visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[n + 1];
		visit = new boolean[n + 1];
		answer = new int [n + 1];
		for(int i = 1; i <= n; i++) {
			list[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			list[s].add(e);
		}
		for(int i = 1; i <= n; i++) {
			visit = new boolean[n + 1];
			BFS(i);
		}
		int max = 0;
		for(int i = 1; i <= n; i++) {
			max = Math.max(max, answer[i]);
		}
		for(int i = 1; i <= n; i++) {
			if(answer[i] == max) {
				System.out.print(i + " ");
			}
		}
 	}
	private static void BFS(int i) {
		Queue<Integer> que = new LinkedList<>();
		que.add(i);
		visit[i] = true;
		while(!que.isEmpty()) {
			int now = que.poll();
			for(int b : list[now]) {
				if(visit[b] == false) {
					visit[b] = true;
					answer[b]++;
					que.add(b);
				}
			}
 		}
	}
}

잘못된 풀이

import java.io.*;
import java.util.*;
public class Main {
	static int n, m;
	static ArrayList<Integer>[] list;
	static int []answer;
	static boolean []visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[n + 1];
		answer = new int[n + 1];
		for(int i = 1; i <= n; i++) {
			list[i] = new ArrayList<>();
		}
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			list[x].add(y);
		}
		
		for(int i = 1; i <= n; i++) {
			visit = new boolean[n + 1];
			BFS(i);
		}
		int max = 0;
		for(int i = 1; i <= n; i++) {
			max = Math.max(max, answer[i]);
		}
		for(int i = 1; i <= n; i++) {
			if(answer[i] == max) {
				bw.write(i + " ");
			}
		}
		bw.flush();
		bw.close();
	}
	private static void BFS(int i) {
		Queue<Integer> que = new LinkedList<>();
		que.add(i);
		visit[i] = true;
		while(!que.isEmpty()) {
			int now = que.poll();
			for(int b : list[now]) {
				if(visit[b] == false) {
					answer[b]++;
					que.add(b);
				}
				
			}
		}
	}
}


문제점

이 문제에서 진짜 많이 해멧다 계속 시간 초과가 나는 것이었다. 정답이 된 코드와 잘못된 코드와 다른 게 없는데 계속 시간 초과가 났다. 문제를 모르겠다. 뒤에 정답 된 코드를 제출했더니 정답이 나왔다...

 

오늘의 회고

오늘은 그리디와 그래프 문제를 풀어봤습니다. 그래프 문제는 앞에서 배웠던 DFS, BFS를 활용해서 해결하는 문제였다. 앞에서 배웠지만 직접 구현하기에는 힘든 점이 있었습니다. 이번 주말 일요일에는 다른 공부 하지 않고 알고리즘만 복습하는 시간을 가지겠습니다. 알고리즘 공부를 시작한 지 얼마 안 되었기 때문에 지치지 않고 좌절하지 않고 풀어내는 힘을 길어내는 게 중요한 것 같습니다. 요행을 바라지 말고 정직하게 공부하자.

728x90
728x90

32번 동전 0


내가 떠올린 풀이 해설

동전 값이 큰 동전부터 탐색을 하면서 k와 작거나 같은 동전이 나올 때까지 탐색하고 count 값은 k / (동전 값)으로 추가해주고 k % 동전 값으로 k의 값을 바꿔준다. 끝으로 count를 출력한다.


정확한 풀이

import java.io.*;
import java.util.*;
public class Baek11047 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		int []arr = new int[n];
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		int div = 0;
		int cnt = 0;
		int max = 0;
		for(int i = n - 1; i >= 0; i--) {
			if(k >= arr[i]) {
				div = arr[i];
				cnt += k / div;
				k = k % div;
			}
		
		}
		System.out.println(cnt);
	}
}

33번 카드 정렬하기


내가 떠올린 풀이 해설

우선순위 큐를 활용해서 풀어야하는 문제이다. 2개의 값을 합해서 비교해야 한다. 문제의 조건대로 연산을 하면 (10+20) + (30 + 40)이다. 앞의 2개를 더한 값을 바로 사용하므로 더한 값을 큐에 계속 넣어줘야 한다. 그냥 큐를 사용하면 30은 맨 뒤로 들어가 곧바로 연산에 수행될 수 없다. 최소한의 비교를 하기 위해서는 낮은 값부터 먼저 더해야 하므로 오름차순으로 정렬된 상태에서 값을 더하기 위해 우선순위 큐를 사용해야 한다.


정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1715 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		for(int i = 0; i < n; i++) {
			int data = Integer.parseInt(br.readLine());
			pq.add(data);
		}
		int data1 = 0;
		int data2 = 0;
		int sum = 0;
		
		while(pq.size() != 1) {
			data1 = pq.remove();
			data2 = pq.remove();
			sum += data1 + data2;
			pq.add(data1 + data2);
		}
		System.out.println(sum);
	}
}

34번 수 묶기


내가 떠올린 풀이 해설

가능한 큰 수들 끼리 묶어야 결괏값이 커진다. 또한 음수끼리 곱하면 양수로 되는 성질을 고려해야 된다. 양수 우선순위 큐와 음수 우선순위 큐와 1의 개수 0의 개수를 카운트하는 변수를 만든다. 데이터를 4개 그룹에 분리해 저장 4개 그룹은 1보다 큰 양수, 1의 개수, 0의 개수, 음수이다. while문을 양수 우선순위 큐 크기가 2보다 작을 때까지 반복하는데 수 2개를 큐에서 뽑고 2 개수를 곱한 값을 결괏값에 더한다.

양수 우선순위 큐에 데이터가 남아있으면 이 데이터를 결과값에 더한다. 음수도 위의 양수와 같이 반복한다 만약 음수 우선순위 큐에 데이터가 남아 있고, 데이터 0이 1개도 없으면 이 데이터를 결과 값에 더한다. 마지막으로 숫자 1의 개수를 결괏값에 더함


정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1744 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> plusPq = new PriorityQueue<>(Collections.reverseOrder());
		PriorityQueue<Integer> minusPq = new PriorityQueue<>();
		
		int one = 0;
		int zero = 0;
		
		for(int i = 0; i < n; i++) {
			int data = Integer.parseInt(br.readLine());
			if(data > 1) {
				plusPq.add(data);
			}
			else if(data == 1) {
				one++;
			} 
			else if(data == 0) {
				zero++;
			}
			else {
				minusPq.add(data);
			}
		}
		int sum = 0;
		while(plusPq.size() > 1) {
			int first = plusPq.remove();
			int second = plusPq.remove();
			sum = sum + first * second;
		}
		if(!plusPq.isEmpty()) {
			sum = sum + plusPq.remove();				
		}
		while(minusPq.size() > 1) {
			int first = minusPq.remove();
			int second = minusPq.remove();
			sum = sum + first * second;
		}
		if(!minusPq.isEmpty()) {
			if(zero == 0) {
				sum = sum + minusPq.remove();				
			}
		}
		sum = sum + one;
		System.out.println(sum);
	}
}

35번 회의실 배정


내가 떠올린 풀이

예전에 풀었던 문제와 비슷한 문제여서 어렵지 않게 풀었다. 끝나는 시간으로 정렬을 하고 시작시간으로 정렬을 한다. 끝나는 시간을 기준으로 겹치지 않는 회의실을 선택한다. 


정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1931 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		ArrayList<Meet> list = new ArrayList<>();
		
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());	
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			list.add(new Meet(x, y));
		}
		int cnt = 0;
		Collections.sort(list);
		int et = 0;
		for(Meet b : list) {
			if(b.x > et) {
				cnt++;
				et = b.y;
			}
		}
		System.out.println(cnt);
	}
}
class Meet implements Comparable<Meet> {
	int x;
	int y;
	Meet(int x, int y) {
		this.x = x;
		this.y = y;
	}
	@Override
	public int compareTo(Meet o) {
		if(this.x == o.x) {
			return this.y - o.y;
		}
		return this.x - o.x;
	}
}

오늘의 회고

오늘은 그리디 알고리즘에 배워보는 시간이였습니다. 오늘 문제들도 쉽지 않은 문제들로 구성이 돼있어 힘들었습니다. 알고리즘을 풀면서 고민해도 답을 못 풀 경우에 답을 보고 다시 풀어야 되나 아니면 계속 고민해야 되나 라는 고민이 생기는데 계속 고민해 보는 것이 가장 좋은 방법이라고 생각하는데 저는 시간의 제약 때문에 답을 보고 다시 풀고 복습하고 공부하는 식으로 내 것으로 만들고 있습니다. 아직 풀 수 있는 문제가 많진 않지만 계속해서 공부하겠습니다.

728x90

+ Recent posts