공부 기록

첨에 아무 생각 없이 mid*mid를 롱 타입으로 계산했는데 오버 플로우가 발생해서 BigInteger로 계산하도록 했다.

import java.math.BigInteger;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		long n = in.nextLong();
		long end = n;
		long start = 0;
		long answer = n;

		while (start <= end) {
			long mid = (start + end) / 2;
			BigInteger bigMid = BigInteger.valueOf(mid);

			if (bigMid.multiply(bigMid).compareTo(BigInteger.valueOf(n)) >= 0) {
				answer = Math.min(answer, mid);
				end = mid - 1;
			} else {
				start = mid + 1;
			}
		}

		System.out.println(answer);
	}
}

• java에서 자료형
  • Long - 64비트(-9223372036854775808 ~ 9223372036854775807)
  • BigInteger - 무한한 값

1~n 까지 합 n(n+1)/2 <= S 의 방정식을 풀면 된다.

이 방정식을 풀면 n^2+n-2S<=0 이고, 방정식의 해를 구하면 n이 (-1+√ (1+8s))/2 와 (-1-√ (1+8s))/2 사이에 있으면 되고, 그 중에 큰 값이므로 (-1+√ (1+8s))/2을 버림하여 구하면 된다. 풀이는 아래와 같다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		long s = in.nextLong();
		long n = (long) ((-1 + Math.sqrt(1 + 8 * s)) / 2);

		System.out.println(n);

	}
}

근데 문제 조건에 이분탐색으로 풀라는 이야기가 있었기 때문에.. 이분탐색으로 풀어보자면

n(n+1)/2를 s와 비교하여 아래와 같이 이분탐색으로 풀 수도 있다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		long s = in.nextLong();
		long end = s;
		long start = 0;
		long answer = 0;

		while (start <= end) {
			long mid = (start + end) / 2;
			long sum = sum(mid);

			if (sum <= s) {
				answer = Math.max(answer, mid);
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}

		System.out.println(answer);
	}

	private static long sum(long n) {
		return n * (n + 1) / 2;
	}
}

그룹화 하기 위해 sorted된 string을 key로 해서 map에 넣도록 했다.

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;
class Solution {
	public List<List<String>> groupAnagrams(String[] strs) {
		List<List<String>> answer = new ArrayList<>();

		HashMap<String, ArrayList<String>> map = new HashMap<>();
		for (String str : strs) {
			String key = Stream.of(str.split("")).sorted().collect(Collectors.joining());

			if (!map.containsKey(key)) {
				map.put(key, new ArrayList<String>());
			}
			map.get(key).add(str);
		}

		for (String key : map.keySet()) {
			answer.add(map.get(key));
		}

		return answer;
	}
}

single string을 정렬하는 방법으로는 스트림으로 정렬하는 방법도 있고,

char로 바꾼 다음에 Arrays.sort를 쓴 후 다시 스트링으로 합치는 방법이 있는데 테스트 해 보니 후자가 더 빠르다는 것을 알게 되었다.

import java.util.*;
class Solution {
	public List<List<String>> groupAnagrams(String[] strs) {
		List<List<String>> answer = new ArrayList<>();
		HashMap<String, ArrayList<String>> map = new HashMap<>();

		for (String str : strs) {
			char[] keys = str.toCharArray();
			Arrays.sort(keys);
			String key = new String(keys);

			if (!map.containsKey(key))
				map.put(key, new ArrayList<>());
			map.get(key).add(str);
		}

		for (String key : map.keySet()) {
			answer.add(map.get(key));
		}

		return answer;
	}
}

자리수가 가장 높은 알파벳에 순서대로 높은 값을 부여하면 되는 문제이다.

그렇지만 캐리 등이 있을 수 있다는 점을 염두해서 문제를 풀도록 해야한다.

이를 위해 예시 GCF + ACDEB의 경우

(100G+10C+1F)+(10000A+1000C+100D+10E+1B)로 변환하여

10000A+1010C+100D+100G+10E+1F+1B로 계산하고, 계수가 높은 순으로 높은 숫자를 부여해서 계산하도록 하면 된다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int alphabets[] = new int[26];

		for (int i = 0; i < n; i++) {
			String str = in.next();
			char ch[] = str.toCharArray();
			int index = 1;

			for (int j = ch.length - 1; j >= 0; j--) {
				alphabets[ch[j] - 'A'] += index;
				index *= 10;
			}
		}

		PriorityQueue<Alphabet> queue = new PriorityQueue<Alphabet>();
		for (int i = 0; i < alphabets.length; i++) {
			queue.add(new Alphabet(i, alphabets[i]));
		}

		int index = 9;
		int sum = 0;
		while (!queue.isEmpty()) {
			Alphabet alphabet = queue.poll();
			sum += alphabet.value * index;
			index--;
		}

		System.out.println(sum);
	}
}

class Alphabet implements Comparable {
	int index;
	int value;

	public Alphabet(int index, int value) {
		this.index = index;
		this.value = value;
	}

	@Override
	public int compareTo(Object o) {
		Alphabet alphabet = (Alphabet) o;
		return -Integer.compare(this.value, alphabet.value);
	}
}

치즈는 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉하면 녹는다.

이 때, dfs를 돌며 바로바로 치즈를 녹이는 식으로 문제를 풀면 안되고, 미리 어떤 치즈가 녹을지 체크를 한 뒤 해당 체크 부분만 녹이도록 해야 한다.

풀이는 아래와 같다.

import java.util.*;

public class Main {
	public static int[] dr = { 0, 0, 1, -1 };
	public static int[] dc = { 1, -1, 0, 0 };

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int mat[][] = new int[n][m];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				mat[i][j] = in.nextInt();
			}
		}

		int time = 0;
		while (true) {
			boolean isVisited[][] = new boolean[n][m];
			boolean isMelted = false;

			dfs(0, 0, n, m, mat, isVisited);
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (mat[i][j] == 1 && meltCheese(i, j, n, m, mat)) {
						isMelted = true;
					}
				}
			}

			if (!isMelted) {
				break;
			}
			time++;
		}
		System.out.println(time);
	}

	private static void dfs(int r, int c, int n, int m, int[][] mat, boolean[][] isVisited) {
		mat[r][c] = -1;
		isVisited[r][c] = true;
		for (int i = 0; i < 4; i++) {
			int row = r + dr[i];
			int col = c + dc[i];
			if (isBoundary(row, col, n, m) && mat[row][col] != 1 && !isVisited[row][col]) {
				dfs(row, col, n, m, mat, isVisited);
			}
		}
	}

	private static boolean meltCheese(int r, int c, int n, int m, int mat[][]) {
		int airs = 0;
		for (int i = 0; i < 4; i++) {
			int row = r + dr[i];
			int col = c + dc[i];
			if (isBoundary(row, col, n, m) && mat[row][col] == -1) {
				airs++;
			}
		}
		if (airs >= 2) {
			mat[r][c] = 0;
			return true;
		}
		return false;

	}

	private static boolean isBoundary(int row, int col, int maxRow, int maxCol) {
		if (row < 0 || col < 0) {
			return false;
		}
		if (row >= maxRow) {
			return false;
		}
		if (col >= maxCol) {
			return false;
		}
		return true;
	}
}

문제 조건

• k[encoded_string] => encoded_string을 k번 반복
• 3a 또는 2[4] 등의 경우는 없다고 생각한다

먼저, 괄호 중 ']' 을 만나는 순간, 뒤에서부터 가장 먼저 만나게 되는 '[' 의 위치를 찾아 그 부분을 반복하는 문제이다.

=> 뒤에서 부터 꺼내는 것이니까 스택을 사용하자

예를 들어 예시2와 같이 `3[a2[c]]` 가 주어졌다고 해 보자

아래와 같이 일단 닫는 괄호를 만나기 전까지는 스택에 push를 한다.

그 다음 여는 괄호를 만나기 전까지 pop을 하며 stringbuilder에 더해주고,

여는 괄호까지 pop한 뒤에 top이 숫자가 될 수 있는지 확인한다. 숫자이면 pop해주고, stringbuilder를 그 숫자만큼 반복해준다.

결과를 스택에 다시 넣어주고 위 규칙을 반복한다.

한가지 더 문제를 풀면서 주의할 점은 예시 4번과 같이 `abc3[cd]xyz`로 들어오게 되면 숫자와 문자의 분리가 필요하고,

스택에는 문자열로 집어넣기 때문에 문자열을 숫자로 바꿀 수 있는지 확인이 필요하다. 이는 아래와 같은 방법으로 해결했다.

class Solution {
	public String decodeString(String s) {
		Pattern p = Pattern.compile("(\\D)+|(\\d)+"); // 숫자와 숫자가 아닌것에 대한 분리
		Matcher m = p.matcher(s);
		
		while(m.find()) {
			System.out.println(m.group());
		}
	}

	private int isNumber(String str) { // 숫자인지 확인
		try {
			int n = Integer.parseInt(str);
			return n; // 맞다면 정수 리턴
		} catch (Exception e) {
			return -1; // 아니라면 -1 리턴
		}
	}
}

이를 코드로 옮겨보면 아래와 같다.

import java.util.*;
import java.util.regex.*;

class Solution {
	public String decodeString(String s) {
		Stack<String> stack = new Stack<String>();
		Queue<String> queue = new LinkedList<String>();

		Pattern p = Pattern.compile("(\\D)+|(\\d)+");
		Matcher m = p.matcher(s);

		while (m.find()) {
			StringTokenizer st = new StringTokenizer(m.group(), "[]", true);
			while (st.hasMoreElements()) {
				queue.add(st.nextToken());
			}
		}
		
		StringBuilder sb = new StringBuilder("");
		while (!queue.isEmpty()) {
			String str = queue.poll();

			if (str.equals("]")) {
				while (true) {
					String buffer = stack.pop();

					if (buffer.equals("[")) {
						break;
					}
					sb.insert(0, buffer);
				}

				if (!stack.isEmpty()) {
					int k = isNumber(stack.peek());
					if (k != -1) {
						stack.pop();
						for (int i = 0; i < k; i++) {
							stack.add(sb.toString());
						}
					}
				}
				
				sb.setLength(0);
			} else {
				stack.add(str);
			}
		}
		
		while(!stack.isEmpty()) {
			sb.insert(0, stack.pop());
		}
		return sb.toString();
	}

	private int isNumber(String str) {
		try {
			int n = Integer.parseInt(str);
			return n;
		} catch (Exception e) {
			return -1;
		}
	}
}

1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다.

문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다.

문제 조건

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

이 문제는 순서가 있다. 기본적으로 위상정렬을 이용 + 크기순으로 순회하면 될 것이라고 생각했다.

크기순으로 순회하기 위해서 PriorityQueue를 사용하도록 했다. 풀이는 아래와 같다.

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int v = in.nextInt();
		int e = in.nextInt();

		LinkedList<Integer> childs[] = new LinkedList[v + 1];
		LinkedList<Integer> parents[] = new LinkedList[v + 1];
		for (int i = 1; i <= v; i++) {
			childs[i] = new LinkedList<Integer>();
			parents[i] = new LinkedList<Integer>();
		}

		int[] parentNum = new int[v + 1];

		for (int i = 0; i < e; i++) {
			int parentNode = in.nextInt();
			int childNode = in.nextInt();

			childs[parentNode].add(childNode);
			parents[childNode].add(parentNode);
			parentNum[childNode]++;
		}

		traverseProblems(parentNum, childs, parents);
	}

	public static void traverseProblems(int[] parentNum, LinkedList<Integer> childs[], LinkedList<Integer> parents[]) {
		int problemNum = parentNum.length;
		boolean[] isVisited = new boolean[problemNum];

		PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
		for (int i = 1; i < problemNum; i++) {
			if (parentNum[i] == 0) {
				queue.add(i);
			}
		}

		while (!queue.isEmpty()) {
			int now = queue.poll();
			isVisited[now] = true;
			System.out.print(now + " ");

			for (int node : childs[now]) {
				parentNum[node]--;

				if (!isVisited[node] && parentNum[node] == 0) {
					queue.add(node);
				}
			}
		}
	}
}

문제 조건

• cpu에 태스크가 들어올건데 태스크의 순서는 맘대로 실행할 수 있다.
• 각 태스크는 한 시간 단위로 수행되고, 태스크를 실행하거나 idle 상태에 있을 수 있다.
• 두 개의 동일한 태스크를 실행하기 위한 사이에는 최소 n개의 태스크/idle이 있어야 한다.

흠... 일단은 그냥 가장 자주 나오는 글자를 배치하고 그 사이에 n개의 빈 칸을 둔 뒤에 다른 애들을 적절히 배치하면 될 것 같다고 생각했다.

class Solution {
	public int leastInterval(char[] tasks, int n) {
		int[] frequency = new int[26];
		for (int task : tasks) {
			frequency[task - 'A']++;
		}

		Arrays.sort(frequency);

		int maxFrequency = frequency[25];
		int betweenTime = (maxFrequency - 1) * n;

		int index = frequency.length - 2;
		while (index >= 0 && betweenTime > 0) {
			betweenTime -= Math.min(maxFrequency - 1, frequency[index]);
			index--;
		}
		betweenTime = Math.max(0, betweenTime);

		return betweenTime + tasks.length;
	}
}