자두의 데브로그

https://www.acmicpc.net/problem/1764 [문제 이해]듣도 못한 사람의 수 N, 보도 못한 사람의 수 M을 각각 입력 받고 String 배열 N과 M에 모두 속하는 사람의 수와 이름을 찾아서 출력하면 되는 문제였다.  [문제 풀이]N만큼의 크기를 갖는 ArrayList와 M만큼의 크기를 갖는 ArrayList를 각각 만들어서 ArrayList에 있는 contains() 함수를 사용해서 함수 내에 있는 원소를 비교하면 될 줄 알았는데 시간 초과가 났다.. 찾아보니 HashSet의 contains() 함수를 사용해야 시간초과가 안난다고 해서 HashSet을 사용해서 문제를 풀었다. HashSet의 contains() = 시간복잡도 : O(1)ArrayList의 contains() =..

https://www.acmicpc.net/problem/2798 [문제 이해]브루트포스 문제임을 알면 쉽게 풀 수 있는데 브루트포스인지 아닌지 스스로 판별을 하기도 전에 문제 유형을 봐버려서 금방 해결 방법을 생각해냈다. 3장의 카드만 뽑는데 모든 경우에 대해서 다 탐색해서 가장 목표한 수에는 가깝지만 넘지는 않는 수를 만드는 방법을 찾으면 되는 문제였다. [문제 풀이]문제를 풀면서 굳이 3중 for문을 탈출하는 부분을 구현하겠다고 break 걸었다가 한 번 틀렸는데 이 부분을 제외하니까 바로 정답 처리가 됐다. 가장 첫 번째로 탐색하는 건(i) 처음부터 마지막에서 2번째까지만 탐색해도 되므로 for문에서 n-3까지만 돌면 됐고(0~n-3) 같은 원리로 두 번째 카드(j)는 n-1(i+1~n-2), 마..

https://www.acmicpc.net/problem/1010 [문제 이해]동적 프로그래밍 문제였다. nCr 을 생각해내면 풀 수 있는 문제였는데 완전 잊고 있었다,, 재귀로도 풀 수 있고 반복문으로도 풀 수 있는데 재귀보다는 반복문을 사용해서 푸는 방식을 선택했다. [문제 풀이]이차원 배열로 나타내면1C0 1C12C0 2C1 2C23C0 3C1 3C2 3C3...이런 느낌이니까 가장 앞줄 즉, arr[i][0]과 가장 마지막 즉, arr[i][i]의 값은 1로 넣어주고 나머지 값은 [i-1][j] + [i-1][j-1] 값을 저장해주면 된다. 이를 통해 입력된 값 중 큰 값을 행의 인덱스로 지정해서 출력하면 된다.import java.io.*;import java.util.*;public class..

1. 10870번 피보나치 수 5 https://www.acmicpc.net/problem/10870 [문제 이해]피보나치 수를 어떻게 동적 프로그래밍으로 구현하는지 알고만 있다면 어렵지 않은 문제였다. 배열을 N보다 하나 크게 만들어서 0은 무시하고 인덱스 1번부터 원하는 값을 넣을 수 있도록 구현하였다. [문제 풀이]1 이나 2 면 1을 넣고 다른 값이면 i-1과 i-2번째 인덱스의 값을 더해서 넣을 수 있도록 구현했다. import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buffered..

체력 이슈로 3일차는 매우 난이도가 낮은 문제들로 ,, 한 번에 풀이해보겠습니다~ 1. [자바] 10807번 개수 세기 (https://www.acmicpc.net/problem/10807) [문제 이해]배열에 입력 받은 값을 저장하고 가장 마지막에 입력 받은 정수가 배열 안에 몇 개나 있는지 찾는 문제였다. [문제 풀이]arr에 차례로 저장하고 비교해서 출력만 하면 되는 간단한 문제였다!  import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStr..

https://www.acmicpc.net/problem/28278 [문제 이해]덱,,,을 사용해서 쉽게 풀어보려고 했더니 또또 시간초과나고 난리남.. 흠 이유는 모르겠으나 intelliJ에서 돌리면 숫자 명령어에 대해서 출력이 바로 나오지 않는데 도대체 왜 맞은 건지 모르겠다며,, 무튼 문제 자체는 어렵지 않았으나 내일은 BufferedWriter를 진짜 마스터해야겠다고 느꼈다. 문제를 이해하지 못해서 못 푼 게 아니라 입출력에서 시간초과 뜨는 건 너무 하잖아~ [문제 풀이]1이 들어올 때만 약간 다른데 StringTokenizer 이용해서 한 줄에 들어오는 다음 숫자 가져다가 stack에 넣으면 되는 부분이라 크게 어려운 건 없었다. import java.io.*;import java.util.*;p..

https://www.acmicpc.net/problem/10773 [문제 이해]덱을 사용하는 것에 대한 이해만 있다면 풀 수 있는 어렵지 않은 문제였다. 0이 나오면 덱에 있던 원소를 삭제하면 되고, 0이 아니라면 저장하는 단순한 플로우로 문제를 해결했다. [문제 풀이]0인 경우, 덱에 아예 저장하지 않고 바로 덱에 있는 가장 마지막 값을 삭제하는 방식으로 구현하면 됐다. 스택을 사용하는 문제라고 생각하면 쉬운데 덱 라이브러리를 사용하면 풀 수 있어서 어렵지 않게 풀었던 것 같다. 합을 구할 때는 덱에 있는 원소를 모두 poll()로 없애면서 반환하도록 구현하였다. import java.io.*;import java.util.*;public class Main { public static void..

https://www.acmicpc.net/problem/2346 [문제 이해]요세푸스랑 비슷해서 금방 풀 줄 알았는데 티어가 차이나는 이유가 있었구나,, 일단 인덱스 값을 저장해서 이를 출력해야되는 것이 가장 큰 차이점이었고, -(마이너스)값이 있기 때문에 값을 어떻게 배치해야하는가도 중요하게 생각해봐야할 부분 중 하나였다. [문제 풀이]값이 양수면 원래 값-1만큼 반복하면서 앞에서 원소를 빼고 뒤에 삽입하면 됐었고, 값이 음수면 원래 값만큼 반복하면서 뒤에서 앞으로 값을 삽입하면 되는 문제였다.처음에는 LinkedList로 선언해서 메모리 초과 파티를 겪은 이후, 이를 수정했더니 이번에는 NullPointer 오류가 났다. 간단한 예제 (123)으로 테스트 해보니 마지막 값일 경우, NullPoint..

https://www.acmicpc.net/problem/10866  [문제 이해]덱을 얼마나 잘 이해하고 있는가에 대한 문제였다.. -> 당연히 금방 풀 줄 알았는데 덱을 제대로 이해 못하고 있었나봄 ㅎㅎ;; [문제 풀이]단순히 equals로 문자 비교해서 관련된 내용 구현하면 된다고 생각하고 풀었는데... 시간 초과~..아무튼 해보니까 get 대신 peek을 쓰는 것이 값을 조회할 때 시간이 덜 걸리는 것 같고,, add보단 offer을 사용하는 것이 시간이 덜 걸리는 것 같다. 그리고 equals로 다 검사해도 괜찮긴 하지만 switch문을 사용해서 구현해보는 방식으로 문제를 풀어봤다.마지막으로 BufferedWriter 초기화하는 거 때문에도 계속 틀렸었는데 flush랑 close는 for문 밖에..