본문 바로가기

Algorithm43

[백준] BOJ 15686 치킨 배달(JAVA/시간초과 해결) 모든 경우의 수를 확인해 보는 문제이다. 해당 조건을 보며 치킨 집 중에서 M개에 대해 나올 수 있는 경우의 수를 전부 확인하여, 도시의 치킨 거리를 구해야겠다고 생각했다. 처음에는 방문체크 여부를 확인하여 해당 치킨 집을 방문하지 않았다면 방문하는 식으로 진행했다. /* * M개의 치킨집을 선택할 수 있는 경우의 수를 전부 구함 * */ static void choice(int cnt, int[] output, boolean[] visited, int now) { //M개의 치킨 집 전부 구함 if (cnt >= M) { getDistance(output); return; } //다음 치킨 집 선택 for (int i = now; i < chickenList.size(); i++) { if (!visi.. 2023. 6. 12.
[백준] BOJ 1759 암호 만들기(자바/메모리 초과 해결) 엄청 어려운 문제는 아니었으나, 메모리 초과 났던 문제이다. 문제 풀이 가능성 있는 암호들을 모두 구해야 하므로 조합을 통해 모든 경우의 수를 확인해야겠다고 생각했다. 따라서, 조합을 통해 나올 수 있는 문자열 조합을 구한 다음 해당 문자열이 최소 모음 1개, 자음 2개를 포함하는지를 확인했다. 하지만, 다음과 같이 메모리 초과가 발생했다.. 이유를 모르겠어서 다른 블로그에서 아이디어를 참고했고, 이번에는 통과할 수 있었다. 내가 메모리 초과를 해결할 수 있었던 방법은 다음과 같다. 우선 나는 조합을 만들때, for문에서 0번 인덱스부터 시작해서 방문체크를 확인하면서 문제를 풀었다. 다음과 같이 말이다. for (int i = 0; i < C; i++) { if(!visited[i]){ visited[i.. 2023. 6. 7.
[백준] BOJ 1254 팰린드롬 만들기(자바) 문제 풀이 문제에서 주어진 예제 입력 3번을 예시로 들어보자 해당 예시를 토대로 문자를 붙여보면 다음과 같다. qwertytrewq 해당 예시를 토대로 팰린드롬을 만들기 위해서는 qwert를 그대로 뒤집어서 trewq를 붙이면 된다. 그래서 나는 0~i 번째 행까지의 문자열을 붙여보았다. 이때, 문자열을 뒤집어서 붙여야 해서 reverse() 함수를 사용했다. for문을 돌면 다음과 같이 출력된다. qwerty qwertyq qwertywq qwertyewq qwertyrewq qwertytrewq ( 팰린드롬 완성) 문제를 풀며 어려웠던 점 문제 쉽다고 생각했는데, 문자열을 그대로 뒤집어서 붙여보면 됐는데, 그 부분을 생각못한 문제 문자열을 뒤집어서 안붙이고 그대로 붙여서 테케를 전부 맞지 못했던 문제.. 2023. 6. 1.
[백준] BOJ 2531 회전 초밥(자바) 문제 풀이 문제를 잘 못 이해해서 오래 걸렸던 문제였다. 문제에 'k개의 접시를 연속해서 먹을 경우' 라는 조건이 주어진다. 나는 이 조건에 대해 k개의 다른 종류를 먹어야 한다고 생각했다. 하지만, k개의 연속된 초밥을 먹는다라고 해석해야 한다. 또한, 주의해야 할 점이 회전 초밥은 원형이니까 배열 마지막 인덱스부터 다시 시작 인덱스 0 ~ k-1까지의 조합도 생각해야 한다. 예제 입력 1번을 예시로 설명해 보겠습니다. 25가 배열의 끝입니다. 그런데, 여기서 (25, 7, 9, 7)의 조합도 생각해야 합니다. 따라서, 다음과 같이 저는 배열의 끝에 k-1만큼 붙였습니다. 그러면 마지막 조합 ( 25, 7, 9, 7)에 대해서도 구해볼 수 있습니다. 구현 public class Main_2531 { s.. 2023. 5. 23.

티스토리툴바