은비블로그

[백준] 2230 : 수 고르기 (JAVA)

https://www.acmicpc.net/problem/2230 [풀이과정]처음 코드는 완전탐색으로 O(N^2)여서 시간초과가 났다.투포인터를 사용해서 풀었는데, 먼저 배열을 정렬한 후 계산을 하는 방식이다.정렬된 상태에서 두 수의 차이를 구하면 이후의 차이가 현재 차이보다 크단 걸 알 수 있으니 넘겨서 더 큰 수끼리 비교하면 된다.배열 정렬 O(N logN) + 투포인터 탐색 O(N)으로 전체 시간복잡도는 O(N logN)임. 이분탐색으로도 풀 수 있고 이분탐색 풀이도 O(N logN)이다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;..

[백준] 1700 : 멀티탭 스케줄링 (JAVA)

https://www.acmicpc.net/problem/1700 [풀이과정]1. 멀티탭의 공간이 남아있을 때 2. 멀티탭의 공간이 남아있지 않을 때•  뒷 순서의 기기 중 현재 사용 중인 기기 저장하기 (willUse)2-2. willUse가 N의 크기와 다르면 == 현재 사용 중인 것 중 나중에 사용되는 게 없다는 뜻• willUSe에 없는 기기 삭제하기2-3. willUSe가 N의 크기와 같으면 == 현재 사용 중인 것 모두 나중에 사용된다는 뜻.• "그리디 알고리즘" 으로 제일 마지막 (willUse에 가장 마지막에 추가된) 순서의 기기를 뺌 [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream..

[백준] 1202 : 보석도둑 (JAVA)

https://www.acmicpc.net/problem/1202 [풀이과정]가방에 들어가는 보석 중 가장 비싼 걸 넣으면 된다.탐색시간을 줄이는 게 가장 중요해보였다. 그리고 최대값이 30억이었기 때문에 long 타입 사용해줬다.먼저 우선순위 큐로 보석, 가방, 가방에 들어가는 보석까 세 개를 정렬해서 사용했다. [시간 복잡도]PriorityQueue의 add, poll의 시간 복잡도는 O(log⁡ n), peek는 O(1) O(N logN) : 보석 정렬O(K log⁡K) : 가방 정렬O(K⋅log⁡N) : 각 가방에 대해 보석을 추가하고 가장 비싼 보석을 꺼내는 과정  [코드]import java.io.BufferedReader;import java.io.IOException;import java...

https://www.acmicpc.net/problem/24230 [풀이과정]N의 크기가 20만이었기 때문에 시간 복잡도가 N^2이 되면 시간초과가 일어난다.복잡도를 줄이려고 처음엔 값 변경을 하지 않고 부모와 색이 다른지 안 다른지 확인하는 방법을 생각하려 했는데,그냥 부모랑 색이 다르면 색칠 횟수 +1 해주면 되는 문제였다. 그럼 복잡도가 O(N)임.그리고 문제 예시가 순차적이었어서 무방향 그래프인 걸 놓쳤다. 그래서 엄청 헤맸다.이 부분은 잘 숙지해서 다음엔 놓치지 않기. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import..

https://www.acmicpc.net/problem/15961 [풀이과정]회전초밥이기 때문에 마지막에 다시 처음 부분의 초밥을 먹는다는 걸 고려하지 못 해서 한 번 틀렸다.마지막에 처음 부분의 초밥을 먹을 때1. 인덱스를 계산해서 먹기sushi[(n + K - 1) % N]2. K개만큼의 처음부분 초밥을 배열 뒤에 이어붙이기sushi[N + K] 둘의 성능차이는 없었지만 변수 크기가 커진다면 1번 방식이 성능이 더 좋을 것이다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*1. 한 위치부터 k개의 접시를 연속해서 먹..

https://www.acmicpc.net/problem/15686 [풀이과정]선택된 M개의 치킨집으로 치킨 거리를 구해야 하는 거니까 M개를 골랐는데 시간초과가 났다.for문에서 시작 인덱스를 i + 1로 해야 기존 탐색했던 부분을 건너뛰니까 불필요한 탐색시간을 줄일 수 있는데, start+1로 하는 실수를 했다. 변수 때문에 논리오류가 생기면 찾기 힘들어지니까 항상 한 번 더 생각하자.[코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import j..

https://www.acmicpc.net/problem/5430 [풀이과정]처음엔 D가 나올 때까지 R의 개수를 세서, %2값이 1일 때만 뒤집는 연산을 수행했다. 당연히 시간초과가 났다.그냥 뒤집은 상태라고 하면 뒤에서부터 출력하면 되는 문제였다.Deque을 사용했고 뒤집은 상태인지 아닌지 구분해줄 변수를 사용했다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;/*R - 순서를 뒤집는 함수D - 첫 번째 수를 버리는 함수, 배열이 비어있을 때 사용되면 에러함수를 조합하여 한 번에 사용최종 결과 구하기 */public class Main { ..

https://www.acmicpc.net/problem/2206[풀이과정]처음엔 DFS로 풀었는데, 값이 너무 커서 BFS로 풀었다.3차원 배열을 사용해서 해당 위치에 벽을 부수고 도착했을 때와 벽을 부수고 도착하지 않았을 때를 나누어서 탐색했다. [BFS 코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;/*N*M 맵. 0은 이동 가능 한 곳, 1은 이동할 수 없는 벽이 있는 곳(1,1)에서 (N,M)의 위치까지 최단 경로로 이동.시작하는..

https://www.acmicpc.net/problem/1062 [풀이과정]입력된 알파벳들 중 배운 개수만큼 뽑아내서 읽을 수 있는 단어를 찾아야 했는데, 이걸 어떻게 뽑아낼지 고민했다.알파벳을 순서대로 index로 가지는 배열을 사용하면 된다. 아스키 코드를 사용하면 됐는데 이걸 생각 못 해서 많이 헤맸다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashMap;import java.util.HashSet;import java.util.Set;import java.util.StringTokenizer;/*anta로 시작하고 tica로 끝나는 남극..

https://www.acmicpc.net/problem/17609[풀이과정]투포인터로 풀었다.양끝에서 문자열을 비교하며 회문 체크를 했고 만약 문자열이 다르면 왼쪽 문자열 삭제하고 한 번, 오른쪽 문자열 삭제하고 한 번씩 회문 체크를 추가적으로 진행했다. 처음에 왼쪽 삭제 후 삭제한 문자열을 복구하지 않고 오른쪽도 진행하는 바람에 살짝 해맸다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;/*회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열인 유사회문회문인지 유사회문인지 일반 문자열인지를 판단해라 */public class Main { static Buffer..