[프로그래머스] 피로도 (Java)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방식 모든 던전을 탐색하면서 던전 진입이 가능한지 여부(최소 피로도를 충족하는가)를 체크하고, 그에 따라 발생하는 두 가지 선택지를 고려해야하는 문제이다. 두 가지 선택지는 다음과 같다: 1) 최소 피로도 충족: 던전에 진입해 던전을 탐험 후 소모피로도를 감소시킨 후에 다음 던전을 탐험 2) 최소 피로도 미충족: 현재까지의 탐험 횟수와 최대 탐험 횟수(max)를 비교하여 큰 쪽을 최대 탐험횟수로 변경 이러한 접근 방식을 고려하면 모든 경우의 수를 탐색해야하는데, 던전의 개수가 8개 이하이기 때문에 DFS..

• format_list_bulleted 코딩테스트/프로그래머스
• · 2023. 4. 1.
• textsms

[프로그래머스] 두 큐 합 같게 만들기 (Java)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 최초 접근방식 (93.3점, 통과못함) 큐는 단방향으로만 움직인다는 아이디어에 착안하여 큐 2개를 합쳐 하나의 배열로 만들고, 시작과 끝 인덱스 2개를 전진시키며 합산을 체크하는 방식으로 풀어보려고 했으나, 다 통과했는데 중간에 테스트케이스 2개를 끝끝내 통과하지 못했다. 예외처리를 해줘야할 부분이 있었던게 아닌가 싶은데 아쉽지만 이 접근 방식으로 답안을 완성하지는 못했다. 프로그래머스에서는 케이스를 공개하지 않는데 가끔은 이게 실제 프로그래밍 방식과 맞는 건지 의문이 들 때가 있다. class Solutio..

• format_list_bulleted 코딩테스트/프로그래머스
• · 2023. 3. 20.
• textsms

[프로그래머스] 주식가격 (Java)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방식 예전에 풀어놨던 문제인데 뒤에 있는 큰 수 찾기 문제와 관련하여 이제서야 기록을 남긴다. 스택/큐 문제로 분류되어있으나 반복문으로 풀어냈다. 로직 설명 - 배열 prices[]를 탐색하며: 각 가격 prices[i]의 뒤에있는 가격들을 탐색하여 span을 증가시킴 - 주식 가격이 떨어지는 경우 탐색을 중단하고 answer[i]에 span을 저장함 Note - 스택으로 풀었어도 될 문제이나 구현으로 풀어내는게 더 직관적이라는 생각이 든다. class Solution { public int[] solu..

• format_list_bulleted 코딩테스트/프로그래머스
• · 2023. 3. 15.
• textsms

[프로그래머스] 뒤에 있는 큰 수 찾기 (Java)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방식 이중 반복문으로 테케는 풀렸으나 당연히 시간초과에 걸렸고, 스택으로 풀어야 해결된다는 힌트를 보고 몇 날 며칠을 고민했던 문제다. 다른 사람들의 접근법을 보고난 후에도 로직을 이해하기 위해 노력해야했는데 막상 이해하고나니 너무나 간단한 문제였다. 이런 유형에서 스택을 사용하는 이유는 탐색 도중 구간별 변화를 감지했을 때에만 그 구간에서의 결과값이 도출되기 때문이다. 즉, 구간별 변화(뒤에 나보다 큰 수가 존재하는 것)가 일어나지 않으면 결과값을 도출할 수 없고(-1), 변화가 감지되었을 때에만 탐색..

• format_list_bulleted 코딩테스트/프로그래머스
• · 2023. 3. 15.
• textsms

[프로그래머스] 땅따먹기 (Java)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 동적 계획법(Dynamic Programming, DP) 문제이다. 처음에 DFS로 테스트 케이스를 풀어내긴 했는데 인풋 최대값이 100,000이다보니 실제 채점에서는 전부 통과되지 않아 DP로 바꾸어 풀게되었다. DP는 '기억하며 풀기'로 보통 바꾸어 말하는데 반복되는 문제에 대한 최적의 결과를 단계별로 메모리에 저장하고 이를 활용하여 다음 단계의 결과를 구하는 방식으로 사용한다. 여기서는 땅따먹기의 각 단계별로 직전단계까지의 최대값을 저장(또는 land에 바로 더해주기)하는 방식으로 DP를 구현했다. - ..

• format_list_bulleted 코딩테스트/프로그래머스
• · 2023. 3. 13.
• textsms

[프로그래머스] 대충 만든 자판 (Java)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 딱히 어려운 문제는 아니다보니 금방 해결되었다. - 알파뱃별 최소 클릭 숫자를 저장할 해시맵 선언 - keymap을 탐색하며 key의 최소 클릭수를 맵에 저장 - targets의 각 문자열을 탐색하며 1) (문자열의 알파뱃이 맵에 없는 경우) answer에 -1 저장 후 break 2) (문자열의 알파뱃이 맵에 있는 경우) 문자열의 각 알파뱃 최소 클릭수를 map에서 가져와 answer에 더하기 import java.util.*; class Solution { public int[] solution(Strin..

• format_list_bulleted 코딩테스트/프로그래머스
• · 2023. 3. 8.
• textsms