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

비기너

문제

2500. Delete Greatest Value in Each Row

# 정렬

https://leetcode.com/problems/delete-greatest-value-in-each-row/

풀이

m * n 행렬에서 각 행의 최댓값을 제거하는 시행을 반복할 때 각 시행마다 제거되는 수의 최댓값의 합을 구하는 문제이다.

2차원 배열에서 각 행을 오름차순으로 정렬한다.

배열의 각 열에서 최댓값을 더해주면 된다.

코드

import java.util.*;

class Solution {
    public int deleteGreatestValue(int[][] grid) {
        for (int i = 0; i < grid.length; i++)
            Arrays.sort(grid[i]);
        
        int ans = 0;
        for (int i = 0; i < grid[0].length; i++) {
            int mx = 0;
            for (int j = 0; j < grid.length; j++)
                mx = Math.max(mx, grid[j][i]);
            ans += mx;
        }
    
        return ans;
    }
}

미들러

문제

소수 찾기

# 완전탐색

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

프로그래머스

풀이

주어진 종이 조각으로 만들 수 있는 수 중에 소수의 개수를 구하는 문제이다.

우선 에라토스테네스의 체 알고리즘을 이용하여 소수의 배열을 만든다.

이후 완전탐색을 통해 종이조각으로 만들 수 있는 모든 수에 대하여 소수인지 확인하여 개수를 센다.

코드

class Solution {
    int ans = 0;
    boolean[] p = new boolean[10000000];
    boolean[] visited = new boolean[10000000];
    boolean[] used;
    
    public void go(String s, String numbers) {
        if (!s.equals("")) {
            int tmp = Integer.parseInt(s);
            if (!p[tmp] && !visited[tmp] && tmp != 0) {
                ans++;
                visited[tmp] = true;
            }
        }
        
        for (int i = 0; i < numbers.length(); i++) {
            if (!used[i]) {
                used[i] = true;
                go(s + numbers.charAt(i), numbers);
                used[i] = false;
            }
        }
    }
    
    public int solution(String numbers) {
        used = new boolean[numbers.length()];
        p[1] = true;
        
        for (int i = 2; i < 10000000; i++) {
            if (!p[i]) {
                for (int j = i * 2; j < 10000000; j += i)
                    p[j] = true;
            }
        }
        
        go("", numbers);
        return ans;
    }
}

챌린저

문제

15686번: 치킨 배달

#완전탐색

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

풀이

도시에 있는 치킨집 중에 m개를 고를 때 도시의 치킨 거리의 최솟값을 구하는 문제이다.

치킨집이 최대 13개이므로 치킨집을 m개 고르는 모든 경우에 대해 치킨 거리를 계산해서 최솟값을 구해주면 된다.

코드

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

class Node {
	int y, x;

	public Node(int y, int x) {
		this.y = y;
		this.x = x;
	}
}

public class Main {
	static int n, m, ans = 1000000000;
	static int[][] a;
	static ArrayList<Node> c = new ArrayList<>();
	static ArrayList<Node> h = new ArrayList<>();

	static void go(int idx, ArrayList<Node> al) {
		if (al.size() == m) {
			int sum = 0;
			for (Node i : h) {
				int cd = 1000000000;
				for (Node j : al) {
					int d = Math.abs(i.y - j.y) + Math.abs(i.x - j.x);
					cd = Math.min(cd, d);
				}
				sum += cd;
			}

			ans = Math.min(ans, sum);

			return;
		}

		for (int i = idx; i < c.size(); i++) {
			al.add(c.get(i));
			go(i + 1, al);
			al.remove(al.size() - 1);
		}
	}

	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());
		a = new int[n][n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				a[i][j] = Integer.parseInt(st.nextToken());
				if (a[i][j] == 1)
					h.add(new Node(i, j));
				else if (a[i][j] == 2)
					c.add(new Node(i, j));
			}
		}

		go(0, new ArrayList<>());

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