3주차에서는 알고리즘 연습을 진행했다.
페어프로그래밍 형식으로 진행되었고 풀지 못했던 문제나 풀었지만 어려웠던 문제를 위주로 리뷰를 해보고자 한다.
(마라톤 35문제)
※ 제일 작은 수 제거하기
- 풀지못함
작성했던 코드
int[] arr = {4,3,2,1};
List<Integer> answer = new ArrayList<>();
Arrays.sort(arr);
for(int i =0; i<arr.length; i++){
answer.add((arr[i]));
}
Arrays.sort(arr);
answer.remove(0);
for (int i : arr) {
answer.remove((Integer.valueOf(0)));
}
for (int i : answer){
System.out.print(i);
}
GPT에서 리뷰 받은 결과
1. Arrays.sort(arr); : 두 번 호출할 필요가 없다. - > 정렬된 배열을 한 번 만들고 나면 그대로 사용가능
2. 이 방식은 remove 메서드가 리스트를 재배열해야 해서 효율적이지 않음
3. remove(0)을 호출해서 첫 번째 요소를 제거하고 있지만, 이것은 항상 작은 값을 제거하는게 아님.
(첫 번째 요소가 중복 값이라면, 중복되는 값 중 가장 작은 값이 아닐 수 있음)
Solution
- 리스트에서 첫 번째 요소를 제거하는 대신, 가장 작은 값과 가은 값을 찾아 제거해야함
- 배열 정렬 후 요소를 리스트에 추가하는 것보다 바로 리스트에 추가하고 나중에 정렬하는 것이 효율적
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String[] args) {
int[] arr = {4, 3, 2, 1};
List<Integer> answer = new ArrayList<>();
// 배열의 요소를 리스트에 추가
for (int i : arr) {
answer.add(i);
}
// 배열을 정렬
Arrays.sort(arr);
// 정렬된 배열의 첫 번째 요소(가장 작은 값)을 찾음
int min = arr[0];
// 리스트에서 가장 작은 값을 제외한 나머지 값을 찾아 제거
answer.remove(Integer.valueOf(min));
// 결과 출력
for (int i : answer) {
System.out.print(i + " ");
}
}
}
다른 방식의 코드
package projext;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class q19 {
private static int[] solution(int[] arr) {
// -1 반환하는 코드
if (arr.length == 1) {return new int[]{-1};}
// arr의 복사본을 만들고 정렬, 가장 작은 값 찾기
int[] tmp = Arrays.copyOf(arr,arr.length);
Arrays.sort(arr);
int min = arr[0];
// 빈 리스트를 생성 (가장 작은 값을 제외한 값들을 저장)
List<Integer> list = new ArrayList<>();
// tmp를 i로 반복해준다.
for(int i : tmp){
// 값이 가장 작은 경우에만 추가해준다.
if(i!=min){list.add(i);}
}
return list.stream().mapToInt(i -> i).toArray();
}
public static void main(String[] args) {
System.out.println(Arrays.toString(q19.solution(new int[]{4,3,2,1})));
}
}
stream
컬렉션, 배열 등에 저장된 요소들을 하나씩 참조하면서 코드를 실행할 수 있는 기능
스트림을 사용하면 불필요한 for문을 사용하지 않을 수 있고, 람다식을 활용할 수 있어서 코드를 직관적으로 처리 가능
- list에 저장된 값을 stream 변환 -> mapToInt() 으로 각 요소에 정수로 매핑해준다.
- toArray 메소드를 활용해서 스트림의 요소를 정수(배열)로 반환한다.
→ 리스트에 저장된 값들을 정수(배열)로 변환해서 반환해준다.
* Arrays.toString() 메소드를 사용해서 정수 배열을 문자열로 변환하고 출력해준다.
※ 최대공약수와 최소공배수
- 풀긴했지만 어려움
작성 코드
public static void main(String[] args) {
int a = 2;
int b = 5;
System.out.println(gcd(a,b));
System.out.println(lcm(a,b));
}
public static int gcd(int a, int b){
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
}
이 문제는 접근 방식을 모르겠어서 검색을 해봤는데 공식같은 것이 있었다.
유클리드 호제법을 이용하는 방식인데 유클리드 호제법은 최대 공약수를 구하는 효율적인 방법이다.
유클리드 호제법?
큰 수에서 작은 수를 빼도 두 수의 최대공약수(GCD)가 변하지 않는다는 원리에 기초한다.
이 과정은 두 숫자가 동일해질 때까지 계속되며, 이는 최대 공약수이다.
- 두 개의 양의 정수 a와 b ( a는 b보다 크거나 같다.)
- a를 b로 나누고 나머지를 r로 둔다. ( r은 b보다 작다.)
- a를 b로, b를 r로 바꾼다.
- b가 0이 될 때까지 2번과 3번을 반복한다.
- 이 시점에서 a의 값은 원래 두 정수 a와 b의 최대 공약수.
코드 리뷰
1. gcd 메서드에서는 유클리드 호제법을 사용해 최대 공약수를 구함
2. lcm 메서드에서는 최소 공배수를 구함
- 최소 공배수는 ( a * b ) / gcd( a * b)로 구할 수 있음
※ 최소직사각형
- 이해하기 어려워서 풀기 어려웠음
작성코드
public static void main(String[] args) {
// [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133
// [[14, 4], [19, 6], [16, 6], [18, 7], 11, 7]]
int[][] sizes = {{60, 50}, {30, 70}, {60, 30}, {80, 40}};
int max_h = 0;
int max_v =0;
for (int i = 0; i < sizes.length; i++) {
int v = Math.max(sizes[i][0], sizes[i][1]); // 최대값 비교
int h = Math.min(sizes[i][0], sizes[i][1]); // 최소값 비교
max_v = Math.max(max_v, v);
max_h = Math.max(max_h, h);
}
System.out.println(max_v * max_h);
}
이 문제는 문제 자체를 해석하는데 어려움이 있었다. 그래서 스펙테이터를 맡으신 분의 도움을 받아 문제를 풀게 되었다.
- 각 배열의 큰 값과 큰 값을 비교해서 가장 큰 값을 뽑는다.
- 각 배열의 작은 값과 작은 값을 비교해서 그 중 큰 값을 뽑는다.
배열의 작은 값들을 비교했을 때 큰 값을 뽑는 이유는
예를 들어 길이가 60*50 인 것과 70*30인 것이 있으면 70*50으로 만들면 두 개의 명함이 모두 들어 갈 수 있지만 70*30으로 만든다면 60*50의 명함은 넣을 수 없게된다.
그렇기 때문에 작은 값 중 큰 값을 넣어준다.
코드 리뷰
1. for문을 사용하여 주어진 사각형의 개수만큼 반복해서 각 사각형의 가로와 세로 길이를 비교
2. max_v와 max_h에서 최대 가로 길이와 최대 세로 길이를 업데이트
※ 시저암호
- 풀지 못함
작성코드
public static void main(String[] args) {
String s = "AB";
int n = 1;
System.out.println(solution(s, n));
}
public static String solution(String s, int n) {
String answer = "";
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (Character.isLowerCase(ch)) { //소문자
ch = (char) ((ch - 'a' + n) % 26 + 'a');
} else if (Character.isUpperCase(ch)) { //대문자
ch = (char) ((ch - 'A' + n) % 26 + 'A');
}
answer += ch;
}
return answer;
}
}
이 문제는 아스키코드로 접근을 해야겠다고 까진 생각을 했는데 코드를 어떻게 짜야 할 지 감이 안잡혔다.
여기서는 스펙테이터를 맡아주신 분이 본인이 작성했던 코드를 가지고 설명을 해주셨는데 몇 개는 테스트 통과가 됐지만 몇 문제는 실패해서 결국엔 공식이 있는 것 같아 그것을 사용해서 풀었다.
코드 리뷰
1. for문 : 주어진 문자열의 문자를 각각 확인하기 위해 반복문을 사용
2. if문 : 현재 문자가 소문자인 경우, 소문자 알파벳을 이동시킴
- 소문자 알파벳의 이동에는 아스키 코드를 사용
- + n % 26(알파벳의 개수) : 알파벳 범위 내에서만 이동이 되도록 하는 것
- 이동 결과를 소문자 알파벳으로 변환
- 대문자도 동일한 방식으로 해줌
3. 문자를 answer 문자열에 추가
저와 페어분 모두 자바가 처음이라 초반에는 많이 어렵고 헤맸었다. (1레벨 14문제 푸는데 8시간이나 걸렸다.ㅠㅠ)
한 문제에 30분 이상 잡고 있지 않는게 좋다고 하셨지만, 조금만 풀면 되는데.. 이것만 하면 될 것 같은데.. 이런 생각에 계속 진행을 하게 되었는데 사실 이것 때문에 공부가 많이 됐던 것 같다.
베이스가 거의 없어서 그런건지 처음에는 이렇게 풀면 될 것 같은데 이런 생각조차 안들었던 문제가 많았다.
그래도 계속 풀다보니까 몇몇 문제를 제외하면 이건 이런식으로 풀면 되겠다. 이정도 틀은 잡히기 시작했고 예상보다 빠르게 마라톤 문제를 완주 할 수 있었다.
한 문제 풀 때마다 성취감을 느낄 수 있는 점이 너무 좋았고, 다음에 비슷한 유형을 봤을 때 제대로 잘 풀 수 있는 내 모습을 보고 발전 했다고 느껴져서 알고리즘 공부는 좋은 경험이였다.
'항해99' 카테고리의 다른 글
| [항해99] WIL 24.02.17 (1) | 2024.02.17 |
|---|---|
| [항해99] 프로그래머스 알고리즘 연습하기 (2) (0) | 2024.02.17 |
| [항해99] WIL 24.02.11 (0) | 2024.02.11 |
| [항해99] 자바 문법 종합반 2주차 ( 02.06 ~ 02.07 ) (1) | 2024.02.07 |
| [항해99] WIL 24.02.04 (1) | 2024.02.05 |
