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

비기너

문제

문자열 나누기

# 문자열

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

프로그래머스

풀이

문자열을 순차 탐색하면서 문자의 개수를 세서 나눠진 문자열의 수를 구하는 단순한 문제이다.

cntx를 통해 문자 x의 수를 세고 cntnx를 통해 x가 아닌 문자의 수를 센다.

cntx와 cntnx가 같아지면 문자열이 나눠진 것이므로 반환값을 1 증가시킨다.

문자열의 순회가 끝났는데 cntx나 cntnx가 0이 아니라면 문자를 세던 상태에서 끝난 것이므로 역시 반환값을 1 증가시킨다.

코드

class Solution {
    public int solution(String s) {
        int ans = 0;
        int cntx = 0, cntnx = 0;
        char x = '0';
        for (int i = 0; i < s.length(); i++) {
            if (x == '0')
                x = s.charAt(i);
            if (s.charAt(i) == x) 
                cntx++;
            else 
                cntnx++;
            if (cntx == cntnx) {
                ans++;
                cntx = 0;
                cntnx = 0;
                x = '0';
            }
        }
        if (cntx != 0 || cntnx != 0)
            ans++;
        return ans;        
    }
}

미들러

문제

입국심사

# 이분탐색

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

프로그래머스

 

풀이

우선 문제의 조건에 따라 정답의 최댓값을 구해보면 심사를 기다리는 사람이 10억 명이고 삼사관이 1명이고 심사 시간이 10억 분이라면 최대 10^18분이 정답이 된다.

즉 문제는 1분에서 10^18분 사이에서 n명을 모두 처리할 수 있는 시간의 최솟값을 찾는 것이다.

범위가 넓으므로 이분 탐색을 이용해서 정답을 구한다.

총 심사 시간을 x분이라고 하면 처리할 수 있는 사람의 수는 각 심사관의 심사시간으로 x를 나눈 몫을 더한 값이 된다.

처리할 수 있는 사람의 수와 n을 기준으로 이분 탐색을 진행한다.

최댓값이 10^18이므로 당연히도 long을 사용해야 한다.

코드

class Solution {
    public long solution(int n, int[] times) {
        long ans = 0;
        long s = 1, e = (long)1e18;
        while (s <= e) {
            long m = (s + e) / 2;
            long cnt = 0;
            for (int i : times)
                cnt += m / i;
            if (cnt >= n) {
                ans = m;
                e = m - 1;
            }
            else
                s = m + 1;
        }
        return ans;
    }
}

챌린저

문제

2660번: 회장뽑기

# bfs

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

풀이

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

점수의 계산은 친구들 사이의 거리의 최댓값이다.

따라서 각 회원마다 bfs를 통해 최단거리를 구하고 그중 최댓값이 해당 회원의 점수이다.

회원의 점수를 모두 구해서 최소인 사람이 회장 후보가 된다.

회원의 수가 최대 50이므로 회원 점수는 최대 50이다. (최솟값을 구할 때 넉넉잡아 초깃값을 100으로 설정한다.)

코드

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));
		n = Integer.parseInt(br.readLine());

		for (int i = 0; i <= n; i++)
			adj.add(new ArrayList<>());

		while (true) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if (a == -1 && b == -1)
				break;
			adj.get(a).add(b);
			adj.get(b).add(a);
		}

		int[] d = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			visited = new int[n + 1];
			bfs(i);
			for (int j = 1; j <= n; j++)
				d[i] = Math.max(d[i], visited[j] - 1);
		}

		int mn = 100;
		int cnt = 0;
		for (int i = 1; i <= n; i++)
			mn = Math.min(mn, d[i]);
		for (int i = 1; i <= n; i++) {
			if (mn == d[i])
				cnt++;
		}
		System.out.print(mn + " " + cnt + "\n");
		for (int i = 1; i <= n; i++) {
			if (mn == d[i])
				System.out.print(i + " ");
		}
	}
}