1. 모든 wires의 왼쪽 노드와 오른쪽 노드를 끊어가며 재귀를 통해 연결된 모든 노드의 개수를 계산해줍니다.
2. 왼쪽 노드와 오른쪽 노드의 차이의 절대값 중 가장 작은 값을 answer에 저장합니다.
코드
import java.util.*;
class Solution {
static ArrayList[] array;
static boolean[] check;
public int solution(int n, int[][] wires) {
int answer = Integer.MAX_VALUE;
array = new ArrayList[n+1];
for(int i = 1 ; i <= n ; i++){
array[i] = new ArrayList<Integer>();
}
for(int i = 0 ; i < wires.length; i++) {
array[wires[i][0]].add(wires[i][1]);
array[wires[i][1]].add(wires[i][0]);
}
for(int i = 0 ; i < wires.length; i++) {
check = new boolean[n+1];
check[wires[i][0]] = true;
check[wires[i][1]] = true;
int a = bfs(wires[i][0]);
int b = bfs(wires[i][1]);
answer = Math.min(answer, Math.abs(a-b));
}
return answer;
}
private static int bfs(int index) {
int sum = 1;
check[index] = true;
for(int i = 0 ; i < array[index].size(); i++){
if(check[(int)array[index].get(i)]) continue;
sum += bfs((int)array[index].get(i));
}
return sum;
}
}
dp[index][0]는 얼리 아답터가 아니기 때문에 모든 주변 사람은 얼리 아답터여야 한다. 따라서 dp[nextIndex][1]를 더해준다. dp[index][1]는 얼리 아답터 이기 때문에 두변 사람은 얼리 아답터 or 얼리 아답터가 아니여도 된다. 따라서 dp[nextIndex][0]와 dp[nextIndex][1] 중에 더 작은 값을 더 해준다.
코드
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
public class Main {
static int N, answer;
static ArrayList<Integer>[] array;
static int[][] dp;
static boolean[] check;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(answer);
}
private static void SetData()throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
array = new ArrayList[N+1];
check = new boolean[N+1];
dp = new int[N+1][2];
for(int i = 1; i <= N; i++)
array[i] = new ArrayList<>();
for(int i = 1; i < N; i++) {
int a = in.nextInt();
int b = in.nextInt();
array[a].add(b);
array[b].add(a);
}
dfs(1);
answer = Math.min(dp[1][0], dp[1][1]);
}
private static void dfs(int index) {
check[index] = true;
dp[index][0] = 0;
dp[index][1] = 1;
for(int i = 0 ; i < array[index].size(); i++) {
int nextIndex = array[index].get(i);
if(check[nextIndex]) continue;
dfs(nextIndex);
dp[index][0] += dp[nextIndex][1];
dp[index][1] += Math.min(dp[nextIndex][0], dp[nextIndex][1]);
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
==>> dequeue에 최적화된 문제라고 생각했습니다. 이유는 dequeue의 경우 앞과 뒤 둘다 넣고 뺄 수 있기 때문입니다.
풀이 방식은 다음과 같습니다.
'D'의 명령이 있을 시 boolean변수를 통해 'R'의 명령이 들어올 시 앞을 빼야하는지 뒤를 빼야하는지 체크해줍니다.
'R'의 명령이 있을 시 체크한 boolean 변수를 통해 앞 or 뒤를 빼줍니다.
명령이 다 끝날시엔 체크한 boolean변수를 통해 앞에서부터 빼야하는지 뒤부터 빼야하는지 체크해 준 뒤 올바르게 빼주면서 출력합니다.
코드
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
public class Main {
static StringBuilder sb;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(sb);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
sb = new StringBuilder();
int testcase = in.nextInt();
while(testcase-- > 0) {
char[] c = in.nextLine().toCharArray();
int n = in.nextInt();
String arrStr = in.nextLine();
Deque<Integer> deque = new LinkedList<>();
for (String s : arrStr.substring(1, arrStr.length() - 1).split(","))
if (!s.equals(""))
deque.add(Integer.parseInt(s));
sb.append(AC(deque, c)).append("\n");
}
}
static String AC(Deque<Integer> deque, char[] c) {
boolean reverse = false;
for (char command : c) {
if (command == 'R')
reverse = !reverse;
else {
if (deque.size() == 0)
return "error";
if (reverse)
deque.removeLast();
else
deque.removeFirst();
}
}
StringBuilder sb = new StringBuilder("[");
while (!deque.isEmpty()) {
sb.append(reverse ? deque.removeLast() : deque.removeFirst());
if (deque.size() != 0)
sb.append(',');
}
sb.append(']');
return sb.toString();
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
처음엔 투포인터로 풀다가 cat, tree, catrtee의 경우 잘 해결되지 않는 점을 확인했습니다.
catrtee의 경우 첫번 째 t를 어디서 뽑아와야되는지 알 수 없습니다. 첫번째 단어 ca 뒤에 있는 t를 써도 되고, tree의 첫글자 t를 써도 됩니다. 따라서, 두 경우 다 확인해봐야 하니 BFS가 필요합니다.
코드
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
public class Main {
static StringBuilder sb;
static boolean[][] check;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(sb);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
sb = new StringBuilder();
int testcase = in.nextInt();
for(int i = 1 ; i <= testcase; i++) {
sb.append("Data set "+i+": ");
String[] temp = in.nextLine().split(" ");
check = new boolean[temp[1].length()+1][temp[2].length()+1];
boolean check = CanMakeString(temp[0], temp[1], temp[2]);
if(check)
sb.append("yes").append("\n");
else
sb.append("no").append("\n");
}
}
private static boolean CanMakeString(String first, String second, String third) {
Queue<int []> queue = new LinkedList<>();
queue.add(new int[] {0, 0});
check[0][0] = true;
while (!queue.isEmpty()) {
int[] index = queue.poll();
if (index[0] + index[1] == third.length()) {
return true;
}
if (index[0] < first.length()
&& first.charAt(index[0]) == third.charAt(index[0] + index[1])
&& !check[index[0] + 1][index[1]]) {
queue.add(new int[]{ index[0] + 1, index[1] });
check[index[0] + 1][index[1]] = true;
}
if (index[1] < second.length()
&& second.charAt(index[1]) == third.charAt(index[0] + index[1])
&& !check[index[0]][index[1] + 1]) {
queue.add(new int[]{ index[0],index[1] + 1 });
check[index[0]][index[1] + 1] = true;
}
}
return false;
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
3. 문자열이 있다면 right를 mid -1로 초기화 시키며 더 위의 열을 확인해줍니다.
4. 문자열이 없다면 left를 mid+1로 초기화 시키며 더 아래의 열을 확인해줍니다.
5. 2~4의 작업을 반복합니다.
위의 설명대로 구현하였으며, 같은 문자열이 있는지 check해줄 때의 데이터는 순서가 상관없으므로 더 빠른 HashSet을 이용했습니다.
코드
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
public class Main {
static int R, C, answer;
static char[][] array;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(answer);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
R = in.nextInt();
C = in.nextInt();
array = new char[R][C];
for (int i = 0; i < R; i++) {
String s = in.nextLine();
for (int j = 0; j < C; j++) {
array[i][j] = s.charAt(j);
}
}
binarySearch(1, R - 1, R - 1);
}
private static boolean check(int start, int end) {
Set<String> s = new HashSet<>();
for (int j = 0; j < C; j++) {
String temp = "";
for (int i = start; i <= end; i++)
temp += array[i][j];
if (!s.contains(temp))
s.add(temp);
else
return false;
}
return true;
}
private static void binarySearch(int left, int right, int end) {
while (left <= right) {
int mid = (left + right) / 2;
boolean flag = check(mid, end);
if (flag) {
if (answer < mid)
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
더 빠르고 메모리 적게 잡아먹는 다른 사람 코드
아래의 코드는 arrayList에 이미 모든 열로 이어진 행의 개수를 다 넣은 뒤 subString으로 더 빠르게 확인해 준 방법이다.
방법은 같지만 반복해서 Set에 데이터를 추가해주는 저의 코드에 비해 반복없이 1번만 작업해줌으로서 훨씬 시간을 단축해준 코드입니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int R = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
char[][] arr = new char[R][C];
for (int i = 0; i < R; i++) {
arr[i] = br.readLine().toCharArray();
}
ArrayList<String> list = new ArrayList<>();
StringBuilder sb = new StringBuilder("");
for (int i = 0; i < C; i++) {
sb.setLength(0);
for (int j = 0; j < R; j++) {
sb.append(arr[j][i]);
}
list.add(sb.toString());
}
int count = 0, start = 0, end = R;
ArrayList<String> tempList = new ArrayList<>();
while (start <= end) {
tempList.clear();
int mid = (start + end) / 2;
for (int i = 0; i < list.size(); i++) {
String temp = list.get(i);
temp = temp.substring(mid, temp.length());
if (!tempList.contains(temp)) {
tempList.add(temp);
} else {
break;
}
}
if (tempList.size() != list.size()) {
end = mid - 1;
} else {
start = mid + 1;
count = mid;
}
}
System.out.print(count);
}
}
TreeMap의 장점 중 하나는 자동으로 key값에 의해 자동 정렬 된다는 것입니다. (우선순위 큐와 비슷한 느낌)
저 같은 경우 Node라는 class를 만들어 현재 string과 자식 Treemap을 생성해 주었다.
맨 처음 연결시킬 string 입력이 올 시 now라는 Node를 만들어 준 뒤 root의 위치를 할당합니다. 그 후 입력된 String이 자식 Treemap의 키값 중 해당 String으로 된 TreeMap이 없다면 새롭게 자식 TreeMap을 만들어 연결 시켜줍니다. 그 후, now를 자식 node를 가리키게 합니다. (해당 동작은 자식 노드를 게속 연결시켜주기 위함.)
연결이 모두 다 되었다면, root에 연결된 자식 TreeMap을 하나씩 꺼내서 자식을 타고가면서 출력해주면 됩니다.
저는 재귀 형식으로 구현했습니다.
코드
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
public class Main {
static StringBuilder sb;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(sb);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
int n = in.nextInt();
Trie trie = new Trie("");
Trie node;
sb = new StringBuilder();
while(n-- > 0) {
String[] temp = in.nextLine().split(" ");
int k = Integer.parseInt(temp[0]);
node = trie;
for(int j = 0 ; j < k ; j++) {
String name = temp[j+1];
if(!node.list.containsKey(name))
node.list.put(name, new Trie(name));
node = node.list.get(name);
}
}
print(trie, -1);
}
public static void print(Trie trie, int depth) {
if(depth != -1) {
for(int i = 0; i < depth; i++) {
sb.append("--");
}
sb.append(trie.name).append("\n");
}
for(Trie tree : trie.list.values()) {
print(tree, depth+1);
}
}
}
class Trie{
TreeMap<String, Trie> list;
String name;
Trie(String name) {
list = new TreeMap<>();
this.name = name;
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
