고민의 흔적

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를 활용해서 해결하는 문제였다. 앞에서 배웠지만 직접 구현하기에는 힘든 점이 있었습니다. 이번 주말 일요일에는 다른 공부 하지 않고 알고리즘만 복습하는 시간을 가지겠습니다. 알고리즘 공부를 시작한 지 얼마 안 되었기 때문에 지치지 않고 좌절하지 않고 풀어내는 힘을 길어내는 게 중요한 것 같습니다. 요행을 바라지 말고 정직하게 공부하자.