본문 바로가기

분류 전체보기

 (386)
[pro] 프로그래머스 level3 131129 카운트 다운 (Java) - dp [문제] https://school.programmers.co.kr/learn/courses/30/lessons/131129 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] dp 문제이다. 최선의 경우 던질 다트의 수와 그 때의 싱글/불을 맞춘 횟수의 합을 반환해야 한다. 두 가지 정보를 기록해 주기 위해 dp[i][0]에는 i 점을 맞출 때 던질 수 있는 최소한의 다트 수를, dp[i][1]에는 그때의 싱글/불을 맞춘 횟수를 저장해주도록 했다. 그 다음 for문 반복을 통해 1~target 점수까지, 1~20점의 다트 점수마다 불/싱글/더블/트리..
[pro] 프로그래머스 level3 12920 선입 선출 스케줄링 (Java) - 이분탐색 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/12920 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] for문 반복으로 초를 증가시켜가며 n의 개수를 감소시키거나 우선순위 큐를 이용하는 방법도 있지만 시간초과가 발생하므로 효율적으로 풀기위한 방법을 찾아야 하는 문제. 이분탐색으로 풀 수 있다. 이분탐색을 하기 위해서는 이분탐색의 기준이 되는 값을 무엇으로 정할 지가 중요하다. cores[0]=1 cores[1]=2 cores[2]=3 누적값 0H o o o 3개 1H o x x ..
[pro] 프로그래머스 level3 87391 공 이동 시뮬레이션 (Java) - 시뮬레이션 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/87391 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] n, m의 범위가 둘 다 매우 크기 때문에 모든 지점에 대해 탐색을 하면 시간초과가 발생할 것이다. 따라서 효율적으로 문제를 해결할 방법을 생각해봐야 한다. 행과 열의 이동을 분리해서 생각하면 조금 더 쉽게 문제를 이해할 수 있다. n=4, m=3, (x,y) = (0,0)는 queries는 ↑ ← → ← ↑ 순서대로 이동한다고 가정해보자. 행 방향 이동인 ↑ ↑ 에 대해서만 생..
[pro] 프로그래머스 level3 152995 인사고과 (Java) [문제] https://school.programmers.co.kr/learn/courses/30/lessons/152995 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 1. 원호가 인센티브를 받지 못하는 경우 -1을 반환한다. 2. 근무태도에 대해 내림차순 정렬 후 0~i-1 의 사원에 대해서 인센티브를 받지 못하는 사원을 걸러낸다. i번째 사원은 이미 0~i-1 번째 사원보다 근무태도 점수가 낮거나 같다. 근무태도 점수가 낮은데 동료평가 점수도 낮다면 인센티브를 받지 못하므로 제외하고, 그렇지 않은 경우만 map에 넣어준다. 3. 총점 순으..
[pro] 프로그래머스 level3 42628 이중우선순위큐 (Java) - heap [문제] https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 최대힙, 최소힙 두개를 만들어서 사용하면 쉽게 해결 가능하다. 두 개의 우선순위큐에서 모두 삭제되어야 하기 때문에 remove(Object o)를 이용한다. [코드] import java.util.*; class Solution { public int[] solution(String[] operations) { int[] answer = new int[2]; PriorityQue..
[pro] 프로그래머스 level3 92345 사라지는 발판 (Java) - DFS [문제] https://school.programmers.co.kr/learn/courses/30/lessons/92345 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 양 플레이어가 최적의 플레이를 해야 한다. 이길 수 있는 플레이어는 최대한 빨리 이겨야 하고, 질수밖에 없는 플레이어는 최대한 오래 버티다 져야 한다. 1. 현재 플레이어가 이동했을 때, 발판이 없으면 패배한다. 2. 상하좌우 방향으로 현재 플레이어가 이동 가능하다면 원래 있던 발판을 0으로 바꿔주고, DFS 재귀 호출을 통해 다음 플레이어로 턴을 넘긴다. 3. 플레이어의 상하좌..
[pro] 프로그래머스 level4 42891 무지의 먹방 라이브 (Java) - 시뮬레이션 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/42891 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] food_times의 모든 음식을 먹는데 걸리는 시간이 k초 이상이라면 네트워크 장애 발생 이후 다시 먹을 음식이 없으므로 -1을 반환하도록 한다. 우선순위큐를 이용하여 음식을 먹는데 걸리는 시간 오름차순으로 Food를 빼올 수 있게 한다. 시간이 가장 적게 걸리는 음식을 다 먹을 수 있다면 더 오래 걸리는 음식들 역시 그 시간동안 먹게되므로 초가 감소될 것이다. 이를 이용해서 ..
[pro] 프로그래머스 level4 43236 징검다리 (Java) - 이분탐색 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/43236 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 지점과 지점 사이 거리 최솟값 중 가장 큰 값을 구해야 하므로 이를 이분탐색의 기준으로 이용할 수 있다. 지점과 지점 사이 거리 최솟값을 먼저 설정한 후, 이를 기준으로 돌을 제거해본다. 제거된 돌이 n개보다 많다면 간격 최솟값을 줄여(high = mid-1) 돌이 더 적게 제거되도록 해야 하고, n개 이하라면 answer를 갱신해준 후, 더 큰 간격도 가능한지 확인해보기 위해 ..

티스토리툴바