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

비기너

문제

문자열 내 p와 y의 개수

#문자열

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

프로그래머스

풀이

toLowerCase() 메서드를 이용해서 문자열의 문자를 소문자로 만든다.

문자열을 순차 탐색하며 p의 개수와 y의 개수를 센다.

p의 개수와 y의 개수를 비교하여 리턴한다.

참고

https://ward.tistory.com/191

자바 String 메서드 정리

코드

class Solution {
    boolean solution(String s) {
        int cntp = 0, cnty = 0;
        
        for (char c : s.toLowerCase().toCharArray()) {
            if (c == 'p')
                cntp++;
            if (c == 'y')
                cnty++;
        }
        
        return cntp == cnty;
    }
}

미들러

문제

1072번: 게임

# 이분탐색

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

풀이

최대 게임 수가 10억이므로 순차탐색을 통해 정답을 구하려 하면 시간초과가 발생한다.

1부터 10억 사이에서 승률이 바뀌는 게임 수을 이분탐색을 이용해서 찾는다.

승률을 구하는 과정에서 게임 수에 100을 곱하면 int의 범위를 벗어날 수 있으므로 long으로 계산해줘야 한다.

참고

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));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		int z = (int) (y * 100L / x);

		int s = 1, e = 1000000000, ans = -1;
		while (s <= e) {
			int m = (s + e) / 2;
			int tmp = (int) ((y + m) * 100L / (x + m));
			if (z < tmp) {
				ans = m;
				e = m - 1;
			} else
				s = m + 1;
		}

		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}

챌린저

문제

11403번: 경로 찾기

# dfs # 플로이드-워셜

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

풀이 1

각 정점마다 dfs를 진행하여 연결된 정점을 구한다.

dfs를 시작하는 정점을 시작할 때 방문 처리 하지 않고 다른 정점을 경유해서 왔을 때 방문 처리한다.

참고

https://ward.tistory.com/193

그래프 탐색

코드

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

public class Main {
	static int n;
	static int[][] adj;
	static int[] visited;

	static void dfs(int x) {
		for (int i = 0; i < n; i++) {
			if (visited[i] == 1 || adj[x][i] == 0)
				continue;
			visited[i] = 1;
			dfs(i);
		}
	}

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

		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++)
				adj[i][j] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < n; i++) {
			visited = new int[n];
			dfs(i);
			for (int j = 0; j < n; j++)
				bw.write(visited[j] + " ");
			bw.write("\n");
		}

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

풀이 2

그래프의 각 모든 정점에서의 다른 정점과의 연결성을 체크하는 문제이므로 플로이드-워셜 알고리즘을 응용하여 풀 수 있다.

참고

https://ward.tistory.com/198

플로이드-워셜

코드

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

public class Main {
	static int n;
	static int[][] adj;

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

		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++)
				adj[i][j] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					if (adj[j][i] == 1 && adj[i][k] == 1)
						adj[j][k] = 1;
				}
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				bw.write(adj[i][j] + " ");
			bw.write("\n");
		}
		bw.flush();
		bw.close();
	}
}