99클럽 코테 스터디 2일차 TIL

비기너

문제

크기가 작은 부분문자열

# 문자열

https://school.programmers.co.kr/learn/courses/30/lessons/147355

프로그래머스

풀이

substirng() 메서드를 이용해서 t에서 길이가 p와 같은 부분 문자열을 모두 구한 후 p와 해당 문자열을 숫자로 변환 후 비교하여 부분 문자열의 크기가 p보다 작거나 같은 것의 개수를 세면 된다.

p의 길이가 최대 18이므로 숫자로 변환하려면 long을 사용해야 한다.

참고

https://ward.tistory.com/191

자바 String 메서드 정리

코드

class Solution {
    public int solution(String t, String p) {
        int cnt = 0;
        for (int i = 0; i < t.length(); i++) {
            if (i + p.length() > t.length())
                break;
            long pl = Long.parseLong(p);
            long tmp = Long.parseLong(t.substring(i, i + p.length()));
            if (pl >= tmp)
                cnt++;
        }
        return cnt;
    }
}

미들러

문제

11561번 징검다리

# 이분탐색

https://www.acmicpc.net/problem/11561

풀이

처음엔 DP 문제가 아닐까 생각했지만 입력의 최댓값이 10^16이므로 다른 방법을 찾기로 했다.

점프할 때마다 점프 거리가 1 이상 증가해야 하고 징검다리를 최대한 밟아야 하므로 1, 2, 3,.... 이런 식으로 점프거리가 1씩 증가하면 된다.

마지막 점프 거리가 k일 때 총 점프 거리는 등차수열의 합을 통해 계산할 수 있다.

총 점프 거리가 n보다 작거나 같은 k의 최댓값을 구하면 된다.

n이 최대 10^16이고 k의 최댓값이 약 10^9이라고 생각하면 순차 탐색을 통해서는 시간 초과가 될 것이므로 이분 탐색을 이용한다.

참고

https://ward.tistory.com/192

이분탐색

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int t = Integer.parseInt(br.readLine());

		while (t-- > 0) {
			long n = Long.parseLong(br.readLine());
			long s = 1, e = 1000000000, ans = 0;

			while (s <= e) {
				long m = (s + e) / 2;
				long tmp = m * (m + 1) / 2;
				if (tmp <= n) {
					ans = m;
					s = m + 1;
				} else
					e = m - 1;
			}

			bw.write(ans + "\n");
		}

		bw.flush();
		bw.close();
	}
}

챌린저

문제

1389번: 케빈 베이컨의 6단계 법칙

# bfs # 플로이드-워셜

https://www.acmicpc.net/problem/1389

풀이 1

인접리스트로 친구 관계 그래프를 저장한다.

각 노드에서 bfs를 돌리면 다른 노드까지의 최단거리를 구할 수 있고 최단 거리의 합이 케빈 베이컨 수이다.

모든 노드의 케빈 베이컨 수를 구하고 그중 최솟값을 구한다.

모든 노드를 순회하며 최솟값과 동일한 케빈 베이컨 수를 가지는 노드를 출력한다.

참고

https://ward.tistory.com/193

그래프 탐색

코드

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

public class Main {
	static int n;
	static int[] visited;
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

	static void bfs(int x) {
		Queue<Integer> q = new LinkedList<>();
		q.add(x);
		visited[x] = 1;
		while (!q.isEmpty()) {
			x = q.poll();
			for (int nx : adj.get(x)) {
				if (visited[nx] >= 1)
					continue;
				visited[nx] = visited[x] + 1;
				q.add(nx);
			}
		}
	}

	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());
		int m = Integer.parseInt(st.nextToken());
		for (int i = 0; i <= n; i++)
			adj.add(new ArrayList<>());

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adj.get(a).add(b);
			adj.get(b).add(a);
		}

		int[] c = new int[n + 1];
		int mn = 1000000000;
		for (int i = 1; i <= n; i++) {
			visited = new int[n + 1];
			bfs(i);
			int sum = 0;
			for (int j = 1; j <= n; j++)
				sum += visited[j];
			c[i] = sum - n;
			mn = Math.min(c[i], mn);
		}

		for (int i = 1; i <= n; i++) {
			if (c[i] == mn) {
				bw.write(i + "");
				break;
			}
		}

		bw.flush();
		bw.close();
	}
}

풀이 2

모든 친구들 사이의 거리를 구해야하므로 플로이드-워셜 알고리즘을 이용한다.

참고

https://ward.tistory.com/198

플로이드-워셜

코드

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

public class Main {
	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());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int d[][] = new int[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(d[i], 1000000000);
			d[i][i] = 0;
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			d[a][b] = 1;
			d[b][a] = 1;
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				for (int k = 1; k <= n; k++)
					d[j][k] = Math.min(d[j][k], d[j][i] + d[i][k]);
			}
		}

		int mn = 1000000000;
		int[] ans = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++)
				ans[i] += d[i][j];
			mn = Math.min(mn, ans[i]);
		}

		for (int i = 1; i <= n; i++) {
			if (ans[i] == mn) {
				bw.write(i + "");
				break;
			}
		}

		bw.flush();
		bw.close();
	}
}