티스토리

다람쥐의 개발 블로그

검색하기

블로그 홈

다람쥐의 개발 블로그

daramgda.tistory.com/m

dotori Java

구독자: 11

방명록 방문하기

주요 글 목록

자바 백준 10816번 문제 : 숫자 카드 2 문제 출처 : https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 : 풀이 : 소스코드 : import java.util.*; import java.io.*; class Main { public StringBuilder solution(int n, int[] nArr, int m, int[] mArr) { StringBuilder sb = new StringBuilder(); // nArr가 오름차순 정렬된 .. 공감수 0 댓글수 0 2023. 1. 19.
자바 백준 1920번 문제 : 수 찾기 문제 출처 : 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 문제 : 풀이 : 이분 탐색을 이용하면 해결될 문제지만 왠지 투포인터 알고리즘을 사용해 풀어보고 싶었다. 투포인터 알고리즘을 사용하기 위해선 mArr와 nArr 둘 다 정렬되어 있어야 하는데 문제는 mArr를 정렬시켜버리면 기존 인덱스(위치)도 섞여서 출력 시 1이 출력되는 위치도 변한다는 것이다. 그럼 HashMap을 사용해 기존 인.. 공감수 0 댓글수 0 2023. 1. 17.
자바 백준 10986번 문제 : 나머지 합 문제 출처 : https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 문제 : 풀이 : 누적 합을 저장한 배열을 생성하고 이용한다. s[i] % m == 0 인 경우, 인덱스 1부터 i까지의 누적 합이 m으로 나누어 떨어진다는 것이다. 인덱스 i부터 j까지의 구간 합은 s[j] - s[i-1] 이다. 구간 합이 m으로 떨어지는 경우를 구해야 한다. ( s[j] - s[i-1] ) % m = 0 해당 식을.. 공감수 0 댓글수 0 2023. 1. 11.
자바 백준 1990번 문제 : 소수인팰린드롬 제목 // 자바 백준 0번 문제 : 문제명 문제 출처 : https://www.acmicpc.net/problem/1990 1990번: 소수인팰린드롬 151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되 www.acmicpc.net 문제 : 풀이 : 에라토스테네스 체 이용해 소수 판별한 다음 팰린드롬인지 아닌지 판별해 출력한다. 소스코드 : import java.util.*; class Main { public boolean plndr(int n) { // 팰린드롬 판별 함수 String str = Integer.toString(n); String reve.. 공감수 0 댓글수 0 2023. 1. 10.
자바 백준 17609번 문제 : 회문 문제 출처 : https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 : 풀이 : 회문인지 아닌지는 StringBuilder로 reverse()해서 확인하는 함수를 작성해둠 먼저 회문인지 아닌지 검사, 회문일 경우 바로 0 출력한다. 회문이 아닐 경우 유사회문인지, 둘 모두 해당되지 않는지 검사해야 하므로 투포인터를 왼쪽(lt) 오른쪽(rt)에 잡고 한칸씩 중앙으로 이동시키다 두 문자가 다른 경우 lt를 삭제한 문자열, rt를 삭제한 문자열을 각각 회문인지 아닌지 검사하는 함.. 공감수 0 댓글수 0 2022. 12. 28.
자바 백준 1991번 문제 : 트리 순회 문제 출처 : https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 : 소스코드 : import java.util.*; import java.io.*; class Node { char value; Node lt, rt; Node(char value, Node lt, Node rt) { this.value = value; this.lt = lt; this.rt = rt; } } public class Main { Node root; p.. 공감수 0 댓글수 0 2022. 11. 14.
자바 백준 17298번 문제 : 오큰수 문제 출처 : 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 문제 : 풀이 : 세 가지 풀이 방식을 생각해서 풀었고, 첫 번째와 두 번째는 보기 좋게 틀렸다. 왜 틀렸는지 코드와 함께 정리해보고, 이후 정답 코드도 정리해보자 오답 코드 (시간 초과) : import java.util.*; import java.io.*; public class Main { public StringBuilder solution(int n, int[] arr) { Strin.. 공감수 0 댓글수 0 2022. 11. 11.
자바 백준 9935번 문제 : 문자열 폭발 문제 출처 : https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 : 풀이 : 스택과 StringBuilder를 이용해 문제를 해결하였다. 소스코드 : import java.util.*; import java.io.*; public class Main { public StringBuilder solution(String str, String boom) { StringBuilder sb = new StringBuilder(); S.. 공감수 0 댓글수 0 2022. 11. 10.
자바 백준 2470번 문제 : 두 용액 문제 출처 : https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 : 풀이 : 항상 그렇듯이 억지로 풀 수는 있다. for문으로 돌리면 0에 가장 가까운 값 찾을 수 있다. 시간초과가 날뿐.. 투포인터를 잡으면 된다. 잡아도 되나? 어떻게 O(N)으로 0에 가장 가까운 두 값만을 서치할 수 있지? 일단 Arrays.sort(arr) 해주고 투포인터의 국룰(?) lt와 rt를 양 끝으로 잡아본다. 쓸모없는 움직.. 공감수 0 댓글수 0 2022. 11. 8.
자바 백준 5430번 문제 : AC 문제 출처 : https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 : 풀이 : 직접 뒤집는 것 보다 Deque를 이용해 Reverse 유무를 체크하며 앞과 뒤에서 삭제하는 것이 좋다. 소스코드 : import java.util.*; import java.io.*; public class Main { public StringBuilder solution(String funcArr, int arrSize, Deque dq) { StringBuilder sb = new StringBuilder(); bo.. 공감수 0 댓글수 0 2022. 11. 7.
자바 백준 18870번 문제 : 좌표 압축 문제 출처 : https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 : 풀이 : 입력받은 원래 값들의 배열을 그대로 저장하는 arr 배열, 오름차순으로 정렬할 sortArr 배열을 만들고 두 배열에 입력받는 좌표를 저장한다. 이후 sortArr 배열을 오름차순 정렬하고, 압축 전의 값과 압축 후의 값을 각각 key와 value로 저장하는 HashMap을 생성한다. 그리고 arr 배열에서 for문.. 공감수 0 댓글수 0 2022. 11. 7.
자바 백준 2110번 문제 : 공유기 설치 문제 출처 : https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 : 풀이 : Parametric Search 알고리즘 통해 간단하게 문제를 해결할 수 있다. 우선 Arrays.sort(arr) 하면 1 2 4 8 9 lt = 1 , rt = 9(arr에서 최대값) , mid = 5 mid = 5로 잡은 것은 가장 가까운 두 공유기 최대 거리가 5라고 가정하고 넣어보는 것이다. 따라서 cou.. 공감수 0 댓글수 0 2022. 11. 5.
자바/C++ 백준 2805번 문제 : 나무 자르기 문제 출처 : https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 : 풀이 : Parametric Search 알고리즘으로 간단히 해결되는 문제인데 왜 정답률이 25% 밖에 안되는걸까 생각하며 문제를 제출하였지만 틀려버렸다. 문제를 다시보니 자료형의 범위를 초과해서 발생한 문제였다. 자료형의 범위를 잘 생각하자는 교훈을 얻게 되었다. 자바 소스코드 : import java.util.*; public cl.. 공감수 0 댓글수 1 2022. 11. 4.
자바 백준 1874번 문제 - 스택 수열 문제 출처 : https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 : 풀이 : 1부터 n까지의 수를 스택에 넣었다가 뽑으면, 즉 stack.push()되고 stack.pop()되면 수열로 들어간다는 것이다. 1부터 n까지의 수를 push()와 pop() 해서 입력된 수열로 만드는 것이니 우선 입력된 수열을 int[] arr로 저장하고 n와 arr 배열을 solu.. 공감수 0 댓글수 0 2022. 11. 3.
자바 백준 7795번 문제 - 먹을 것인가 먹힐 것인가 문제 출처 : https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 문제 : 풀이 : T만큼 반복하는 반복문 안에서 N, M과 각 배열 입력받는다. 그리고 각 케이스마다 정답 리턴하는 함수 작성하고 사용한다. arrA, arrB 정렬한 다음 arrA 기준으로 for문 돌리고 그 안에서 이분 탐색 알고리즘 이용해 arrA[i]보다 작은 arrB 개수들 계산해서 구하고자 하는 값 리턴시킨다. 소스코드 .. 공감수 0 댓글수 0 2022. 11. 3.
자바 백준 10828, 10845, 10866번 문제 - 스택, 큐, 덱 문제 출처 : https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 출처2 : https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 출처3 : htt.. 공감수 0 댓글수 0 2022. 10. 21.
자바 백준 1181번 문제 - 단어정렬 문제 출처 : https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 ) 객체 간 비교를 가능하게 해주는 Comparable 인터페이스 이용해서 비교해주면 된다. 여기선 사전식 오름차순 정렬이라 Comparable 인터페이스를 사용했지만, String 사전 역순이였을 경우에는 Comparable이 아니라 Comparator를 사용하는 것이 좋을 것이다. 소스코드 ) import java.util.*; class Words impleme.. 공감수 3 댓글수 0 2022. 10. 21.
자바 백준 2108번 문제 - 통계학 문제 출처 : https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 풀이 ) 내 블로그 카테고리에 시간복잡도 O(N)을 가진 정렬 풀이법이 있다. 바로 생각났다. 수의 크기보다 N이 크다.거기다가 구해야하는 문제들을 보니 카운팅 정렬 알고리즘으로 풀면 괜찮을 것 같다. import java.util.*; import java.io.*; class Main { // 1 2 4 4 6 -> 0 1 1 0 2 0 1 (cntArr[4] = 2) public String.. 공감수 2 댓글수 0 2022. 10. 20.
같은 정답 다른 무게 + 무서운 이야기 m n 이 첫 줄에 주어지면 m이상 n이하 소수 모두 출력하는 간단한 문제 소스코드1의 무게 (메모리, 시간) : 소스코드1 (Scanner 사용과 배열 이용한 출력) : import java.util.*; class Main { public ArrayList solution(int m, int n) { ArrayList answer = new ArrayList(); boolean prime[] = new boolean[n+1]; Arrays.fill(prime, true); prime[0] = prime[1] = false; for(int i=2; i*i 공감수 0 댓글수 0 2022. 8. 16.
자바 백준 16472번 문제 - 고냥이 문제출처 : https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 문제 : 소스코드 : import java.util.*; class Main { // 투포인터 알고리즘 + 슬라이딩 윈도우 알고리즘 public int solution(int n, char[] arr) { int lt = 0, dif = 0; int answer = Integer.MIN_VALUE; // 해쉬맵 이용해 현재 인식중인 알파벳과 그 알파벳의 횟수 key와 value값으로 저장 Ha.. 공감수 0 댓글수 0 2022. 8. 11.
자바 백준 1016번 문제 - 제곱 ㄴㄴ 수 문제 출처 : https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 문제 : 소스코드 : import java.util.*; class Main { public int solution(long min, long max) { int answer = 0; // min부터 max까지의 배열을 생성한다. long len = (int)(max-min)+1; long arr[] = new long[(int)len]; // 에라토스테네스 체 알고.. 공감수 0 댓글수 0 2022. 8. 11.
자바 백준 1644번 문제 - 소수의 연속합 문제출처 : https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 : 소스코드 : import java.util.*; class Main { // 소수를 구해서 소수 배열을 만드는 함수 작성 // 에라토스테네스 체 알고리즘 적용 public ArrayList primeArr(int n) { ArrayList arr = new ArrayList(); boolean[] p = new boolean[n+1]; Arrays.fill(p, true); p[0] = p[1] = false; for(int i=2; i*i 공감수 0 댓글수 0 2022. 8. 11.
자바 백준 1806번 문제 - 부분합 문제출처 : https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 : 소스코드 : import java.util.*; class Main { // 투포인터 알고리즘 + 슬라이딩 윈도우 알고리즘 public int solution(int n, int s, int[] arr) { int lt = 0, sum = 0; int answer = Integer.MAX_VALUE; for(int rt=0; rt= s) { answer = Ma.. 공감수 0 댓글수 0 2022. 8. 2.
Java 백준 1747번 문제 - 소수&팰린드롬 https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 소스코드 : import java.util.*; class Main { public boolean reverseOk(int n) { String str = Integer.toString(n); String reverseStr = new StringBuilder(str).reverse().toString(); if (str.equals(reverseStr)) r.. 공감수 0 댓글수 0 2022. 8. 1.
백준 1032번 명령 프롬프트 / 자바 문자열 파트 출처 : https://www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net 소스 코드 import java.util.*; class Main { public String solution(String[] arr, int n) { String answer = ""; if (n == 1) return arr[0]; else { int strLen = arr[0].length(); for(int i=0; i 공감수 0 댓글수 0 2022. 7. 13.
백준 10808번 알파벳 개수 / 자바 문자열 파트 문제 출처 : https://www.acmicpc.net/problem/10808 10808번: 알파벳 개수 단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. www.acmicpc.net 각 알파벳을 나타내는 26개의 int 배열 작성 후 for문 돌려 알파벳의 문자의 아스키 코드 (소문자 a는 97부터 시작) 이용해 해당 알파벳이 나올 때 마다 해당하는 인덱스에 1씩 더하기 import java.util.*; class Main { public String solution(String str) { int[] count = new int[26]; for (int i=0; i 공감수 0 댓글수 0 2022. 7. 12.
백준 String(문자열) 문제풀이 백준 11719 그대로 출력하기 문제 : NULL이 입력(ctrl+z) 될 때 까지 입력받은 그대로 심지어 그냥 엔터나 공백까지도 그대로 출력하기 소스코드1 import java.util.*; import java.io.*; class Main { /* public StringBuilder solution(String str) { StringBuilder answer = new StringBuilder(""); return answer; } */ public static void main(String[] args) throws Exception { //Main T = new Main(); BufferedReader br = new BufferedReader(new InputStreamReader(Syst.. 공감수 0 댓글수 0 2022. 6. 1.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.