우유

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

기존에 BFS를 돌렸던 방식과 다르게 BFS를 돌릴 Queue 를 static 으로 선언해서

처음부터 익은 토마토가 있으면 순차적으로 Queue 에 넣어서 BFS를 돌리면 해결되는 문제였다.

또한, 전체 토마토가 익지 않은 경우를 생각하기 위해 BFS가 모두 돌았을 때 익지 않은 토마토 (0인 값)이 있으면

-1을 출력하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int M, N;
	static int map[][];
	static int dy[] = { 1, 0, -1, 0 };
	static int dx[] = { 0, 1, 0, -1 };
	static int cnt1 = 0, cnt2 = 0, day = 0;
	static Queue<int[]> qu = new LinkedList<int[]>();

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken()); // 가로
		N = Integer.parseInt(st.nextToken()); // 세로

		map = new int[N + 1][M + 1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());

				if (map[i][j] == 1)
					qu.add(new int[] { i, j });
				else if (map[i][j] == -1)
					cnt1++;
			}
		}

		BFS();

		Loop1: for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				day = Math.max(day, map[i][j]);

				if (map[i][j] == 0) {
					day = -1;
					break Loop1;
				}
			}
		}
		if (day != -1)
			System.out.println(day - 1);
		else
			System.out.println(day);
	}

	static void BFS() {

		while (!qu.isEmpty()) {
			int curY = qu.peek()[0];
			int curX = qu.peek()[1];

			qu.poll();

			for (int i = 0; i < 4; i++) {
				int ny = curY + dy[i];
				int nx = curX + dx[i];

				if (ny <= 0 || nx <= 0 || ny > N || nx > M)
					continue;

				if (map[ny][nx] != 0)
					continue;

				qu.add(new int[] { ny, nx });

				map[ny][nx] = map[curY][curX] + 1;

			}
		}

	}
}

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

간단한 DFS로 해결할수 있는 문제지만 ArrayList 와 Array 두가지 방법을 사용했을 때를 비교하고

두개 다 구현하는 방법을 연습하는 문제로 활용하였다.

Array로 구현한 DFS 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, M, V;
	static int map[][];
	static boolean visited[];
	static int cnt =0;

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());

		map = new int[N + 1][N + 1];
		visited = new boolean[N + 1];

		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			map[y][x] = 1;
			map[x][y] = 1;
		}

//		DFS(1);
//
//		Arrays.fill(visited, false);
//		System.out.println();
		
		BFS(1);
		System.out.println(cnt);
	}

	static void DFS(int i) {
		visited[i] = true;
		System.out.print(i + " ");

		for (int j = 1; j < N; j++) {

			if (map[i][j] == 1 && visited[j] == false) {
				visited[j] = true;
				DFS(j);
			}
		}
	}

	static void BFS(int i) {
		Queue<Integer> q = new LinkedList<Integer>();

		q.offer(i);
		visited[i] = true;

		while (!q.isEmpty()) {

			int temp = q.poll();
//			System.out.print(temp + " ");

			for (int j = 1; j <= N; j++) {

				if (map[temp][j] == 1 && visited[j] == false) {
					cnt ++;
					visited[j] = true;
					q.offer(j);
				}
			}
		}
	}
}

ArrayList 로 구현한 DFS 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

	static ArrayList<ArrayList<Integer>> al = new ArrayList<>();
	static int N, M;
	static boolean[] Visited;

	static int cnt =0;

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());

		Visited = new boolean[N + 1];

		Arrays.fill(Visited, false);
		for (int i = 0; i <= N; i++) {
			al.add(new ArrayList<Integer>());
		}

		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			al.get(x).add(y);
			al.get(y).add(x);
		}

		DFS(1);
		
		System.out.println(cnt-1);
	}

	static void DFS(int V) {
		Visited[V] = true;

		cnt ++;
		for (int i = 0; i < al.get(V).size(); i++) {
			int temp = al.get(V).get(i);

			if (!Visited[temp]) {
				DFS(temp);
			}
		}
	}
}

Map 의 기본 개념만 알면 풀수 있는 간단한 문제였다.

오름차순으로 sort_arr 정렬에 재 배치하고

각 정렬된 해당 값을 키값으로 저장한뒤 순서를 value 값으로 Map 에 저장하여

해당 key값에 저장된 value를 가져오는 방법

But,,,, StringBuilder를 쓰지 않을땐 시간초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] agrs) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] sort_arr = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			sort_arr[i] = arr[i];
		}

		Arrays.sort(sort_arr);

		int n = 0;
		for (int i = 0; i < N; i++) {
			if (!hm.containsKey(sort_arr[i])) {
				hm.put(sort_arr[i], n);
				n++;
			}
		}

		for (int i = 0; i < N; i++) {
			sb.append(hm.get(arr[i]) + " ");
		}
		
		System.out.println(sb);
	}
}

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

이전문제와 비슷한 문제

익명함수의 개념만 알면 어렵지 않은 문제였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] agrs) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		String[][] arr = new String[N][100];

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			arr[i][0] = st.nextToken();
			arr[i][1] = st.nextToken();
		}

		Arrays.sort(arr, new Comparator<String[]>() {

			@Override
			public int compare(String[] o1, String[] o2) {
				return Integer.parseInt(o1[0]) - Integer.parseInt(o2[0]);
			}

		});

		for (int i = 0; i < N; i++) {
			System.out.println(arr[i][0] + " " + arr[i][1]);
		}

	}

}

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

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

문제 로직은 굉장히 단순했지만

람다식에 대한 개념?이 기억이 잘안나서 오래 걸렸던 문제였다.

나중에 다시 공부해야겠다

참고 블로그

https://mangkyu.tistory.com/113

https://st-lab.tistory.com/243

https://mangkyu.tistory.com/113

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int N = Integer.parseInt(br.readLine());

		int[][] arr = new int[N][2];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());

			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr, (o1, o2) -> {
			if (o1[0] == o2[0]) {
				return o1[1] - o2[1];
			} else {
				return o1[0] - o2[0];
			}
		});

		for (int i = 0; i < N; i++) {
			System.out.println(arr[i][0] + " " + arr[i][1]);
		}

	}

}

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

단순한게 최고라는 생각에 일반적인 2진법으로 나누었을때랑 같은 방법으로 -2를 나누어보았다.

예를들어

-13 / -2 = 6.5 -> 올림 7 (나머지 1)

7 / -2 = -3.5 -> 올림 -3 (나머지 1)

-3 / -2 = 1.5 -> 올림 2 (나머지 1)

2 / -2 = -1 -> -1 (나머지 0)

-1 / -2 = 0.5 -> 1 (나머지 1)

1. 마지막 몫이 1일때까지 반복되야 함.

2. 나머지는 항상 양수

3. 음수에서 계산이 되기때문에 소수점에서 올림 (ceil)

4. 마지막 1일때 몫을 따로 append 해주고 순서를 reverse 해야한다. 

위와 같은 방법으로 코드를 구현하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();

		int N = Integer.parseInt(br.readLine());

		if (N == 0) {
			System.out.println(0);
		} else {
			while (N != 1) {

				sb.append(Math.abs(N % -2));
				N = (int) Math.ceil((double) N / (-2));

			}

			sb.append(N);

			sb.reverse();
			System.out.println(sb);
		}

	}
}

StringTokenizer 클래스란?

BufferedReader 클래스의 메서드로 입력을 읽어들이면, 라인 단위로 읽어들일 수밖에 없어요.

거기서 머 스페이스 기준으로 문자열을 분리한다던가 필요할때가 많겠죠?

BufferedReader 클래스가 아니더라도, 컴마로 구분되는 문자열들을 분리한다던가, 

특정 문자에 따라 문자열을 나누고 싶을 때에 StringTokenizer를 이용하실 수 있습니다. 

String : 문자열을

Tokenizer : 토큰화한다.

즉 토큰은 분리된 문자열 조각으로, 스트링토크나이저 클래스는 하나의 문자열을 여러 개의 토큰으로 분리하는 클래스인거죠.

StringTokenizer 생성자

StringTokenizer를 생성하는 방식에는 3가지가 있습니다.

StringTokenizer 메서드

앞에서 nextToken() 이용해 토큰값을 가져올 수 있다는 건 대충 알았어요.

이 외에 이 클래스에서 지원하는 메서드들은 뭐가 있을까요?

자주 사용하는 메서드는 hasMoreTokens, countTokens 그리고 nextToken 정도 되겠습니다.

StringTokenizer와 Split 차이?

둘 다 모두 문자열 파싱하는데 사용할 수 있습니다.

■ StringTokenizer는 java.util에 포함되어 있는 클래스, split는 String클래스에 속해있는 메소드이다.

■ StringTokenizer는 문자 또는 문자열로 문자열을 구분한다면, split는 정규표현식으로 구분합니다. 

■ StringTokenizer는 빈 문자열을 토큰으로 인식하지 않지만 split는 빈 문자열을 토큰으로 인식하는 차이가 있습니다.

■ Stringtokenizer는 결과값이 문자열이라면 split는 결과 값이 문자열 배열입니다. 따라서 StringTokenizer를 이용할 경우, 전체 토큰을 보고 싶다면 반복문을 이용해서 하나하나 뽑을 수 밖에 없어요.

■ 배열에 담아 반환하는 Split는 데이터를 바로바로 잘라서 반환해주는 StringTokenizer보다 성능이 약간 뒤쳐지겠죠? 그러나 데이터양이 많은 경우 거기서 거기기 때문에 크게 신경쓸 필요는 없습니다.

|  문자열을 다루를 대표적인 클래스 String, StringBuffer, StringBuilder 차이점

| String  vs  StringBuffer/StringBuilder

String str = "hello";   // String str = new String("hello");
str = str + " world";  // [ hello world ]

StringBuffer sb= new StringBuffer("hello");
sb.append(" world");

| StringBuffer  vs  StringBuilder

소수 구하는 방법처럼 제곱근까지만 for문을 돌렸다.

소인수분해로 나누어지는 정수는 2부터 시작이고 2가 제일 작은 숫자기때문에

주어진 숫자는 제곱근 숫자 이하의 인수 개수만 가지기 때문 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static int N;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		for (int i = 2; i <= Math.sqrt(N); i++) {
			while (N % i == 0) {
				System.out.println(i);
				N /= i;
			}
		}

		if (N != 1)
			System.out.println(N);
	}
}

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

소수 구하는 다른 방법인 에라토스테네스 방법도 공부해야 할듯

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

	static int N, M;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());

		ArrayList<Integer> al = new ArrayList<Integer>();
		int sum = 0;

		for (int i = N; i <= M; i++) {
			boolean flag = true;

			if(i == 1)
				continue;
			
			for (int j = 2; j <= Math.sqrt(i); j++) {

				if (i % j == 0) {
					flag = false;
					break;
				}
			}

			if (flag) {
				
				sum += i;
				al.add(i);
			}
		}
		
		Collections.sort(al);
		
		if(al.isEmpty()) {
			System.out.println("-1");
		}
		else {
			System.out.println(sum);
			System.out.println(al.remove(0));
		}

	}

}