문제풀이
-
[프로그래머스]이중우선순위큐 - JAVA문제풀이/프로그래머스 2021. 2. 12. 13:39
[프로그래머스]이중우선순위큐 programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 풀이 문제 제목에 힌트가 있듯이 우선순위 큐 2개를 사용하여 구현하였다. 하나는 최소힙 구조의 우선순의 큐를 사용하여 저장해주었고, 하나는 Collections.reverseOrder() 메소드를 사용하여 최대힙으로 구현해 주었다. 그리고 연산 기호에 따라 동작을 처리해 주었다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import java.util.*; class Solution { pub..
-
[백준]1759: 암호 만들기 - JAVA문제풀이/백준 2021. 2. 11. 20:55
[백준]1759: 암호 만들기 www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 순열을 사용한 백트랙킹문제! 결과가 사전 순서대로 저장되어야 하므로 sort를 해주었다. 그리고 값을 뽑을때 알파벳이 증가하는 순서대로만 뽑아야 하므로 compareTo 메소드를 사용하여 이전의 뽑은 값과 비교해 주었다. 또한 모음인지 체크하는 함수를 만들어 주었고 조건에 모든 문자를 다 뽑은 후에는 모음의 수, 자음의 수가 조건에 맞는지 확인한 후 맞다면 출력하도록 해주었다. 별..
-
[백준]10844: 쉬운 계단 수 - JAVA문제풀이/백준 2021. 2. 11. 18:51
[백준]10844: 쉬운 계단 수 www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 DP문제는 진짜진짜 많이 풀어봐야 할 것 같다. 아직 완전히 이해하고 풀 수준이 안되는 것 같다. 이 문제는 dp함수를 2차원 배열로 만들었다. dp배열 의미하는 뜻은 dp[길이][마지막 자리수가 계단이 되는 경우의 수] 이다. n이 1 일때는 다음과 같다. n이 1일때 0은 결과에 포함되지 않으므로 계산하지 않는다. dp[1][1] 1 길이가 1일이고 끝자리의 수가 1일때 앞에 올 수 있는 수는 없으므로 1이다. dp[1][2] 1 길이가 1일이고 끝자리의 수가 2일때 앞에 올 수 있..
-
[백준]2470: 두 용액 - JAVA문제풀이/백준 2021. 2. 10. 18:45
[백준]2470: 두 용액 www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 이분탐색 문제를 풀어보려고 풀었는데 풀고나니 이분탐색 문제보다는 투포인터? 라는 문제라고 한다. 배열을 정렬한 후 첫 인덱스와 마지막 인덱스 값을 증감하며 적절한 위치를 찾아주었다. scanner를 써서 풀면 시간초과가 났다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..
-
[백준]14503: 로봇 청소기 - JAVA문제풀이/백준 2021. 2. 10. 16:32
[백준]14503: 로봇 청소기 - JAVA www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 조건에 맞는 모든 경우를 탐색해야 하므로 dfs를 사용하여 풀었다. 여기서 중요한 조건은 탐색을 할 때에는 이전으로 되돌아 갈 수 없다는 조건이다. 예를들어서 아래와 같은 경우이고 시작 위치가 1,1일때 1 0 0 1 0 1 1 0 0 dfs로 탐색을 한 방향으로 하고 나면 아래와 같아진다. 1 2 2 1 2 1 1 0 0 이후에는 원래 dfs라면 1,1로 돌..
-
[프로그래머스]경주로 건설 - JAVA문제풀이/프로그래머스 2021. 2. 10. 14:57
[프로그래머스]경주로 건설 - JAVA programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 풀이 최소 비용을 구하는 문제이므로 모든 경우를 다 탐색하는 ..
-
[백준]1916: 최소비용 구하기 - JAVA문제풀이/백준 2021. 2. 9. 16:08
[백준]1916: 최소비용 구하기 www.acmicpc.net/problem/1916 풀이 전형적인 다익스트라 알고리즘을 사용하는 문제였다. 채점할때 50퍼센트에서 계속 틀리길래 이것 저것 건드려 보다가 초기화 하는 값을 변경해 주었더니 맞았다. 거리를 계산하는 문제들을 풀 때에는 초기화 값을 항상 신경써서 설정해 주어야 겠다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 import java.util.*; p..
-
[백준]17406: 배열 돌리기4 - JAVA문제풀이/백준 2021. 2. 9. 15:19
[백준]17406:배열 돌리기4 www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 회전 순서에 따라 결과가 바뀌므로 순열을 사용하였다. 순열로 K의 회전 순서를 뽑은 후 회전시켰고, 회전이 끝난 후 각 배열의 행의 최솟값을 계산해주었다. 순열은 어렵지 않았지만 회전하는 부분이 생각해주어야 할 조건이 많아서 시간이 오래걸렸다. 회전을 하기 위해 한 자리씩 이동할 때 회전 방향에 존재하는 가장 마지막 값들이 지위져 이 값들을 따..