Java

[백준, Java] 1806번 : 부분합

🔗 문제 링크 https://www.acmicpc.net/problem/1806 🤔 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 😮 문제 해결 방법 아래의 그림과 같이 num 배열이 주어지고 다음 인덱스로 갈 때 마다 이전 값을 누적해서 더해주는 sum배열을 생성한다. 각 인덱스의 누적합을 더해준 sum배열의 동작에 대해 알아야한다. 예를 들어, sum 배열에서 인덱스 2에서 인덱스 6까지의 부분합을 구하고 싶다면, sum[6] - sum[2] = 25를 구할 수 있다. 이 결과가 성립할 수 있는 이유는 sum[2] = num[1] ~ num[2]까지..

[ 백준, Java] 1339번 : 단어 수학

🔗 문제 링크 https://www.acmicpc.net/problem/1339 🤔 문제 민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그..

[백준, Java] 16120번 : PPAP

🔗 문제 링크 https://www.acmicpc.net/problem/16120 😮 문제 해결 방법 스택을 이용해서 문제를 해결했다. ‘P’가 들어오는 경우 스택에 저장하고, ‘A’가 들어오는 경우는 PPAP 문자열인지 판단해주었다. ‘A’가 들어오는 경우 PPAP 문자열인지 판단하기 위해 바로 다음 인덱스 문자가 ‘P’인지 판단하고 스택 사이즈가 2 이상 (스택에는 ‘P’만 들어감)인지 확인 후 스택을 두번 pop해 주었다. 결론적으로, 스택에서 pop된 문자 2개 PP와 현재 인덱스 A, 다음 인덱스 P가 되어 문자열 PPAP가 만들어지므로 다음 인덱스 ‘P’로 대체가 가능하다. 이외의 경우는 PPAP문자열을 P로 대체할 수 없으므로 “NP”를 리턴한다. 모든 PPAP 문자열이 P로 대체된다면, 마..

[백준, Java] 16637번 : 괄호 추가하기

🔗 문제 링크 https://www.acmicpc.net/problem/16637 😮 문제 해결 방법 문제에서 주의깊게 봐야하는 조건이 몇가지 있다. 모든 연산자의 우선순위는 동일하기 때문에 수식 계산은 왼쪽 부터 차례로 계산한다. 괄호 안에는 연산자가 한 개만 들어간다. 1번 조건을 충족하기 위해서 재귀함수 호출 시 마다 현재까지의 결과 값(ouput 파라미터)과 괄호 추가한 경우 결과값 혹은 다음 차례의 피연산자와 계산을 한 결과값을 다음 재귀 호출시 넣어주어야 한다. 2번 조건을 충족하기 위해서 **현재 차례로 부터 다음 차례와 다다음 차례 (index + 1, index + 2)**의 피연산자를 먼저 계산해준다. 그 후 현재까지의 결과 값과 다시 한번 계산 하면 괄호를 반영한 결과값을 구할 수 있..