1. 최대공약수와 최소공배수
: 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
제한 사항
두 수는 1이상 1000000이하의 자연수입니다.
[문제 풀이]
1. 입력된 두 수의 최대공약수를 구해서 배열[0]에 추가
2. 최소공배수를 구해서 배열[1]에 추가
class Solution {
public int[] solution(int n, int m) {
int[] answer = new int[2];
int min = (n < m) ? n : m;
int gcd = 0;
for (int i = 1; i <= min; i++) {
if (n % i == 0 && m % i == 0)
gcd = i;
}
answer[0] = gcd;
answer[1] = n * m / gcd;
return answer;
}
}[기억해야할 이론]
- 유클리드 호제법
: 유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나.
호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타냄.
(추가 참고 : https://programmer-chocho.tistory.com/9 )
2. 올바른 괄호
: 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
제한사항
문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
[문제 풀이]
- 괄호의 짝을 for문을 돌려서 확인
-> 효율성 검사에서 실패하게됨.
//-> 효율성 검사에서 실패하게됨.
class Solution {
boolean solution(String s) {
boolean answer = true;
// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
System.out.println("Hello Java");
String[] arr = s.split("");
int right = 0;
int left = 0;
for(int i = 0; i < arr.length; i++){
if(arr[i].equals("(")){
left ++;
}
else if(arr[i].equals(")")){
right++;
}
}
if(left == right && arr[0].equals("(") && arr[arr.length - 1].equals(")")){
answer = true;
}
else answer = false;
return answer;
}
}//스택을 이용한 풀이
import java.util.Stack;
class Solution {
boolean solution(String s) {
boolean answer = true;
// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
System.out.println("Hello Java");
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(c);
} else if (c == ')') {
if (stack.isEmpty() || stack.pop() != '(') {
return false;
}
}
}
//스택에 남아있는 괄호가 없으면 올바른 괄호 문자열이므로 true를 반환
//스택에 괄호가 남아있으면 짝이 맞지 않는 괄호가 있으므로 false를 반환
return stack.isEmpty();
}
}[기억해야할 이론]
(참고 : https://coding-factory.tistory.com/601)
- 스택
- 먼저 들어간 자료가 나중에 나옴 LIFO(Last In First Out) 구조
- 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함
- 인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임
- 그래프의 깊이 우선 탐색(DFS)에서 사용
- 재귀적(Recursion) 함수를 호출 할 때 사용
//stack에서 사용하는 함수
Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1); // stack에 값 1 추가
stack.push(2); // stack에 값 2 추가
stack.size(); // stack의 크기 출력 : 2
stack.empty(); // stack이 비어있는제 check (비어있다면 true)
stack.contains(1) // stack에 1이 있는지 check (있다면 true)3. 최솟값 만들기
: 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.
배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)
예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면
A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
A에서 세번째 숫자인 2, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)
즉, 이 경우가 최소가 되므로 29를 return 합니다.
배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.
제한사항
배열 A, B의 크기 : 1,000 이하의 자연수
배열 A, B의 원소의 크기 : 1,000 이하의 자연수
[문제 풀이]
- 누적된 값이 최소가 되게 하는 것이 목표
- 완전 탐색 알고리즘을 사용해야함
import java.util.Arrays;
class Solution
{
public int solution(int []A, int []B)
{
int answer = 0;
// 배열 A와 배열 B를 오름차순으로 정렬
Arrays.sort(A);
Arrays.sort(B);
// 배열 A의 가장 작은 값과 배열 B의 가장 큰 값을 곱하여 최소값을 구함
for (int i = 0; i < A.length; i++) {
answer += A[i] * B[B.length - i - 1];
}
return answer;
}
}[기억해야할 부분]
- 그리디 알고리즘(Greedy Algorithm)의 대표적인 문제
(참고 : https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm)
