2023.08.18 TIL - 알고리즘 문제 - 1
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
입력이 홀수일 때 "Odd", 짝수일 때 "Even"을 출력하는 함수를 작성하는 문제이다.
class Solution {
public String solution(int num) {
String answer = num%2==0?"Even":"Odd";
return answer;
}
}
%를 사용해 2로 나눈 나머지가 0일 때 "Even", 1일 때 "Odd"를 출력하게 했다.
간단한 조건문 문제로, if else를 사용해도 문제 없이 동작한다.
어떤 배열의 평균값을 출력하는 문제이다.
class Solution {
public double solution(int[] arr) {
double answer = 0;
for (int a : arr){
answer += a;
}
return answer/arr.length;
}
}
arr 안의 요소를 모두 합한 뒤, arr의 길이로 나누면 쉽게 문제를 풀 수 있다.
다른 정답에서 stream을 사용해 Arrays.stream(array).average() 형태로 풀었는데, stream에 대한 이해가 필요할 듯하다.
주어진 자연수의 모든 자릿수를 더하는 문제이다.
import java.util.*;
public class Solution {
public int solution(int n) {
int answer = 0;
while(n!=0){
answer +=n%10;
n/=10;
}
return answer;
}
}
주어진 정수 n을 %를 이용해 10으로 나눈 나머지를 계속 더하는 형태로 어렵지 않게 풀었다.
n을 String 타입으로 변환하고 split을 활용해 분리한 후, 요소를 int로 변환해 더하는 방법도 생각해 보았는데, 실제로 그렇게 푼 사람들도 있었다.
주어진 자연수의 약수의 합을 더하는 문제이다.
import static java.lang.Math.floor;
import static java.lang.Math.sqrt;
import java.util.*;
class Solution {
public int solution(int n) {
int answer = 0;
List<Integer> arr = new ArrayList<>();
double root = sqrt(n);
for (int i = 1; i<root;i++){
if (n%i==0){
arr.add(i);
}
}
int len = arr.size();
for(int i=0;i<len;i++){
arr.add(n/arr.get(i));
}
if (floor(root)==root)
arr.add((int)root);
for (int i:arr){
answer+=i;
}
return answer;
}
}
먼저 약수에 대한 이해가 필요하다. n의 약수의 갯수는, n의 제곱근을 기준으로 그보다 작은 약수의 갯수와 큰 약수의 갯수가 일치한다. 또한, 그보다 작은 약수의 집합을 a1, a2,...,ax 그보다 큰 약수의 집합을 b1, b2,...,bx(둘 다 숫자가 작은 순서대로 나열한 것)이라 했을 때, n = ay*b(x-y)와 일치하기에 작은 약수의 집합을 알면 큰 약수의 집합도 알 수 있다.
먼저 i가 1부터(보통 for문을 쓸때처럼 0부터를 사용하면 ZeroDivisionException이 뜬다.) n의 제곱근까지를 n으로 나누어 작은 약수의 집합을 구한다. 또한, n을 이들에서 각각 나누어 큰 약수의 집합을 구한다. 그렇게 구한 집합의 요소를 모두 더하는 형태로 구성했다.
i가 n의 제곱근 이하로 for문을 지정하게 될 경우 n이 제곱수일 때를 한번에 판별할 수 있지만, 큰 약수를 구할 때 n의 제곱근이 한번 더 들어가기에 n의 제곱근 미만으로 지정한 후, n이 제곱수일 경우는 n의 제곱근이 자연수일 때를 판별해 따로 넣는 방향으로 제작하였다.
i를 1부터 n까지 모두 계산하여도 문제는 풀 수 있지만, 이 경우 시간복잡도는 n이 된다. 일부 문제에서 시간 제한을 둘 경우 시간 초과가 출력되었던 경험이 있어 조금 더 빠른 출력을 위해 n^0.5의 시간복잡도를 갖도록 작성하였다.
n을 그보다 작은 수로 나누었을 때 나머지가 1이 되는 가장 작은 수를 찾는 문제이다.
class Solution {
public int solution(int n) {
int answer = 1;
while(n%answer!=1) {
answer++;
}
return answer;
}
}
문제에서, 답이 항상 존재함은 증명될 수 있음을 알려주어 while을 통해 answer의 조건을 만족할 때까지 실행하는 코드를 작성하였는데, 만약 이것이 증명할 수 없다면 for문이나 break;를 통해 반복을 그만두는 코드를 추가해야 할 필요가 있다.
x부터 시작해 x씩 증가하는 숫자를 n개 지니는 리스트를 출력하는 문제이다.
class Solution {
public long[] solution(int x, int n) {
long[] answer = new long[n];
answer[0]=x;
for (int i = 1; i < n; i++) {
answer[i] = answer[i-1] + x;
}
return answer;
}
}
해당 리스트는 초기값이 x이고 공차가 x인 등차수열과 동일하기에, 초기값에 x를 대입한 후 이후 이전 배열 요소에서 x를 더해주는 것으로 문제를 해결하였다.
x를 i+1번 곱해준 수를 대입해도 동일하게 문제를 해결할 수 있다.
주어진 자연수의 각 자릿수를 순서를 뒤집어 배열로 만드는 문제이다.
class Solution {
public int[] solution(long n) {
String[] str = Long.toString(n).split("");
int len = str.length;
int[] answer = new int[len];
for(int i = 0;i<len;i++)
answer[i] = Integer.parseInt(str[len-i-1]);
return answer;
}
}
자릿수 n을 String으로 바꾼 후, split을 활용해 분리하였다. 이를 for문을 활용해 역순으로 집어넣는 행위를 반복해 문제를 해결하였다.
자릿수 합 문제처럼 %를 활용해 10으로 나눈 나머지를 순서대로 저장해도 같은 결과를 얻을 수 있을 것으로 예상했으나, 문제를 해결할 수 없었다. 확인한 결과, long 타입의n을 계산한 결과를 int 타입에 넣을 때 에러가 날 것을 예상해 (int)n%10 형태로 값을 넣어 주었는데, 이것이 n%10을 먼저 계산한 후 형변화한 것이 아닌 n을 형변화한 후 %10을 계산해 생긴 오버플로우가 일으킨 문제였다. (int)(n%10) 형태로 입력한 결과 정상적으로 동작하였다.