본문 바로가기

알고리즘 공부 및 문제 풀이/프로그래머스(PRO)

 (81)
[pro] 프로그래머스 level2 134239 우박수열 정적분 (Java) - 시뮬레이션 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/134239 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 단순 구현. 모든 x좌표에 대해서 우박수열의 꺾은 선 그래프에 의해 생기는 사다리꼴의 넓이를 구해서 저장해 준 후 사용하였다. [코드] import java.util.*; class Solution { public double[] solution(int k, int[][] ranges) { double[] answer = {}; //정적분의 결과 목록을 return List l..
[pro] 프로그래머스 level2 132265 롤케이크 자르기 (Java) - 시뮬레이션 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/132265 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 포인터를 이동시켜가며 오른쪽 해시맵에 있던 토핑을 왼쪽 해시맵으로 옮겨준다. 이후 해시맵의 크기를 비교해가며 크기가 같으면 answer를 증가시킨다. 처음에는 중복없이 토핑 종류의 개수만 저장하기 위해 Set을 사용하려 했으나 이 경우 전체 토핑이 한 번에 삭제되기 때문에 토핑의 종류와 개수를 함께 저장할 수 있는 HashMap을 이용해주었다. [코드] import java.u..
[pro] 프로그래머스 level2 135807 숫자 카드 나누기 (Java) - 시뮬레이션 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/135807 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] arrayA의 최대공약수를 구한 후 arrayB를 나눌 수 없는지 확인한다. 마찬가지로 arrayB의 최대공약수를 구하고, arrayA를 나눌 수 없는지 확인한다. 그 중 더 큰 수가 정답이 된다. 최대공약수의 약수들에 대해서도 확인해야 하는 것이 아닌가? 라는 생각에 빠져서 조금 헤매었다. 결과적으로는 최대공약수에 대해서만 비교를 해주면 된다. 예를 들어, arrayA의 최대..
[pro] 프로그래머스 level2 140107 점 찍기 (Java) - 시뮬레이션 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/140107 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] d의 범위가
[pro] 프로그래머스 level2 142085 디펜스 게임 (Java) - 시뮬레이션 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 단순 구현. 우선순위큐를 이용하여 가장 병사가 많은 라운드에서 무적권을 사용할 수 있도록 해준다. [코드] import java.util.*; class Solution { public int solution(int n, int k, int[] enemy) { int answer = 0; //준호가 몇 라운드까지 막을 수 있는지 return PriorityQueue pq = n..
[pro] 프로그래머스 level2 148653 마법의 엘리베이터 (Java) - 시뮬레이션 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/148653 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 각 자릿수마다 엘리베이터를 올리는게 최소인지, 내리는게 최소인지 판단해야 한다. 먼저 6, 7, 8, 9일 때 엘리베이터를 올린다면 각각 4, 3, 2, 1 만큼 올리고 내릴 때보다 1만큼 더 소요되므로 5, 4, 3, 2 만큼이 들 것이다. 이는 엘리베이터를 내리는 경우 6, 7, 8, 9 가 걸리는 것보다 작다. 단순히 생각해보아도 엘리베이터를 무조건 올려야 최소가 될 것이..
[pro] 프로그래머스 level2 152996 시소 짝꿍 (Java) - 구현 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/152996 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 오름차순 정렬을 했기 때문에 무게가 같은 경우와 (*4,*3), (*3, *2), (*4, *2) 경우에 대해서만 체크해준다. 또한 같은 무게인 경우 앞서 구한 count에서 1을 뺀 값을 그대로 활용할 수 있다. 시간초과가 나지 않기 위해서 필수적인 부분! [코드] import java.util.*; class Solution { public long solution(int[..
[pro] 프로그래머스 level2 154538 숫자 변환하기 (Java) - DP [문제] https://school.programmers.co.kr/learn/courses/30/lessons/154538 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] dfs&bfs 풀이로 먼저 생각이 되었는데 dfs 로 풀었다가 시간초과가 났다. 그래서 완전탐색말고 더 효율적인 코드를 찾아서 dp로 풀이하게 되었다. (bfs 로 푼 정답 코드는 찾아보니 많다..) dp 풀이도 단순하게 3가지 경우만 고려해주면 된다. dp[i] = x를 i로 변환하기 위해 필요한 최소 연산 수를 저장한다. 따라서 dp[x] = 0으로 두고 시작한다. 1. d..

티스토리툴바