티스토리 뷰
목차
1. 반복수열(2331)
👉 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int A, P;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
ArrayList<Integer> list = new ArrayList<Integer>();
A = Integer.parseInt(st.nextToken());
P = Integer.parseInt(st.nextToken());
list.add(A);
while(true) {
int tmp = list.get(list.size() - 1);
int num = 0;
while(tmp != 0) {
num += Math.pow(tmp % 10, P);
tmp /= 10;
}
if(!list.contains(num)) {
list.add(num);
}else {
System.out.println(list.indexOf(num));
break;
}
}
}
}- 두 자리수를 P만큼 곱해서 더하다가 중복된 수가 나오면 자리수 리턴
2. 알고스팟(1261)
👉 소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static int[] moveN = {0, 0, -1, 1};
static int[] moveM = {-1, 1, 0, 0};
static int N, M;
static int[][] arr;
static int[][] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
arr = new int[N][M];
visited = new int[N][M];
for(int i = 0; i < N; i++) {
String[] s = br.readLine().split("");
for(int j = 0; j < M; j++) {
arr[i][j] = Integer.parseInt(s[j]);
visited[i][j] = Integer.MAX_VALUE;
}
}
System.out.println(bfs(0, 0));
}
public static int bfs(int x, int y) {
PriorityQueue<Info> pq = new PriorityQueue<Info>();
pq.offer(new Info (x, y, 0));
visited[x][y] = 0;
while(!pq.isEmpty()) {
// int curN = pq.peek()[0];
// int curM = pq.peek()[1];
// int count = pq.peek()[2] - 0;
Info info = pq.poll();
for(int i = 0; i < 4; i++) {
int nextN = info.y + moveN[i];
int nextM = info.x + moveM[i];
int count = info.broken;
if(nextM < 0 || nextN < 0 || nextM >= M || nextN >= N) continue;
if(arr[nextN][nextM] == 1) {
count++;
}
if(visited[nextN][nextM] > count) {
visited[nextN][nextM] = count;
pq.offer(new Info (nextN, nextM, count));
}
}
}
return visited[N - 1][M - 1];
}
static class Info implements Comparable<Info>{
int y;
int x;
int broken;
public Info(int y, int x, int broken) {
this.y = y;
this.x = x;
this.broken = broken;
}
@Override
public int compareTo(Info I) {
return this.broken - I.broken;
}
}
}- 문제를 보자마자 bfs로 쉽게 풀 수 있다고 생각했는데 방과 벽의 차이를 비교했을 때 가중치를 생각하지 못했습니다. 1이면 벽이라 부수고 통과해야 하지만 0이라면 방이기 때문에 바로 통과가 가능하기 때문이지요. 방문 체크를 할 visited 변수를 모두 Integer 최대값으로 초기화하는 이유는 이 때문인데요 벽을 부순 후, 가중치 체크를 위함입니다. 벽을 만나면 벽을 부수고 부순 값을 객체에 저장하면서 가중치를 체크하여 N,M까지 도달하여 counting하는 문제였습니다.
하루하루 문제를 풀면서 털리는 느낌인데 재미는 있지만 한번씩 자괴감이 밀려오는 것을 막는게 주요할 거 같습니다.
결론은 화이팅,, ㅋ
3. 큐(10845) https://www.acmicpc.net/problem/10845
👉 소스코드
public class Main {
public static void main(String[] args) throws IOException {
Deque<Integer> q = new ArrayDeque<Integer>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(st.nextToken());
for(int i = 0; i < T; i++) {
String s = br.readLine();
if(s.contains("push")) q.offer(Integer.parseInt(s.substring(5)));
else if(s.equals("pop")) {
if(q.isEmpty()) sb.append(-1 + "\n");
else sb.append(q.poll() + "\n");
}else if(s.equals("size")) sb.append(q.size() + "\n");
else if(s.equals("empty")) {
if(q.isEmpty()) sb.append(1 + "\n");
else sb.append(0 + "\n");
}else if(s.equals("front")) {
if(q.isEmpty()) sb.append(-1 + "\n");
else sb.append(q.peekFirst() + "\n");
}else {
if(q.isEmpty()) sb.append(-1 + "\n");
else sb.append(q.peekLast() + "\n");
}
}
bw.write(sb.toString());
bw.flush();
br.close();
bw.close();
}
}- 간단한 Deque를 활용한 문제
3. 덱(10866)
👉 소스코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
Deque<Integer> q = new ArrayDeque<Integer>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(st.nextToken());
for(int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine());
String s = st.nextToken();
switch(s) {
case "push_front" :
q.offerFirst(Integer.parseInt(st.nextToken()));
break;
case "push_back" :
q.offerLast(Integer.parseInt(st.nextToken()));
break;
case "pop_front" :
if(q.isEmpty()) sb.append(-1).append("\n");
else sb.append(q.pollFirst()).append("\n");
break;
case "pop_back" :
if(q.isEmpty()) sb.append(-1).append("\n");
else sb.append(q.pollLast()).append("\n");
break;
case "size" :
sb.append(q.size()).append("\n");
break;
case "empty" :
if(q.isEmpty()) sb.append(1).append("\n");
else sb.append(0).append("\n");
break;
case "front" :
if(q.isEmpty()) sb.append(-1).append("\n");
else sb.append(q.peekFirst()).append("\n");
break;
case "back" :
if(q.isEmpty()) sb.append(-1).append("\n");
else sb.append(q.peekLast()).append("\n");
break;
}
}
bw.write(sb.toString());
bw.flush();
br.close();
bw.close();
}
}- 덱과 스위치문을 활용한 풀이방법
4. 수 찾기(1920)
👉 소스코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.StringTokenizer;
public class Main {
static int[] nArr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
nArr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
nArr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(nArr);
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for(int i = 0; i < M; i++) {
if(bSearch(Integer.parseInt(st.nextToken())) >= 0 ) bw.write(1 + "\n");
else bw.write(0 + "\n");
}
bw.flush();
}
public static int bSearch(int key) {
int start = 0;
int end = nArr.length - 1;
while(start <= end) {
int mid = (start + end) / 2;
// 찾을 수가 앞에 있다면
if(nArr[mid] > key) end = mid - 1;
// 찾을 수 가 뒤에 있다면
else if(nArr[mid] < key) start = mid + 1;
//찾는 수가 중간 값과 동일하다면
else return mid;
}
// 찾는 수가 없는 경우
return -1;
}
}- 시간초과가 나서 시간이 좀 걸렸는데 종료조건을 정확하게 생각하고 탐색을 시작해야 꼬이지 않을 것 같다.
5. 수열 정렬
👉 소스코드
public class Main1 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
Integer[] arr = new Integer[num];
Integer[] arrTmp = new Integer[num];
Integer[] res = new Integer[num];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < num; i++) {
int a = Integer.parseInt(st.nextToken());
arr[i] = a;
arrTmp[i] = a;
}
Arrays.sort(arrTmp);
for(int i = 0; i < num; i++) {
res[Arrays.asList(arr).indexOf(arrTmp[i])] = i;
arr[Arrays.asList(arr).indexOf(arrTmp[i])] = 0;
}
for(int i = 0; i < num; i++) {
System.out.print(res[i] + " ");
}
}
}- 비교적 쉬워 보이는 문제임에도 불구하고 문제에서 요구하는 부분을 정확하게 파악하지 못하여 시간을 잡아 먹었다.
주어진 순열에 대한 인덱스 값을 구해 새로운 배열에 저장하여 리턴하면 되는 문제
6. 보물
👉 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main1 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
int[] A = new int[num];
Integer[] B = new Integer[num];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < num; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i = 0; i < num; i++) {
B[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(A);
Arrays.sort(B, Collections.reverseOrder());
int result = 0;
for(int i = 0; i < num; i++) {
result += (A[i] * B[i]);
}
System.out.println(result);
}
}- A 배열을 오름차순, B배열을 내림차순으로 정렬한 후 곱셈하면 결과를 알 수 있는 문제
7. 기타줄
👉 소스코드
import java.util.*;
import java.io.*;
import java.math.BigInteger;
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 broken = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] pack = new int[m];
int[] piece = new int[m];
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
pack[i] = Integer.parseInt(st.nextToken());
piece[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(pack); Arrays.sort(piece);
int cheapestPack = pack[0];
int cheapestPiece = piece[0];
int result = 0;
while(broken > 0) {
int curBroken = broken >= 6 ? 6 : broken;
// 현재 시점에 사야하는 기타줄을 알고 있어야
// 낱개 기타줄과 팩 기타줄의 가격을 비교할 수 있다.
if(cheapestPack < cheapestPiece) {
result += cheapestPack;
broken -= curBroken;
} else {
if(cheapestPack > cheapestPiece * curBroken) {
result += (cheapestPiece * curBroken);
broken -= curBroken;
} else {
result += cheapestPack;
broken -= curBroken;
}
}
}
System.out.println(result);
}
}-세트 줄과 낱개 줄의 가격 중에서 가장 저렴한 가격을 구한다. 구한 저렴한 값이 세트 줄이라면 모든 N개의 줄을 구매하는데 필요한 최소비용은 세트 줄의 가격이다.
- 위 조건이 아니라면 세트 줄의 가격과 현재 구매해야 하는 N개의 줄을 사는데 필요한 낱개 줄 가격과 비교하며 구매하면 된다.
8. 숫자 정사각형
👉 소스코드
import java.util.*;
import java.io.*;
import java.math.BigInteger;
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 n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] map = new int[n][m];
int length = Math.min(n, m);
for(int i = 0; i < n; i++) {
String[] s = br.readLine().split("");
for(int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(s[j]);
}
}
while(length > 1) {
for(int i = 0; i <= n-length; i++) {
for(int j = 0; j <= m-length; j++) {
if(map[i][j] == map[i][j + length - 1] && map[i][j] == map[i + length - 1][j + length - 1] && map[i][j] == map[i + length - 1][j]) {
System.out.println(length * length);
return;
}
}
}
length--;
}
System.out.println(length * length);
}
}- n, m 두 수중 작은 수가 나올 수 있는 정사각형 최대 크기가 된다. 최대 크기를 length 라는 변수로 두면 즉, 세로는 n-length 가로는 m-length까지만 탐색하면 된다. 반복문을 돌리면서 가장 큰 정사각형 부터 탐색하다가 꼭지점 4개가 동일한 값이라면 반복문을 중단해도 된다.
9. 토너먼트
👉 소스코드
import java.util.*;
import java.io.*;
import java.math.BigInteger;
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 totalPlayer = Integer.parseInt(st.nextToken());
int jimin = Integer.parseInt(st.nextToken());
int hansoo = Integer.parseInt(st.nextToken());
int round = 0;
while(jimin != hansoo) {
round++;
if(jimin % 2 == 1) jimin++;
if(hansoo % 2 == 1) hansoo++;
jimin /= 2;
hansoo /= 2;
}
System.out.println(round);
}
}- 지민과 한수가 만날 때까지 반복
10. 문자열
👉 소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
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());
String a = st.nextToken();
String b = st.nextToken();
int cnt = 0;
int result = Integer.MAX_VALUE;
for(int i = 0; i < b.length() - a.length() + 1; i++) {
for(int j = 0; j < a.length(); j++) {
if(b.charAt(j + i) != a.charAt(j)) cnt++;
}
result = Math.min(result, cnt);
cnt = 0;
}
System.out.println(result);
}
}- 문제를 잘 읽어보면 결국에는 두 문자열을 비교했을 때 b문자열에 a문자열이 들어갈 수 있는 경우의 수를 모두 확인해 본 뒤 그 최소값을 출력하는 문제
11. 학생 번호
👉 소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.HashSet;
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 num = Integer.parseInt(st.nextToken());
BigInteger[] arr = new BigInteger[num];
for(int i = 0; i < num; i++) {
arr[i] = new BigInteger(br.readLine());
}
int count = 0; // k 값
int dic = 10; // k의 값을 구하는데 필요한 자릿수
HashSet<Integer> set = new HashSet<Integer>();
while(set.size() != arr.length) {
count++;
set.clear();
for(int i = 0; i < arr.length; i++) {
set.add(arr[i].mod(BigInteger.valueOf(dic)).intValue());
}
dic = dic * 10;
}
System.out.println(count);
}
}- 제일 작은 자리수부터 자리수를 하나씩 늘려가면서 set에 다 집어넣어보고 set에 있는 수가 모두 유니크한지 즉, set의 길이와 입력 받은 학생의 수를 비교한 후 같다면 종료하고 k의 값을 출력하면 되는 문제
12. 스위치 켜고 끄기
👉 소스코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int switchNum = Integer.parseInt(br.readLine());
int[] switchArr = new int[switchNum];
String[] s = br.readLine().split(" ");
for(int j = 0; j < s.length; j++) {
switchArr[j] = Integer.parseInt(s[j]);
}
int personNum = Integer.parseInt(br.readLine());
ArrayList<ArrayList<Integer>> personArr = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < personNum; i++) {
personArr.add(new ArrayList<Integer>());
}
for(int i = 0; i < personNum; i++) {
String[] tmp = br.readLine().split(" ");
for(int j = 0; j < 2; j++) {
personArr.get(i).add(Integer.parseInt(tmp[j]));
}
}
for(int i = 0; i < personArr.size(); i++) {
int idx = personArr.get(i).get(1);
if(personArr.get(i).get(0) == 1) {
for(int j = 0; j < switchArr.length; j++) {
// 입력 받은 스위치를 벗어난다면 반복문 종료
if(idx *( j + 1) > switchArr.length) break;
switchArr[idx * (j + 1) - 1] = switchArr[idx * (j + 1) - 1] == 0 ? 1 : 0;
}
} else {
int start = 1;
while(true) {
// 대칭을 넓혀 가면서 스위치의 범위를 벗어난다면 종료
if(idx - start - 1 < 0 || idx + start - 1 >= switchArr.length) {
switchArr[idx - 1] = switchArr[idx - 1] == 0 ? 1 : 0;
break;
}
if(switchArr[idx - start - 1] != switchArr[idx + start - 1]) {
switchArr[idx - 1] = switchArr[idx - 1] == 0 ? 1 : 0;
break;
} else {
switchArr[idx - start - 1] = switchArr[idx - start - 1] == 0 ? 1 : 0;
switchArr[idx + start - 1] = switchArr[idx + start - 1] == 0 ? 1 : 0;
start++;
}
}
}
}
for(int i = 0; i < switchArr.length; i++) {
System.out.print(switchArr[i] + " ");
if((i+1) % 20 == 0) System.out.println();
}
if(switchArr.length % 20 != 0) System.out.println();
}
}- 남자와 여자 구분해서 구현하면 쉽게 구현 가능한 문제,, 출력하는 부분에서 이해를 못해서 시간을 허비했다.. 가장 단순한 부분이였는데,,
13. 대칭 차집합
👉 소스코드
import java.util.*;
import java.io.*;
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 a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int count = 0;
ArrayList<Integer> aArr = new ArrayList<Integer>();
ArrayList<Integer> bArr = new ArrayList<Integer>();
HashSet<Integer> set = new HashSet<Integer>();
String[] s = br.readLine().split(" ");
for(int i = 0; i < a; i++) {
int n = Integer.parseInt(s[i]);
aArr.add(n);
set.add(n);
}
String[] s1 = br.readLine().split(" ");
for(int i = 0; i < s1.length; i++) {
int n = Integer.parseInt(s1[i]);
bArr.add(n);
if(set.contains(n)) count++;
}
System.out.println(aArr.size() + bArr.size() - (count * 2));
}
}- a와 b집합의 합집합에서 차집합을 빼는 간단한 계산인 문제
14. 베스트셀러
👉 소스코드
import java.util.*;
import java.util.Map.Entry;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
HashMap<String, Integer> map = new HashMap<String, Integer>();
StringTokenizer st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken());
while(num--> 0) {
String s = br.readLine();
map.put(s, map.getOrDefault(s, 0) + 1);
}
int count = 0;
String result = "";
for(Entry<String, Integer> entry : map.entrySet()) {
if(count < entry.getValue() && count != entry.getValue()) {
count = Math.max(count, entry.getValue());
result = entry.getKey();
} else if(count == entry.getValue()) {
if(result.compareTo(entry.getKey()) > 0) result = entry.getKey();
}
}
System.out.println(result);
}
}- map에 값을 저장할 때 키값을 가지고 와서 계속해서 max값을 갱신해준 뒤 반복문을 열어서 max 값과 같은 value라면 해당 키값을 리스트에 add한 후, sort를 진행한 다음 최종 index 0번지에 있는 단어를 출력하면 간단하게 풀이가 가능합니다
저는 입력받을 때 max를 저장해 두지 않고 따로 반복문을 열어서 해당 반복문 내에서 모두 해결하는 방식으로 문제풀이를 진행하였습니다. -> (compareTo 함수를 활용하기 위해서)
15. 올바른 배열
👉 소스코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
ArrayList<Integer> arr = new ArrayList<Integer>();
for(int i = 0; i < num; i++) {
arr.add(Integer.parseInt(br.readLine()));
}
Collections.sort(arr);
int count = Integer.MAX_VALUE;
for(int i = 0; i < arr.size(); i++) {
ArrayList<Integer> tmpArr = new ArrayList<Integer>();
for(int j = 0; j < 5; j++) {
// 올바른 배열인지 판단하기 위해 5개를 만들어본다
if(!arr.contains(arr.get(i) + j)) tmpArr.add(arr.get(i) + j);
}
count = Math.min(count, tmpArr.size());
}
System.out.println(count);
}
}- 5개의 연속된 숫자가 존재하는 배열을 올바른 배열이라고 하는데 문제에서 말하는 올바른 배열을 만들기 위해서 필요한 최솟값을 구하는문제로써 주어진 원소에 대해 연속된 5개의 수를 만들어보고 만들 때 입력 받은 배열에 있는지 없는지 체크를 한다. 체크한 뒤 없는 수만 배열에 넣으면서 배열의 길이를 최솟값으로 갱신하면 쉽게 풀이가 가능한 문제
16. 바닥 장식
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
static char[][] map;
static boolean[][] visited;
static int[] moveN = {-1, 1, 0, 0}, moveM = {0, 0, -1, 1};
static int count = 0, N, M;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
visited = new boolean[N][M];
for(int i = 0; i < N; i++) {
map[i] = br.readLine().toCharArray();
}
for(int i = 0; i < map.length; i++) {
for(int j = 0; j < map[i].length; j++) {
if(!visited[i][j]) {
if(map[i][j] == '-') {
dfs(i,j);
count++;
} else if(map[i][j] == '|') {
dfs(i,j);
count++;
}
}
}
}
System.out.println(count);
}
public static void dfs(int x, int y) {
visited[x][y] = true;
for(int i = 0; i < 4; i++) {
int nextN = x + moveN[i];
int nextM = y + moveM[i];
if(nextN < 0 || nextM < 0 || nextN >= N || nextM >= M || visited[nextN][nextM]) continue;
if(map[x][y] == '-') {
if(x == nextN && map[nextN][nextM] == '-') {
dfs(nextN, nextM);
}
}
if(map[x][y] == '|') {
if(y == nextM && map[nextN][nextM] == '|') {
dfs(nextN, nextM);
}
}
}
}
}- N과 M의 크기가 50이하이기 때문에 선형 탐색으로도 풀이가 가능하나, 그래프 탐색 알고리즘 연습을 하기 위해서 깊이 우선 탐색을 이용하여 풀이를 진행했다.
17. 바닥 장식
👉 소스코드
import java.io.*;
import java.util.*;
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());
long x = Integer.parseInt(st.nextToken());
long y = Integer.parseInt(st.nextToken());
long w = Integer.parseInt(st.nextToken());
long s = Integer.parseInt(st.nextToken());
long result = 0;
if(2 * w < s) {
result = (x + y) * w;
}
else if(2 * w > 2 * s) {
if((x + y) % 2 == 0) {
result = Math.max(x, y) * s;
} else {
result = (Math.max(x, y) - 1) * s;
result += w;
}
} else {
if(x == y) {
result = x * s;
} else {
result = Math.min(x*s, y*s);
result += Math.abs(x - y) * w;
}
}
System.out.println(result);
}
}- 대각선으로 가는 것과 도로를 따라서 가로나 세로방향으로 가는 것 중 유리한 것을 판별해가면서 풀이를 진행하면 된다.
첫 번째로는 대각선으로 가는 것 보다 두번에 걸쳐서 가는 것이 더 최소 시간인 경우, 두번째는 (0,0) 에서 (2,0) 으로 가는 경우를 예로 들 때, (1,0) 을 통해서 가는 경우도 있지만 (1,1) 을 통해서 가는 경우도 있다 (대각선을 선택한 경우) 이런 경우의 가중치를 생각해서 대각선으로 가는 경우가 유리할 때 x,y가 (4, 2) 같은 경우라면 큰 수만큼 대각선 길이를 곱하면 되고 (3, 2) 같은 경우라면 -1을 해줘야 한다. 왜냐하면 대각선으로 움직이는 경우이기 때문에 홀수가 나올 수 없기 때문이다.
마지막으로는 대각선을 사용 후 가로 세로 방향으로 한칸씩 움직이는 경우이다.
18. 물건 팔기
👉 소스코드
import java.io.*;
import java.util.*;
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 num = Integer.parseInt(st.nextToken());
int[][] arr = new int[num][2];
for(int i = 0; i < num; i++) {
String[] s = br.readLine().split(" ");
for(int j = 0; j < 2; j++) {
arr[i][j] = Integer.parseInt(s[j]);
}
}
/*
* 1. 지불 용의 금액순으로 정렬
* 2. 배송비 순으로 정렬
* (오름차순)
*/
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1];
}
});
int result = 0;
int answer = 0;
for(int i = 0; i < num; i++) {
int price = arr[i][0];
int total = 0;
for(int j = 0; j < num; j++) {
if(arr[j][0] >= price) {
if(price - arr[j][1] < 0) continue; // 적자라면 안팜
total += price;
total -= arr[j][1];
}
}
if(result < total) {
result = total;
answer = price;
}
}
System.out.println(answer);
}
}- 입력 값의 크기가 크지 않아 모두 탐색해도 충분한 풀이가 가능,, 우선순위가 되는 지불 용의 금액으로 먼저 오름차순 정렬 그 다음으로 배송비로 오름차순 정렬한 뒤, 최대값을 찾는 문제
19. 문서 검색
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String paper = br.readLine();
String find = br.readLine();
int count = 0;
int index = paper.indexOf(find);
while(index != -1) {
String tmp = paper.substring(index, paper.length());
if(!tmp.contains(find)) break;
index += find.length();
String tmp1 = paper.substring(index, paper.length());
if(tmp1.indexOf(find) != -1) index += tmp1.indexOf(find);
count++;
}
System.out.println(count);
}
}- 문제에서 부르트포스 알고리즘을 추천해서 부르트포스 알고리즘을 이용하여 문제풀이를 진행했다. 주어진 문자열에서 임시 문자열을 만들고 문자열에 찾고자하는 문자열이 있다면 찾고자 하는 문자열의 인덱스만큼 더해주고 그 다음 임시 문자열에서 문자열을 찾는 방식으로 진행했다. 문제풀이를 모두 완료하고 타인의 문제풀이를 봤는데 찾고자하는 문자열을 모두 치환하고 두 처음 문자열에서 없어진 문자열의 길이와 비교할 생각은 못했다,, (부르트포스 알고리즘으로만 풀이를 진행할 생각을 하지 않았어도 해당 아이디어는 떠올리지 못했을 것 같다..)
밀려오는 자괴감~~
20. 사이클 단어
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
HashSet<String> set = new HashSet<String>();
ArrayList<String> list = new ArrayList<String>();
int N = Integer.parseInt(br.readLine());
while(N-->0) {
set.add(br.readLine());
}
int count = 0;
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
String s = iterator.next();
boolean flag = false;
for (int i = 0; i < s.length(); i++) {
if(!list.contains(s)) {
list.add(s);
flag = true;
}
s = s.substring(1, s.length()) + s.substring(0, 1);
}
if(flag) count++;
}
System.out.println(count);
}
}- set으로 중복되는 단어를 제거하고, iterator 객체를 이용하여 set에서 꺼낸 단어를 사이클로 돌려가면서 없는 단어는 list에 추가하고 단어당 list에 추가될때만 flag 변수로 체크하여 단어의 개수를 체크하는 방식으로 문제풀이를 진행했다.
21. 나는야 포켓몬 마스터 이다솜
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
HashMap<Integer, String> map = new HashMap<Integer, String>();
HashMap<String, Integer> mapNum = new HashMap<String, Integer>();
int seq = 1;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
while(N--> 0) {
String s = br.readLine();
map.put(seq, s);
mapNum.put(s, seq);
seq++;
}
int num = 0;
boolean flag = false;
while(M--> 0) {
String find = br.readLine();
if(find.matches("[0-9]+")) {
num = Integer.parseInt(find);
flag = true;
}
if(flag) {
bw.write(map.get(num) + "\n");
num = 0;
flag = false;
} else bw.write(mapNum.get(find) + "\n");
}
bw.flush();
br.close();
bw.close();
}
}- 시간 복잡도 O(1)를 가지는 HashMap을 이용하여 문제풀이 진행, int값을 Key로 가지는 map 하나 String 값을 Key로 가지는 Map하나를 각각 선언한다. 그리고 찾고자하는 값에 따라서 get() 메서드를 이용하여 간편혀게 가져오면 된다.
22. 공통 순열
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
while(sc.hasNextLine()) {
char[] a = sc.nextLine().toCharArray();
char[] b = sc.nextLine().toCharArray();
HashMap<Character, Integer> mapA = new HashMap<Character, Integer>();
HashMap<Character, Integer> mapB = new HashMap<Character, Integer>();
for(char c : a) mapA.put(c, mapA.getOrDefault(c, 0) + 1);
for(char c : b) mapB.put(c, mapB.getOrDefault(c, 0) + 1);
ArrayList<Character> res = new ArrayList<Character>();
for(char k: mapA.keySet()) {
if(mapB.containsKey(k)) {
int m = Math.min(mapA.get(k), mapB.get(k));
while(m-->0)
res.add(k);
}
}
String result = "";
Collections.sort(res);
for(char c : res) {
result += c;
}
sb.append(result).append("\n");
}
System.out.println(sb);
}
}- a, b 두 순열을 입력 받아서 더 작은 문자들만 찾으면 되는 문제, java의 EOF는 hasNextLine()으로 처리했다.
23. 행운의 티켓
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String num = br.readLine();
// 탐색의 범위
int leng = num.length() % 2 == 0 ? num.length() : num.length() - 1;
int L, R, start, luckyL, luckyR, mid;
leng += 2;
while(leng > 2) {
start = 0;
leng -= 2;
luckyL = start;
luckyR = leng;
while(luckyR <= num.length()) {
mid = (luckyL + luckyR) / 2;
L = 0; R = 0;
for(int i = luckyL; i < mid; i++) L += Character.getNumericValue(num.charAt(i));
for(int i = mid; i < luckyR; i++) R += Character.getNumericValue(num.charAt(i));
if(L == R) {
System.out.println(leng);
return;
}
luckyL++; luckyR++;
}
}
System.out.println(0);
}
}- 가장 긴 길이부터 체크하면서 문제에서 찾고자 하는 행운의 티켓 조건이 만족하면 종료하면 됨.
시작 지점 끝점 중간지점만 찾아주면서 문제를 진행해 나가면 된다.
24.숫자놀이
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
static String[] number = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int index = 0;
String[] arr = new String[N - M + 1];
String[] s = new String[N - M + 1];
for(int i = M; i <= N; i++) {
if(i < 10) {
s[index++] = number[i];
} else {
String tmp = "";
int tmpInt = i;
String tmp1 = number[tmpInt % 10];
tmpInt /= 10;
tmp += number[tmpInt % 10];
tmp += " ";
tmp += tmp1;
s[index++] = tmp;
}
}
Arrays.sort(s);
for(int i = 0; i < s.length; i++) {
String tmp = s[i];
String tmp1 = "";
String tmp2 = "";
if(tmp.contains(" ")) {
tmp1 = tmp.substring(0, tmp.indexOf(" "));
tmp2 = tmp.substring(tmp.indexOf(" ") + 1, tmp.length());
}
String result = "";
// 1의 자리 숫자인경우와 십의 자리숫자 중 앞자리 수
for(int j = 0; j < number.length; j++) {
if(!tmp.contains(" ")) {
if(number[j].equals(tmp)) {
arr[i] = String.valueOf(j);
break;
}
} else {
if(number[j].equals(tmp1)) result += String.valueOf(j);
}
}
// 십의 자리 숫자 중 뒤의 숫자
for(int j = 0; j < number.length; j++) {
if(number[j].equals(tmp2)) result += String.valueOf(j);
}
if(result.length() == 2) arr[i] = result;
}
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
if((i + 1) % 10 == 0) System.out.println();
}
}
}25. 알바생 강호
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cus = Integer.parseInt(br.readLine());
Integer[] arr = new Integer[cus];
for(int i = 0; i < arr.length; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr, Collections.reverseOrder());
long result = 0;
for(int i = 0; i < arr.length; i++) {
int tip = arr[i] - ((i+1) - 1);
if(tip >= 0) {
result += tip;
} else break; // 팁이 음수인 경우, 이후 손님들은 팁을 주지 않으므로 반복문을 종료합니다.
}
System.out.println(result);
}
}- 내림차순 정렬하여 음수가 나오기전까지 더하면 되는 문제
26.듣보잡
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
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());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
ArrayList<String> list = new ArrayList<String>();
HashSet<String> set = new HashSet<String>();
for(int i = 0; i < N; i++) {
set.add(br.readLine());
}
for(int i = 0; i < M; i++) {
String s = br.readLine();
if(set.contains(s)) list.add(s);
}
Collections.sort(list);
bw.write(list.size() + "\n");
for(String s : list) bw.write(s + "\n");
bw.flush();
br.close();
bw.close();
}
}27.차집합
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
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());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
HashSet<Integer> set = new HashSet<Integer>();
st = new StringTokenizer(br.readLine());
while(a-- > 0) set.add(Integer.parseInt(st.nextToken()));
st = new StringTokenizer(br.readLine());
while(b--> 0) {
int n = Integer.parseInt(st.nextToken());
if(set.contains(n)) set.remove(n);
}
ArrayList<Integer> list = new ArrayList<Integer>();
Iterator<Integer> iter = set.iterator();
while(iter.hasNext()) {
list.add(iter.next());
}
Collections.sort(list);
bw.write(list.size() + "\n");
for(int i : list) bw.write(i + "\n");
bw.flush();
br.close();
bw.close();
}
}-a 집합 입력받은 뒤, b를 받을 때 a에 있으면 set에서 삭제한 후 정렬하여 출력
28.주몽
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
int[] material = new int[N];
String[] s = br.readLine().split(" ");
for(int i = 0; i < N; i++) material[i] = Integer.parseInt(s[i]);
Arrays.sort(material);
int left = 0;
int right = material.length - 1;
int count = 0;
while(left < right) {
if(material[left] + material[right] == M) { // 갑옷을 만들 수 있다면
count++;
// 포인터를 하나씩 증감하는 이유는 종료조건인 두 포인터가 엇갈리면 더이상 갑옷을 만들 수 없다고 판단하기 때문
left++;
right--;
} else if(material[left] + material[right] > M) {
right--;
} else left++;
}
System.out.println(count);
}
}- 두포인터 알고리즘으로 풀이 진행
29. 수들의 합 2
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] arr = new int[n];
String[] s = br.readLine().split(" ");
for(int i = 0; i < s.length; i++) arr[i] = Integer.parseInt(s[i]);
int left = 0, right = 0, sum = 0, count = 0;
while(true) {
if(sum >= m) sum -= arr[left++]; // sum이 m 이상인 경우, sum에서 arr[left]를 빼고 left를 오른쪽으로 이동
else if(right == n) break; // right이 배열의 끝에 도달한 경우, 반복문 종료
else sum += arr[right++]; // sum이 m 미만인 경우, sum에 arr[right]를 더하고 right를 오른쪽으로 이동
if(sum == m) count++; // sum이 m과 같은 경우, count 증가
}
System.out.println(count);
}
}30. 카드2
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int card = Integer.parseInt(br.readLine());
Deque<Integer> dq = new ArrayDeque<Integer>();
for(int i = 0; i < card; i++) {
dq.offer(i + 1);
}
while(dq.size() != 1) {
dq.poll();
dq.offerLast(dq.pollFirst());
}
System.out.println(dq.poll());
}
}- 덱으로 문제에서 요구하는대로 구현하면 되는 문제
31. 로프
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int result = Integer.MIN_VALUE;
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
// 오름차순으로 정렬 후, 작은 인덱스 * 남은 로프의 개수를 갱신
for(int i = 0; i < n; i++) {
result = Math.max(result, arr[i] * (arr.length - i));
}
System.out.println(result);
}
}- 그리디 알고리즘을 이용하여 풀이할 수 있는 문제입니다. 로프를 정렬해놓고 항상 최댓값이 나오는 경우는 인덱스 값 * 남은 로프의 수 이기 때문에 배열을 정렬 후, 갱신하면서 반복문을 진행하면 됩니다.
32. 수열
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
String[] s = br.readLine().split(" ");
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(s[i]);
}
int cnt = 1;
int ans = 1;
for(int i = 1; i < n; i++) {
if(arr[i-1] <= arr[i]) {
cnt++;
}
else {
ans = Math.max(ans, cnt);
cnt = 1;
}
}
ans = Math.max(ans, cnt);
cnt = 1;
for(int i = 1; i < n; i++) {
if(arr[i-1] >= arr[i]) {
cnt++;
}
else {
ans = Math.max(ans, cnt);
cnt = 1;
}
}
ans = Math.max(ans, cnt);
System.out.println(ans);
}
}- 연속된 작은 값, 큰 값을 간단하게 비교하여 풀이 진행
33. 암기왕
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
while(n--> 0) {
int N = Integer.parseInt(br.readLine());
HashSet<Integer> note1 = new HashSet<Integer>();
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) note1.add(Integer.parseInt(st.nextToken()));
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for(int i = 0; i < M; i++) {
int tmp = Integer.parseInt(st.nextToken());
if(note1.contains(tmp)) bw.write(1 +"\n");
else bw.write(0 + "\n");
}
}
bw.flush();
bw.close();
br.close();
}
}- 처음에는 입력 값을 다 받고나서 문제에서 요구하는 것을 처리해줬는데 시간초과가 나서 입력을 받으면서 처리를 해주니 문제를 해결할 ㄱ수 있었다. 수첩1에 받는 값은 set에 넣어서 중복 값을 제거하고 수첩2에 받는 값은 입력 받음과 동시에 수첩1에 있는지 확인하고 있으면 1을 기록, 없으면 0을 기록한다.
34. 설탕배달
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
if(n % 5 == 0) System.out.println(n / 5);
else {
int cnt = n / 5;
while(cnt >= 0) {
if((n - cnt * 5) % 3 == 0) {
cnt += (n - cnt * 5) / 3;
System.out.println(cnt);
break;
}
cnt -=1;
}
if(cnt < 0) System.out.println(-1);
}
}
}- 3kg, 5kg 중 최대한 5kg를 많이 사용해야 한다. 5를 가장 많이 사용할 수 있게 5의 최대 수를 구하고 그 수만큼 반복문을 돌리면서 3을 사용해야 하는지 아닌지를 판별하는식으로 풀이했다.
35. 게임을 만든 동준이
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
int result = 0;
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
for(int i = n - 1; i >= 1; i--) {
if(arr[i] <= arr[i - 1]) {
result += arr[i - 1] - (arr[i] - 1);
arr[i - 1] = arr[i] - 1;
}
}
System.out.println(result);
}
}- 문제에서는 점수를 내리는 것을 최소한으로 하라고 했기 때문에 각 레벨별로 1차이가 나도록 하면 된다. 인덱스를 끝에서부터 거꾸로 돌리면서 더 낮은 레벨이 큰 점수를 가지고 있다면 그 전 인덱스의 점수에서 -1해서 바꿔주면서 이를 체크하면 되는 문제이다.
36. 수학숙제
👉 소스코드
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
ArrayList<BigInteger> list = new ArrayList<BigInteger>();
int n = Integer.parseInt(br.readLine());
while(n--> 0) {
String input = br.readLine();
String result = "";
for(int i = 0; i < input.length(); i++) {
if(input.charAt(i) >= '0' && input.charAt(i) <= '9') {
result += input.charAt(i);
} else {
if(!result.isEmpty() && isNumeric(result)) {
list.add(new BigInteger(result));
result = "";
}
}
}
if(!result.isEmpty() && isNumeric(result)) list.add(new BigInteger(result));
}
Collections.sort(list);
for(int i = 0; i < list.size(); i++) {
sb.append(list.get(i));
if(i != list.size() -1) sb.append("\n");
}
System.out.println(sb.toString());
br.close();
}
public static boolean isNumeric(String str) {
return str.matches("\\d+");
}
}- 문자열내에 수를 찾으면 되는데 처음에 Integer로 처리했다가 계속 NumberFormat 오류가 나오고 빠져나오지 못했다. 문자열의 길이를 생각 하지 않고 문제 풀이를 진행하여 발생한 문제이다. BigInteger로 변경해서 풀이 할 수 있었다.
37. 에라토스테네스의 체
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
static boolean[] prime;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
prime = new boolean[n + 1];
prime[0] = prime[1] = true;
int count = 0;
int result = 0;
for(int i = 2; i <= n; i++) {
if(!prime[i]) {
count++;
if(count == k) {
result = i;
break;
}
for(int j = i * i; j <= n; j += i) {
if(!prime[j]) {
prime[j] = true;
count++;
}
if(count == k) {
result = j;
break;
}
}
}
}
System.out.println(result);
}
}- 소수 찾는 알고리즘인 에라토스테네스의 체를 진행하면서 prime에 배수들을 true로 바꿔줄 때 count 변수로 체크하여 문제에서 원하는 k번째로 지워지는 수를 찾으면 되는 문제
38. 링
👉 소스코드
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int firstCir = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
int ring = Integer.parseInt(st.nextToken());
if(i == 0) firstCir = ring;
else {
if(firstCir % ring == 0) bw.write(String.valueOf(firstCir / ring) + "/1\n");
else {
int eucdNum = eucd(firstCir, ring);
bw.write(String.valueOf(firstCir / eucdNum) + "/" + String.valueOf(ring / eucdNum) + "\n");
}
}
}
bw.flush();
br.close();
bw.close();
}
public static int eucd(int big, int small) {
if(big % small == 0) return small;
else return eucd(small, big % small);
}
}- 나누어 떨어지는 것은 분수로 간단하게 표현하면 되는데 그렇지 않은 수는 최대공약수를 구하여 분수를 표현하면 되는 문제
39. 좋은 단어
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int count = 0;
while(n--> 0) {
Stack<Character> st = new Stack<Character>();
boolean flag = false;
String word = br.readLine();
for(int i = 0; i < word.length(); i++) {
if(!st.isEmpty()) {
if(st.peek() == word.charAt(i)) {
st.pop();
flag = true;
} else st.push(word.charAt(i));
} else st.push(word.charAt(i));
}
if(flag && st.size() == 0) count++;
}
System.out.println(count);
}
}- 스택으로 간단하게 구현 가능한 문제
40. 균형잡힌 세상
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String str = "";
while(! (str = br.readLine()).equals(".")) {
Stack<Character> st = new Stack<Character>();
for(int i = 0; i < str.length(); i++) {
if(!st.isEmpty()) {
if(str.charAt(i) == ')' && st.peek() == '(') st.pop();
else if(str.charAt(i) == ']' && st.peek() == '[') st.pop();
else {
if(str.charAt(i) == '(' || str.charAt(i) == ')' || str.charAt(i) == '[' || str.charAt(i) == ']') {
st.push(str.charAt(i));
}
}
} else if(str.charAt(i) == '(' || str.charAt(i) == ')' || str.charAt(i) == '[' || str.charAt(i) == ']') {
st.push(str.charAt(i));
}
}
if(st.size() == 0) bw.write("yes\n");
else bw.write("no\n");
}
bw.flush();
bw.close();
br.close();
}
}- 문자열 입력받은 후 순회하면서 stack에 넣는다. 넣기 전 입력 받은 문자열 중 닫는 괄호일 경우 stack에서 상위에 있는 값이 동일한 타입의 여는 괄호일 경우 stack에서 제거를 해주는 방식으로 구현을 하고 마지막에 stack 사이즈가 0이라면 균형잡힌 경우로 판별하면 되겠다.
41. 상근이의 여행
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
while(T--> 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < N + 1; i++) graph.add(new ArrayList<Integer>());
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
graph.get(x).add(y);
graph.get(y).add(x);
}
bw.write(N - 1 + "\n");
}
bw.flush();
bw.close();
br.close();
}
}42. GCD의 합
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
while(T--> 0) {
long result = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int[] arr = new int[n];
for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());
for(int i = 0; i < arr.length; i++) {
for(int j = i + 1; j < arr.length; j++) {
result += gcd(Math.max(arr[i], arr[j]), Math.min(arr[i], arr[j]));
}
}
bw.write(result + "\n");
}
bw.flush();
bw.close();
br.close();
}
public static int gcd(int x, int y) {
if(x % y == 0) return y;
else return gcd(y, x % y);
}
}- 합을 구하는 변수의 자료형을 long으로 해주어야 한다. 입력이 주어지는 수가 1,000,000을 넘지 않는다고 하였는데 입력으로 주어지는 수들이 999,999일 경우 int를 초과하는 수가 나오게 되므로 long 자료형 사용
43. 30
👉 소스코드
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
int sum = 0;
char[] charArr = str.toCharArray();
Arrays.sort(charArr);
StringBuilder sb = new StringBuilder();
for(int i = charArr.length - 1; i >= 0; i--) {
int num = charArr[i] - '0';
sum += num;
sb.append(num);
}
if(charArr[0] != '0' || sum % 3 != 0) {
System.out.println(-1);
return;
}
System.out.println(sb.toString());
}
}- 입력값의 범위 제한 떄문에 처음에는 BigInteger로 입력받아 반복문을 돌려가면서 해결하려고 했는데 아래와 같이 30이 될 수 없는 조건을 파악할 수 있다면 쉽게 풀이할 수 있는 문제였다.
- 30이 될 수 없는 조건
- 문자 배열의 각 원소를 더한 값이 3의 배수가 아닐 때
- 주어진 문자열에서 0이 한개라도 없을 때
43. 제로
👉 소스코드
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int k = Integer.parseInt(br.readLine());
Stack<Integer> st = new Stack<Integer>();
while(k--> 0) {
int tmp = Integer.parseInt(br.readLine());
if(!st.isEmpty() && tmp == 0) st.pop();
else st.push(tmp);
}
int result = 0;
for(int i : st) result += i;
System.out.println(result);
}
}- stack에 입력받은 수를 넣으면서 0이면 최근에 입력 받은 수를 지우고 남은 수들을 모두 더해 출력하면 되는 문제
44. 국영수
👉 소스코드
import java.io.*;
import java.util.Comparator;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
Student[] students = new Student[n];
for(int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
students[i] = new Student(
st.nextToken(),
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken())
);
}
Arrays.sort(students);
for(Student s : students) bw.write(s.name + "\n");
bw.flush();
bw.close();
br.close();
}
static class Student implements Comparable<Student> {
String name;
int korean, english, math;
public Student(String name, int korean, int english, int math) {
this.name = name;
this.korean = korean;
this.english = english;
this.math = math;
}
@Override
public int compareTo(Student other) {
if(this.korean != other.korean) return Integer.compare(other.korean, this.korean);
else if(this.english != other.english) return Integer.compare(this.english, other.english);
else if(this.math != other.math) return Integer.compare(other.math, this.math);
else return this.name.compareTo(other.name);
}
}
}- 객체를 이용하여 타입이 다른 입력 값을 받고, Comparable 클래스의 인터페이스 중 compareTo 추상 메소드를 재정의하여 다중정렬 조건을 문제에서 요구하는대로 정리하여 정렬한 후 출력
45. 세 개의 소수 문제
👉 소스코드
import java.io.*;
import java.util.Comparator;
import java.util.*;
public class Main {
static boolean[] prime = new boolean[1001];
static int max = 1000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
primeCheck();
int T = Integer.parseInt(br.readLine());
while(T--> 0) {
int K = Integer.parseInt(br.readLine());
exit : for(int i = 2; i <= K; i++) {
for(int j = 2; j <= K; j++) {
for(int k = 2; k <= K; k++) {
if((!prime[i] && !prime[j] && !prime[k]) && i + j + k == K) {
System.out.println(i + " " + j + " " + k);
break exit;
}
}
}
}
}
}
public static void primeCheck() {
prime[0] = prime[1] = true;
for(int i = 2; i * i <= max; i++) {
if(!prime[i]) {
for(int j = i * i; j <= max; j += i) prime[j] = true;
}
}
}
}- 에라토스테네스의 체를 이용하여 입력범위인 1,000까지 소수 배열 prime을 만들고 입력 받은 수 까지 반복문을 돌면서 소수이면서 더한 값들이 k와 동일하다면 출력
46. 2 + 1 세일
👉 소스코드
import java.io.*;
import java.util.Comparator;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int sum = 0;
int result = 0;
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i = 0; i < n; i++) list.add(Integer.parseInt(br.readLine()));
list.sort(Collections.reverseOrder());
for(int i = 0; i < n; i++) {
sum += list.get(i);
if((i + 1) % 3 ==0) {
sum -= list.get(i);
result += sum;
sum = 0;
}
}
if(sum != 0) result += sum;
System.out.println(result);
}
}- 가장 큰 수들끼리 묶어서 혜택 받으면서 그리디하게 풀이하면 되므로 역순으로 정렬하여 문제를 해결했다.
47. 카드
👉 소스코드
import java.io.*;
import java.util.*;
import java.util.Map.Entry;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
HashMap<Long, Integer> map = new HashMap<Long, Integer>();
while(n--> 0) {
Long tmp = Long.parseLong(br.readLine());
map.put(tmp, map.getOrDefault(tmp, 0) + 1);
}
Long resultKey = (long) 0;
int resultValue = Integer.MIN_VALUE;
for(Entry<Long, Integer> entry : map.entrySet()) {
if(resultValue == entry.getValue()) {
resultKey = Math.min(resultKey, entry.getKey());
} else if(resultValue < entry.getValue()) {
resultValue = entry.getValue();
resultKey = entry.getKey();
}
}
System.out.println(resultKey);
}
}- 입력 받는 값을 HashMap에 저장하되 입력값의 범위가 2^62 이기 때문에 int의 범위를 벗어난다. 그러므로 Long으로 입력 받아 Long으로 저장한 후, Entry 객체를 이용하여 map을 순회하며 많이 가지고 있는 카드를 갱신하면서 해결한 문제
48. 접미사 배열
👉 소스코드
import java.io.*;
import java.util.*;
import java.util.Map.Entry;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
ArrayList<String> list = new ArrayList<String>();
String s = br.readLine();
int leng = s.length();
for(int i = 0; i < leng; i++) {
list.add(s);
s = s.substring(1, s.length());
}
Collections.sort(list);
for(String str : list) bw.write(str + "\n");
bw.flush();
bw.close();
br.close();
}
}- 선언해 놓은 배열에 받은 문자열을 substring 해 가면서 넣어주고 정렬하면 되는 문제
49. 오셀로 재배치
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
while(T--> 0) {
ArrayList<Integer> location = new ArrayList<Integer>();
int strLength = Integer.parseInt(br.readLine());
String input = br.readLine();
String goal = br.readLine();
int wCount = 0;
int bCount = 0;
for(int i = 0; i < strLength; i++) {
if(input.charAt(i) != goal.charAt(i)) {
if(input.charAt(i) == 'W') wCount++;
else bCount++;
}
}
int count = bCount >= wCount ? bCount : wCount;
bw.write(count + "\n");
}
bw.flush();
bw.close();
br.close();
}
}- 문제에서 제시하는 두가지 방법이 있는데 쉽게 풀이를 진행해 보면 결국에는 W와 B의 개수를 세어 최소값을 출력하면 되는 문제
50. 점화식
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
long[] dp = new long[36];
dp[0] = dp[1] = 1;
for(int i = 2; i < 36; i++) {
for(int j = 0; j < i; j++) {
dp[i] += (dp[j] * dp[i - 1 - j]);
}
}
System.out.println(dp[n]);
br.close();
}
}- 문제에서 요구하는 부분을 그대로 구현
51. 소가 길을 건너간 이유3
👉 소스코드
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] arr = new int[n][2];
StringTokenizer st;
for(int i = 0; i < arr.length; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int firstCow = arr[0][0] + arr[0][1];
for(int i = 1; i < arr.length; i++) {
if(arr[i][0] >= firstCow) firstCow = arr[i][0] + arr[i][1];
else firstCow += arr[i][1];
}
System.out.println(firstCow);
br.close();
}
}- 도착한 시간과 검문 시간을 입력 받고 도착한 시간을 기준으로 오름차순 정렬한다. 첫번째 소는 곧바로 검문을 받을 수 있기 때문에 변수에 따로 저장을 해주고 두번째 소부터는 반복문을 통하여 현재 시간보다 크거나 같은지 확인한 후 투입할 수 있다.
52. 피보나치 비스무리한 수열
👉 소스코드
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
long[] dp = new long[n + 1];
if(n <= 2) System.out.println(1);
else {
dp[1] = dp[2] = dp[3] = 1;
for(int i = 4; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 3];
}
System.out.println(dp[n]);
}
br.close();
}
}- f(n) = f(n - 1) + f(n - 3) 이라는 피보나치 비스무리한 수열을 구현하면 되는 문제이다. 최대 입력값인 116이 들어오게 된다면 116번째 자리의 피보나치 수는 7536815746437618530가 나오게 되므로 int 배열로는 범위 밖의 값이 나오게 된다. 따라서 long배열로 구현을 해줘야 통과할 수 있게 된다.
53. 피보나치수 7
👉 소스코드
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] dp = new int[n + 1];
dp[1] = 1;
for(int i = 2; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
}
System.out.println(dp[n]);
}
}- 문제에서 피보나치 수를 1,000,000,007로 나눈 나머지로 출력하라고 요구하는데 피보나치 수를 구하고 출력하면 범위를 벗어나기 때문에 피보나치 수를 구하여 저장할 때 이 요구사항을 이행해주면 된다.
53. Router
👉 소스코드
import java.io.*;
import java.util.*;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
Queue<Integer> q = new LinkedList<Integer>();
while(true) {
int packit = Integer.parseInt(br.readLine());
if(packit == -1) break;
else {
if(q.size() < n) {
if(packit == 0 && !q.isEmpty()) q.poll();
else q.offer(packit);
} else if(q.size() == n && packit == 0) q.poll();
}
}
int leng = q.size();
if(leng <= 0) {
bw.write("empty");
} else {
for(int i = 0; i < leng; i++) {
bw.write(q.poll() + " ");
}
}
bw.flush();
bw.close();
br.close();
}
}- 큐로 먼저 들어오는 패킷에 대해 처리해주는 식으로 구현
54. 화살표 그리기
👉 소스코드
import java.io.*;
import java.util.*;
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[][] arrow = new int[N][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
arrow[i][0] = Integer.parseInt(st.nextToken());
arrow[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arrow, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int lengthSum = 0;
for (int i = 0; i < N; i++) {
int min = Integer.MAX_VALUE;
for (int j = i - 1; j >= 0; j--) {
if (arrow[i][1] == arrow[j][1]) {
min = Math.min(min, Math.abs(arrow[i][0] - arrow[j][0]));
break;
}
}
for (int j = i + 1; j < N; j++) {
if (arrow[i][1] == arrow[j][1]) {
min = Math.min(min, Math.abs(arrow[i][0] - arrow[j][0]));
break;
}
}
lengthSum += min;
}
System.out.println(lengthSum);
br.close();
}
}- 점의 위치를 기준으로 정렬한 후, P점에서 찾고자 하는 가장 가까운 거리이면서 색상이 동일한 점을 찾기 위해서는 앞뒤로 반복문을 나누어서 진행해야 한다. 앞뒤로 진행하면서 작은 값만 더해주면 된다.
55. 점프왕 젤리 (Small)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
static int[][] map;
static boolean[][] visited;
static int[] moveX = {0, 1}, moveY = {1,0};
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
visited = new boolean[N][N];
for(int i = 0; i < N; i ++) {
String[] tmp = br.readLine().split(" ");
for(int j = 0; j < N; j++) map[i][j] = Integer.parseInt(tmp[j]);
}
bfs();
System.out.println("Hing");
br.close();
}
static void bfs() {
visited[0][0] = true;
Queue<Loc> q = new LinkedList<Loc>();
q.offer(new Loc (0, 0, map[0][0]));
while(!q.isEmpty()) {
Loc location = q.poll();
if(map[location.x][location.y] == -1) {
System.out.println("HaruHaru");
System.exit(0);
}
for(int i = 0; i < 2; i++) {
int nextX = location.x + moveX[i];
int nextY = location.y +moveY[i];
if(i == 0) nextY += location.num - 1;
else nextX += location.num - 1;
if(nextX >= N || nextY >= N || nextX < 0 || nextY < 0 || visited[nextX][nextY]) continue;
q.offer(new Loc(nextX, nextY, map[nextX][nextY]));
visited[nextX][nextY] = true;
}
}
}
static class Loc {
int x, y, num;
public Loc(int x, int y, int num) {
this.x = x;
this.y = y;
this.num = num;
}
}
}- bfs를 통해 다음 스텝을 가기전 현재 땅에 적혀있는 수를 확인해주면서 -1을 찾아서 진행.