🔗 문제 링크 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr📌 문제 개요휴대폰 자판에서 각 문자를 입력하기 위해 필요한 최소 입력 횟수를 구한 뒤, targets의 각 문자열을 입력하기 위한 최소 버튼 입력 횟수를 구하는 문제이다. 같은 문자가 여러 키에 존재하거나 같은 키에 여러 번 등장할 수 있으므로, 항상 가장 적게 눌러 입력할 수 있는 횟수를 사용해야 한다.또한 자판에 존재하지 않는 문자가 포함되어 있다면 해당 문자열은 입력할 수 없으므로 -1을 반환한다.📌 접근 방법먼저 keymap을 순회하며 문자별 최소 입력 횟수를 HashMap에 저장한다.이후 targets를 순회하면서 각 문자의 입력 횟수를..

🔗 문제 링크 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr📌 문제 개요자연수 n이 주어질 때, 연속된 자연수들의 합으로 n을 표현할 수 있는 경우의 수를 구하는 문제이다.예를 들어 15는 다음과 같이 표현할 수 있다.1 + 2 + 3 + 4 + 5 = 154 + 5 + 6 = 157 + 8 = 1515 = 15따라서 정답은 4이다.📌 접근 방법연속된 자연수의 구간을 표현하기 위해 투 포인터를 사용한다.start와 end를 이용하여 현재 구간을 나타내고, 현재 구간의 합을 sum으로 관리한다.sum 이면 구간이 부족하므로 오른쪽을 확장한다.sum > n 이면 구간이 크므로 왼쪽을 줄인다.sum == n ..

🔗 문제 링크 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr📌 문제 개요자연수 n이 주어질 때 다음 조건을 만족하는 가장 작은 자연수를 구하는 문제이다.n보다 큰 수n과 2진수의 1의 개수가 같은 수조건을 만족하는 수 중 가장 작은 수예를 들어 78의 이진수는 다음과 같다.78 = 10011101의 개수는 4개이다.이후 숫자를 확인하면79 = 1001111 (5개)80 = 1010000 (2개)81 = 1010001 (3개)82 = 1010010 (3개)83 = 1010011 (4개)따라서 정답은 83이다.📌 접근 방법현재 숫자의 1의 개수를 먼저 구한다.int count = Integer.bitCount..

🔗 문제 링크 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr📌 문제 개요피보나치 수열은 다음과 같은 규칙을 가진다. n번째 피보나치 수를 구한 뒤, 1234567로 나눈 나머지를 반환하는 문제이다.F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2)📌 접근 방법처음에는 DP 배열을 사용하여 모든 피보나치 값을 저장할 수 있다.arr[i] = arr[i - 1] + arr[i - 2];하지만 현재 값을 계산할 때 필요한 것은 직전 두 개의 값뿐이다.따라서 배열 대신 두 개의 변수만 사용하여 공간을 절약할 수 있다.또한 피보나치 수는 매우 빠르게 증가하므로 매 계산마다 1234567로 나눈 나..

🔗 문제 링크 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr📌 문제 개요괄호 문자열이 주어졌을 때 올바른 괄호인지 판별하는 문제이다.올바른 괄호란 열린 괄호 ( 가 나오면 반드시 대응되는 닫힌 괄호 ) 가 존재해야 하며, 순서 또한 올바르게 짝지어져 있어야 한다.예를 들어()() → 올바른 괄호(())() → 올바른 괄호)()( → 올바르지 않은 괄호(()( → 올바르지 않은 괄호문자열이 올바른 괄호이면 true, 아니면 false를 반환한다.📌 접근 방법괄호의 짝을 확인해야 하므로 스택(Stack)을 사용한다.문자를 하나씩 확인하면서( 이면 스택에 저장한다.) 이면 가장 최근에 저장된 ( 와 짝을 맞춘다..

🔗 문제 링크 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr📌 문제 개요길이가 같은 두 배열 A, B가 주어진다.각 배열에서 숫자를 하나씩 선택하여 곱한 뒤 누적 합을 구한다. 모든 원소를 한 번씩만 사용해야 하며, 최종 누적 합이 최소가 되도록 만들어야 한다.📌 접근 방법처음에는 같은 인덱스의 값끼리 곱하면 된다고 생각할 수 있다.하지만 이렇게 하면 최솟값이 보장되지 않는다. 예를 들어, 같은 인덱스끼리 곱하면A = [1, 2]B = [3, 4]1 * 3 + 2 * 4 = 11 반면 아래와 같이 작업시 더 작다.따라서 작은 수와 큰 수를 매칭하는 방식이 필요하다.1 * 4 + 2 * 3 = 10📌 핵심..

🔗 문제 링크https://programmers.co.kr/learn/courses/30/lessons/49191📌 문제 개요권투 선수 간 경기 결과가 주어질 때일부 결과가 누락된 상태에서도 정확한 순위를 알 수 있는 선수 수를 구하는 문제이다.단, A가 B를 이기면 항상 이긴다는 전제가 존재한다.📌 접근 방법이 문제는 단순 승패가 아니라간접 관계까지 포함한 전체 승패 관계를 구해야 한다. 따라서 그래프를 사용하여 관계를 저장하고플로이드-워셜 알고리즘을 통해 모든 경로를 확장한다.- “직접 승패 + 간접 승패”를 모두 알아야 함,그래서 플로이드-워셜로 모든 승패 관계를 확장하는 것 플로이드-워셜 알고리즘- “모든 정점 쌍 사이의 최단 경로(또는 도달 가능 여부)를 한 번에 구하는 알고리즘”- 모든 ..