본문 바로가기

전체 글1099

[자바] 프로그래머스 - 프린터 (programmers java) 문제 : programmers-프린터 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 문제에서 제시된 대로 시뮬레이션을 돌려주면 된다. 이 때 서브 문제로 문제를 나눠서 생각해보자. 1. 대기목록의 앞에서 꺼내고, 뒤에 다시 넣을 수 있는 자료구조를 선택해야 한다. 2. 현재 꺼내지 않은 대기목록에서 중요도가 가장 높은 값을 알 수 있어야 한다. 3. location으로 지정된 문서의 위치를 항상 알 수 있어야 한다. 위의 3가지를 모두 할 수 있다면 이 문제를 풀 수 있다. 그럼 각각 어떻게 해야할지 생각해보자. 1. 대기목록의 앞에서 꺼내고, 뒤에 다시 넣을 수 있는 자료구조를 선택해야 한다. 사실 이걸 만족하는 자료구조는 엄청.. 2022. 5. 4.
[자바] 백준 1388 - 바닥 장식 (boj java) 문제 : boj1388 문제에 제시된대로 구현을 하면 된다. 좀 더 편하게 하려면 어차피 n, m이 수치가 매우 낮으므로 가로와 세로를 따로 세면 편하다. 가로로 세면서 '|' 을 만나면 세던걸 초기화 하는 식으로, 세로로 세면서 '-'을 만나면 세던걸 초기화 하는 식으로 진행하면 좀 더 로직을 세우기 편하다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputS.. 2022. 5. 4.
[자바] 백준 2246 - 콘도 선정 (boj java) 문제 : boj2246 각 N개에 대해 모든 N-1개의 다른 지점들을 전부 확인해봐도 O(N^2)으로 시간 제한인 2초 내에 가능하다. 따라서 모든 경우를 봐주면 된다. 문제에 제시된 조건을 if문으로 잘 표현만 할 수 있다면 어렵지 않게 풀 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { class Condo { int d, c; public Condo(int d, int c) { this.d = d; this.c = c; } } private void solution() throws Exception { B.. 2022. 5. 3.
[자바] 백준 11576 - Base Conversion (boj java) 문제 : boj1576 우선 A진법의 수를 10진법으로 만들고, 10진법을 B진법으로 만들면 된다. A에서 10진법을 만드는것은 예를들어 각 자리수가 ..., c2, c1, c0 이고 현재 a진법의 수라면 ... + c2*a^2 + c1*a^1 + c0*a^0 을 해주면 된다. 그럼 그렇게 만들어진 10진법 수를 나누기와 나머지연산을 사용해 B진법으로 만들어주면 되긴한데, 자바의 경우 Integer.toString에서 해당 기능을 지원해주므로 그렇게 처리했다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private.. 2022. 5. 2.
[자바] 프로그래머스 - 신고 결과 받기 (programmers java) 문제 : programmers-신고결과받기 프로그래머스 기준 레벨 1은 에바같고.. 레벨 2정도는 될 것 같다. 백준기준 한 실버5~3정도 수준인듯. 결국 서브 문제로 '잘' 나누고 적절한 자료구조를 '잘' 쓰면 된다. 사실 엄밀히 따지자면 기본적인 자료구조들을 다 알고있다는 가정하에 그냥 제시된대로 단순 구현만 하면 되는 문제니 레벨 1이 맞는것 같기도 하다. 아무튼 내 경우엔 다음의 단계로 나누어서 풀었다. 1. 문자열을 숫자로 매칭 (안해도 되지만, 효율성을 높히려면 하면 좋다) - HashMap 사용 2. 신고당한 횟수를 센다 - int[] 사용 / 이 때 중복되는 신고는 걸러줘야 한다 - HashSet[] 사용 / 이 때 자신을 신고한 사람의 리스트를 유지한다 - ArrayList[] 사용 3... 2022. 5. 1.
[자바] 백준 22935 - 이진 딸기 (boj java) 문제 : boj22935 우선 이 문제를 풀기 위해 알아야 하는 2가지 정보를 확인해보자. A. 1부터 15까지 출력해야 하는 문자열 미리 전처리로 만들어두면 된다! 이하 코드에서 init()이 이 역할을 한다. 비트연산을 사용해 문제에서 제시된 대로 문자열을 만들어주면 된다. 1부터 15까지를 전부 만들어보면 다음과 같다. B. 이제 입력으로 들어온 N이 'A' 중 뭐에 해당하는지를 확인하면 된다. 이건 나머지 연산을 사용해서 쉽게 구할 수 있다. 아래 코드를 참고해보자. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { String[] arr; private void init().. 2022. 5. 1.
[자바] 백준 8244 - Tales of seafaring (boj java) 문제 : boj8244 자바로는 정신건강상 시도 안하는걸 추천한다. 자바론 사실상 통과 불가능한 메모리 제한이라 메모리 초과를 뚫기 위해 이상한 짓들을 많이 해야 한다. 1. 키 아이디어 기본 아이디어는 어찌보면 생각하기 어렵고 어찌보면 간단한데 다음의 그래프를 보자. 이 때 k개로 주어진 각각의 'tales that Bytensson has heard'중 하나를 Q라고 칭하겠다. 이 때 1에서 출발해서 2로 가는 최단길이는 1이다. 그럼 Q가 '1 2 1'이라면 당연히 가능하다. 그럼 '1 2 3'이나 '1 2 5'라도 가능할까? 이것도 가능하다. 왜냐면 한 번 들렸던 곳을 다시 못간다는 제한이 없으므로 다음과 같이 왔다갔다 하면 되기 때문이다. 최단거리는 1이지만, 그 이후로 1+2*n (n은 0부터.. 2022. 4. 30.
[자바] 백준 13222 - Matches (boj java) 문제 : boj13222 결국 sqrt(w^2*h^2) 보다 입력으로 들어온 값이 작거나 같다면 YES, 아니면 NO이다. 이 때 실제로 sqrt를 하게 되면 오차가 있을 수 있으므로 N개의 입력값 중 현재 보고 있는 값을 cur이라 하면, 양변을 제곱해서 w^2*h^2 >= cur^2 을 체크해주면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStr.. 2022. 4. 29.
[자바] 백준 1241 - 머리 톡톡 (boj java) 문제 : boj1241 에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유(글 링크) 이 글을 이해했다면 쉽게 풀 수 있다. N개를 입력받으면서 HashMap 등으로 각 숫자의 존재 여부 및 몇 개 존재하는지 저장해둔다. 이후 N개를 순회하면서 각각을 A라고 하면, 1부터 sqrt(A) 사이에 존재하는 A의 약수가 B라 하자. 그럼 HashMap에서 B의 개수를 더해주고, A/B도 약수일 것이므로 그것도 HashMap에서 찾아 더해주면 된다. 이 때 주의점은 sqrt(A)로 A가 나누어 떨어질 경우 (즉, (int)sqrt(A) * (int)sqrt(A) == A 인 경우), 두 번 더해지게 되므로 한 번은 빼줘야 한다. 그럼 시간복잡도는 N명 중 가장 큰 숫자가 K라 할 때, O(N.. 2022. 4. 28.
[자바] 백준 19622 - 회의실 배정 3 (boj java) 문제 : boj19622 문제 읽으면서 와.. 이거 N이 25 이하 정도가 아니라면 힘들꺼같은데 이걸 어떻게 하지 생각하면서 읽어내려오니 역시나 '임의의 회의 K(1≤ K ≤ N)는 회의 K − 1과 회의 K + 1과는 회의 시간이 겹치고 다른 회의들과는 회의 시간이 겹치지 않는다.' 이런 조건이 있었다. 그럼 그냥 dp로 쉽게 해결 가능하다. 결국 자신의 이전과 이후와 겹칠 수 없으므로, 방향을 입력이 주어지는 순서로 제한해보자면 결국 현재 회의를 개최하지 않는다면 이전 회의가 개최했던, 안했던 상관이 없다. 그리고 현재 회의를 개최하려면 이전 회의가 개최되지 않았어야 한다. dp 배열을 다음과 같이 정의하자. dp[i][0] -> i번째 회의를 개최하지 않을 경우 i번 회의까지의 최대 인원 dp[i].. 2022. 4. 28.

티스토리툴바