알고리즘
[Java 백준 16637] 괄호 추가하기
풀이 괄호가 중복된 것을 허용하지 않고, 연산자 우선순위가 동일하므로 왼쪽부터 계산하는 문제입니다. 연산자와 숫자를 나누어 담고 dfs를 활용해서, 케이스를 인덱스 기반으로 1. 괄호를 안친것으로 계산 과정 2. 괄호를 친것으로 계산 과정 두가지로 나누어서 진행했습니다. 첫번째 경우는 index, index + 1 를 연산과정을 하고 다음 dfs 두번째 경우는 index + 1, index +2를 먼저 연산하고, 지금까지 계산한 것과 다시 또 연산하고 다다음 dfs import java.io.*; import java.util.*; public class Main { static int N, max=Integer.MIN_VALUE; static ArrayList number = new ArrayList(..
[Java/자바 백준 17281] 공
풀이 순열 + 구현 문제인거같다. 순열 과정에서 4번째 타자가 1번 선수라는걸 인지하고 백트래킹 시켜줘야하는 문제 ! 안시켜주면 시간초과난다... 타자들 순서를 나열하고, 순서대로 게임을 진행하면 되는 문제 처음에 점수 계산 중 1루, 2루, 3루 배열에 넣어서 계산했는데 (이렇게 풀어도 시간 초과 안난다) 다른 답안 참고 중 해당 이닝에서 뒤에서부터 다른 합을 구해 4를 넘게 되면 앞에있는 타자들은 모두 득점으로 계산가능하단걸 보고 참고했다. import java.io.*; import java.util.*; public class Main { static int N, max, temp; static boolean[] isSelected; static int[][] order; static int[] ..
[Java/자바 백준 9466] 텀 프로젝트
풀이 학생이 10만명이므로 O(n^2)으로 풀게되면 시간초과가 나는 문제입니다. 백준 게시판 들어가서 보면 사람들이 엄청나게 고뇌(?)하면서 질문이 엄청 많아요 ! 저도 엄청나게 고뇌하다고 시간 초과를 해결하지 못했습니다 ㅜㅜ 참고한 예시를 보면서 설명드릴게요 ! 문제의 포인트는 모든 노드는 다른 노드를 가리킨다 입니다. 즉, DFS를 돌다보면 무조건 싸이클이 생기게 됩니다. ex) 3-2-4-5-6-7-3 1부터 dfs 시작하면 1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 3 2 - > 2 3 -> 4 -> 5 -> 6 -> 7 -> 3 4 -> 5 -> 6 -> 7 -> 3 5 -> 6 -> 7 -> 3 6 -> 7 -> 3 7 -> 3 3,4,5,6,7은 사이클 내에서 반복하는 것을 알 수..
[Java/자바 백준 10655] 마라톤 1
풀이 실버 3 문제이지만 체감상 좀 더 어려워서 풀이를 남겨봅니당 ! 처음 이중 포문으로 브루트포스로 아주 간단히 풀려다가 시간 초과가 났습니다. 이후 어떤식으로 풀 수 있을까 생각하다가 모든 체크 포인트를 방문한 값을 distance에 넣어주고 체크포인트 한 개를 건너뛰게 되면 줄어드는 거리를 비교해주었습니다. 예를 들어 현재 위치를 i로 예시를 들면 원래라면 i-1, i, i+1값이 있지만 i값을 점프하게되면 i-1, i+1의 위치로 가게 됩니다. 이 거리 값을 original과 jump 변수에 각각 넣어주어 최소값을 비교했습니다. import java.io.*; import java.util.*; public class Main { static int N; static int[][] checkPoi..
[Java/자바 백준 17825] 주사위 윷놀이
풀이 문제를 보고 어떻게 풀어야 할지 감이 안왔다. https://pangtrue.tistory.com/285 이 분의 풀이를 보면서 해석하면서 문제를 풀었다. 첫 번째, 말의 순서에 대해서 어떻게 정해줘야하나 했었는데, 주사위 순서가 정해져있으니 order 라는 배열을 만들고 0~3 말의 인덱스를 넣어 순열로 해결하였다. 두 번째, 윷놀이 판에 대해서 어떻게 구현해야할까... 주어진 윷놀이판을 1차원으로 표현하게 되면 위의 1차원 구조에서 포인트는 10, 20, 30은 두 가지 방향을 가진다는 것이다. 그럼 노드가 가져야할 정보는 다음과 같다. 해당 칸의 점수, 해당 칸이 비었는지(다른 말이 있는지), 지름길(파란 방향)이 있는지, 도착점인지 addNext는 다음 하나의 노드를 새로 만들어 해당 점수를..
[Java/자바 백준 17822] 원판 돌리기
풀이 문제를 보면 원판이 있고, 문제도 길어서 어려워 보이지만, 사실 간단한 문제이다. 초기 값을 map에 입력 받고 1. 시계, 반시계 방향으로 몇 번 돌릴지 2. 인접한 숫자 중 같은 값이 있어주면 0으로 만들어주기 3. 인접한 숫자 중 같은 값이 없으면 평균 값을 구해 평균 값보다 크면 +1, 작으면 -1 해주는 문제 시계, 반시계는 forwardLotate(), reverseLotate()로 index를 하나씩 밀어주거나 땡겨주었다. findEqualPoint()에서 bfs를 사용했는데, y값에 해당하는 값이 0 or M 값이 일때 조건을 줘 값을 바꿔주었다. 왜냐하면 원 형태이므로 순환하기 때문이다. 같은 값이 있으면 처리해서 point에 더해주었고 더한 point값 들을 total에서 빼주었다..
[Java/자바 백준 17135] 캐슬 디펜스
풀이 주요 로직을 설명하자면 1. combination()을 사용하여 궁수들의 위치를 정해주었다. 2. copyMap()으로 맵의 적들의 위치를 깊은 복사를 해주었다. 3. game()을 진행 3-1. killNearEnemy() 가장 가까운 적, 여러 명이라면 가장 왼쪽의 적을 죽인다. 3-2. forwardEnemy() 한 칸씩 전진. 그나마 구현하기 까다로운 부분은 killNearEnemy() 이 부분이였습니다. 다른 위치에 궁수가 같은 적을 죽일 수도 있기 때문에 적을 죽이는 위치를 큐로 담고, 후에 처리를 하는 순으로 진행했습니다. 추가적으로 반례를 참고 하고싶으면 https://www.acmicpc.net/board/view/73578 가시는 걸 추천합니다 !! import java.util...
[Java/자바 백준 1347] 미로 만들기
풀이 실버 4 문제지만, 그것보다는 조금 더 어려운 문제인거 같다. 처음 문제를 봤을 때 맵의 크기를 어떻게 정해주지 10분 정도 고민하다가 최대 맵 크기를 한정해주고, 명령에 따라서 도달한 전진한 위치는 1로 바꿔주었다. x,y값들의 최대 최소 값을 구해서 범위 안에 1인 값은 "." , 0인 값은 "#"으로 StringBuilder에 넣어주었다. import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { // 북 동 남 서 static int[] dx = {-1,0,1,0}; static int[] dy = {0,1,0,-1}; public static void main(String[] args) throws..
[Java/자바 백준 17837] 새로운 게임 2
풀이 2차원 스택을 활용해서 문제를 풀었습니다. 구현 난이도는 엄청 어렵지 않지만 테케 4번이 계속 틀려서 뭐가 문제지 하면서 봤는데 원인은 파란색 칸 일때 !! 문제를 보면 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다. 라고 나와있는데, 제가 고려하지 않은 것은 방향을 바꾸고 진행한 nx, ny칸이 흰색 or 빨간색 칸일 수도 있는 상황을 고려하지 않았네요 ! 그거 수정하니까 정답이 되었습니다 ! 흰색 칸일때는 쌓여있는 말들을 모두 임시 스택에 넣어주고, nx, ny에 다시 넣어줬습니다. 빨간 칸 일때는 스택을 하나 더 써서, 뒤집어서 넣어줬습니다. import java.io.*; impo..
[Java/자바 프로그래머스] 방문길이
풀이 방법은 hashmap이나 set써도 될거같지만, 4차원 배열은 사용했습니다. x, y, nx, ny를 방문처리하고 nx, ny, x, y 또한 양방향 방문처리를 했습니다. class Solution { public int solution(String dirs) { int answer = 0; int x = 5; int y = 5; int[][][][] map = new int[11][11][11][11]; int[] dx = {1, -1, 0, 0}; int[] dy = {0, 0, 1, -1}; for(int i = 0 ; i < dirs.length(); i++){ char tmp = dirs.charAt(i); int dir = -1; if(tmp == 'U'){ dir = 0; } else ..