개발하는 기계공학도

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net import java.util.ArrayDeque; import java.util.Deque; import java.util.Scanner; public class Q_9935 { //두 줄 받을 거라 오랜만에 Scanner 사용해보자. static Scanner sc = new Scanner(System.in); //끝 쪽 추가 삭제를 주로 할테니까 ArrayDeque static..

https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net import java.io.*; public class Q_17609 { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int result; public static vo..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 전형적인 DFS, BFS 문제에 효율성을 추가한 문제이다. 아무것도 안 잠기는 경우 = 안전 영역 1개 그 외에 판단해야 하는 경우 각 위치의 높이가 해당하는 지점 예를 들면 높이가 (1, 2, 2, 3, 3, 4, 8) 이라면, 1, 2, 3, 4, 8 일때 확인함으로서 확인 횟수를 줄일 수 있다. => Set을 사용해서 중복된 높이를 지웠다. 이번에는 dfs로 풀어보고 싶었는데 최악의 경우에 스택이 ..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 전형적인 bfs, dfs 문제이다. 일정 때문에 마음이 급해 코드를 깔끔하게 작성하지 못했다. 각 그림마다 최댓값을 구하기 위해 큐 하나를 더 사용했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.S..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 사실 얼마 전에 풀었던 탑 문제와 개념적으로 아예 같은 문제라 금방 풀었다. 100만개를 전부 비교하면 시간복잡도 N^2 이라 시간이 부족할 것이고 스택을 사용해 비교할 필요가 없는 부분들은 제거하면서 확인했다. https://godhkekf24.tistory.com/93 [백준 - JAVA] 2493번 : 탑 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 처음에는 단순히 값 비교를 하나하나 하는 방식을 생각했는데 최악의 경우 500000^2 회 비교를 해야하기 때문에 시간초과가 날 것 같았다. 매번 전부를 계산하는 것은 안되고 진행 과정 중간에 쳐낼 수 있는 것은 쳐내야 했는데 스택에 쌓으면서 전에 있던 숫자보다 크다면 더 이상 스택에 쌓아놓을 필요가 없다는 것을 알았다. 새로운 숫자가 들어올 때 본인보다 작으면 버리고 본인보다 크면 위에 쌓는 ..

https://www.acmicpc.net/problem/18115 18115번: 카드 놓기 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. www.acmicpc.net 취업 스터디 덕분에 알고리즘을 다시 블로그에 올리게 됐습니다. 취업 스터디 감사합니다. 어떤 3가지 작업을 실행했더니 1 ~ N 으로 정렬이 되었다! 그럼 반대로 돌려봐라! 아래에서부터 N->1 로 쌓여 있었기 때문에 1부터 N까지 순서대로 반대 작업을 수행하면 된다. 1번의 반대 작업은 첫번째 순서에 넣으면 된다. 2번의 반대 작업은 두번째 순서에 넣으면 된다. 3번의 반대 작업은 마지막 순서에..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net // 먼저 받은 수들을 배열에 넣고 정렬한다. 그 이후 이분탐색으로 수를 찾는다. // 사실 하나의 수가 있는지 없는지 확인하는 과정은 정렬 후 이분탐색을 활용하는 것보다 하나씩 확인하는 작업이 더 빠를 수 있다. // 하지만 지금은 여러개의 수를 확인해야 하기 때문에 정렬 후 이분탐색이 훨씬 빠른 것으로 추측해 볼 수 있다. //프로덕션코드 imp..

https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 일단 출력물을 Ball이라는 객체로 생각하고 큐에다 다 넣어놓고 차례대로 조건 확인해주면 되겠다. Ball에는 location과 priority 넣어주고 큐에 들어있는 볼을 빼면서 나와야하는 priority가 나오면 location확인하고 값 확인. //테스트코드 import org.junit.jupiter.api.BeforeEach; import org.junit..

https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net // 기본값 0층 i호에 있을때 i명이 있다고 먼저 초깃값 지정해준 뒤에. // 재귀함수로 계속 역으로 불러오면 되겠다. //프로덕션코드 mport java.util.Scanner; public class Quiz2775 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int numberOfTestCase = scanner.nextIn..