문제풀이/프로그래머스
-
[프로그래머스]합승 택시 요금 - JAVA문제풀이/프로그래머스 2021. 2. 17. 13:59
[프로그래머스]합승 택시 요금 programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 풀이 방향성이 없는 연결 그래프에서 최단 경로를 구해야 하는 문제였..
-
[프로그래머스]불량 사용자 - JAVA문제풀이/프로그래머스 2021. 2. 16. 14:25
[프로그래머스]불량 사용자 programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 풀이 백트랙킹을 사용하여 뽑을 수 있는 모든 경우의 수를 뽑은 뒤 HashSet에 저장해 중복된 값이 이미 있었으면 저장이 되지 않도록 하였다. 그리고 마지막으로 set의 size를 return하였다. 문자열을 비교할 때는 정규식을 사용하기 위해 banned_id의 "*"을 모두 "."으로 바꾸어 주었다. 그리고 mathes()함수를 사용해 정규식과 u..
-
[프로그래머스]정수 삼각형 - JAVA문제풀이/프로그래머스 2021. 2. 15. 13:43
[프로그래머스]정수 삼각형 programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 DP문제 치고 쉬운 DP문제여서 어렵지 않게 접근했다! 위치별로 누적 값을 저장하여주기 위해 dp를 2차원 배열로 만들어 주었다. 그리고 마지막에 배열의 마지막줄에서 최댓값을 찾아 반환해 주었다. 우선 문제의 예제를 분석해 보았다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 예제에 따르면 매개변수인 triangle은 이러한 형태로 전달된다. 이때 각 항목별로 값을 계산해 나가는 과정을 써보았다. dp[0][0..
-
[프로그래머스]N-Queen - JAVA문제풀이/프로그래머스 2021. 2. 14. 13:51
[프로그래머스]N-Queen programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 풀이 순열을 사용하여 풀었다. 순열로 퀸의 순서를 뽑아준 후, 뽑은 퀸을 이전의 뽑았던 퀸의 위치와 비교하여 뽑을 수 있는 위치라면 재귀함수를 사용해 순환적으로 호출해주었고, 뽑을 수 없는 위치라면(행이 같거나 대각선 위치에 존재하거나) 퀸을 뽑지 않았다. 뽑을 때는 1차원 배열을 이용해 각 인덱스가 하나의 열을 나타내도록 하였다. ..
-
[프로그래머스]가장 먼 노드 - JAVA문제풀이/프로그래머스 2021. 2. 13. 14:33
[프로그래머스]가장 먼 노드 - JAVA programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 최단경로로 이동하며 답을 찾아야 하는 문제이므로 BFS를 사용했다. 인접 행렬을 사용했는데, boolean이 아닌 int형으로 선언하면 메모리 초과가 난다. 인접 리스트로 구현하면 메모리 초과가 나지 않는다고 한다. 기본적인 BFS와 동일한데 중요한 점은 반환 값이 가장 멀리 떨어진 노드의 수 라는 점이다. 이를 위해 qSize로 큐의 크기를 저장해 마지막 큐의 크기를 반환하도록 구현하였다. 가장 멀..
-
[프로그래머스]이중우선순위큐 - 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..
-
[프로그래머스]경주로 건설 - 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 풀이 최소 비용을 구하는 문제이므로 모든 경우를 다 탐색하는 ..