Java
-
[백준]1655: 가운데를 말해요 - JAVA문제풀이/백준 2021. 4. 27. 15:24
[백준]1655: 가운데를 말해요 www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 처음에는 우선순위큐를 사용해서 풀려다가 우선순위큐의 메소드 중에서는 인덱스로 접근할 수 있는 메소드가 없어 ArrayList로 접근하였다. list에 숫자를 입력받아 넣어주고 정렬 후에 2로나눈 인덱스 값을 출력하도록 하였더니 시간초과가 발생하였다. 다시 우선순위큐로 접근을 시도하였으나 마땅한 해결방법이 떠오르지 않았다. 다른 분들의 풀이를 확인하면서 정말..
-
[백준]4386: 별자리 만들기 - JAVA문제풀이/백준 2021. 4. 26. 19:04
[백준]4386: 별자리 만들기 www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 별들의 좌표를 간선으로 이었을때 최소인 비용을 찾는 문제로 MST알고리즘을 사용하여 풀면 된다. 별을 입력받을때 해당 별의 번호와 좌표를 저장해 주었다. 이 문제에서는 별들이 연결된 간선의 정보가 없으므로 모든 별들 사이의 거리를 직접 구하여 간선list에 저장해 주었다. 그다음 MST알고리즘인 prim, kruskal알고리즘을 사용하여 각각의 MST를 구해주면 된다. 코드 ..
-
[백준]2096: 내려가기 - JAVA문제풀이/백준 2021. 4. 26. 15:09
[백준]2096: 내려가기 www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이 DP문제로 프로그래머스의 '정수 삼각형'문제와 매우 유사하다. 정수 삼각형은 최대값만 찾았다면 이번 문제는 최대, 최소값을 모두 찾는 문제이다. 합을 누적시킬때 최대값을 누적시키는 maxDp, 최솟값을 누적시키는 minDp배열을 만들어 주었다. 이때 한 줄당 총 3개의 숫자가 올 수 있으므로 3개의 경우로 나누어서 누적시켜주었다. 각각의 위치에서 누적시킬 인덱스는 다음과 같다. 현재 인덱스가 ..
-
[백준]15686: 치킨 배달 - JAVA문제풀이/백준 2021. 4. 25. 20:54
[백준]15686: 치킨 배달 www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 백트랙킹 + 조합을 사용하여 문제를 풀었다. 자주 보이는 유형 중에 하나이당. 먼저 연산을 편리하게 하기 위해 집의 위치와 치킨집의 위치를 arraylist로 따로 저장해주었다. m개의 뽑은 치킨집은 boolean타입으로 체크하여 이미 뽑았는지 여부와 함께 도시의 치킨 거리를 구할때도 사용할 수 있도록 하였다. 치킨집 m개를 모두 뽑고난 후 각각의 집 위..
-
[백준]1062: 가르침 - JAVA문제풀이/백준 2021. 4. 24. 15:08
[백준]1062: 가르침 www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 백트래킹과 조합을 사용하여 풀었다. 이 문제는 앞 뒤 'anta'와 'tica'에 속한 a,c,n,t,i 5개의 알파벳을 제외하고 k개의 알파벳을 추가로 학습하여 읽을 수 있는 단어의 최대 개수를 구하는 문제이다. 알파벳을 뽑았는지 확인하기 위해 boolean타입의 visited배열을 선언해 주었고 이미 알고있는 a,c,n,t,i를 true로 설정해 주었다. 그리고 뽑은 알..
-
[백준]1339: 단어 수학 - JAVA문제풀이/백준 2021. 4. 24. 13:54
[백준]1339: 단어 수학 www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 백트랙킹을 사용하여 풀었다. 먼저 알파벳을 리스트에 중복 없이 저장한 다음, 0부터 숫자를 하나씩 올리며 알파벳에 숫자를 할당(?)해 주었다. 리스트의 길이만큼 숫자를 다 뽑았다면 원래의 문자열과 비교하여 자리수에 맞게 숫자 연산을 하여 MAX값을 찾아주었다. 풀이 코드의 구조를 보면 전형적인 백트랙킹 순열 문제와 같다. 이번 문제에서 어려웠던 부분은 문자열을 자리수에 맞..
-
[백준]16929: Two Dots - JAVA문제풀이/백준 2021. 4. 21. 15:37
[백준]16929: Two Dots www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 풀이 해당 게임을 알고 있다면 아주 쉽게 이해할 수 있다. 싸이클을 이루는 같은 색의 점 4개를 선택할 수 있는지 출력하는 문제이다. DFS탐색을 사용해 문제를 풀었다. 싸이클을 확인하는 방법을 아래와 같이 구현하였당. 첫번째로 선택한 점과 마지막에 선택한 점이 같아야 한다. 선택된 점들의 개수가 4개 이상이어야 한다. 위의 조건을 만족하면 true를 반환하고, 아니..
-
[백준]5430: AC - JAVA문제풀이/백준 2021. 4. 18. 18:44
[백준]5430: AC www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 복잡한(자바에선 이정도 문자열이면 복잡한 문자열에 속한다고 생각한당.)문자열을 입력받은 후 문제의 조건에 맞게 출력하면 되는 문제이다. 자바로 문자열 문제들을 풀때 입력 받을때, 출력할때, 문자열 쪼개고 예외케이스 처리할 때마다 머리가 아프다.. 처음에는 StringBuilder객체를 사용해서 직접 reverse()와 substring() 함수를 사용하여 문자열을 조작해 주었는데 시간초과가 났다. 그래서 start, end포인터를 만들어 ..