반응형

공부하며 가볍게 정리

람다

람다식은 함수(메서드)를 간단한 식으로 표현하는 것

람다 작성 방법 : 메서드의 이름과 반환타입을 제거하고 →를 블록{} 앞에 추가한다

ex)

int max(int a, int b){
	return a > b ? a : b;
}
(int a, int b) -> {
	return a > b ? a : b;
}

람다식을 활용하여 사용할 때는 함수형 인터페이스를 통해서 람다를 구현할 수 있어야한다.

interface를 자체적으로 선언해서 활용해도 되고, 기존에 있는 Functions 패키지에 들어있는 여러 클래스의 의미를 명확히 아는 것이 좋을 것 같다. 그 이유는 자바에서 지원하는 내부 클래스에는 함수형 인터페이스를 매개로 동작하는 메서드들이 있는데 그 메서드를 사용하기 위해서는 함수형 인터페이스가 어떻게 활용되는지 의미라도 파악을 해야 사용할 수 있을 것이기 때문이다.

함수형 인터페이스로는 대표적으로 네가지가 있고 바로 아래 쓴 메서드가 해당 함수를 실행하는 메서드이다.

  • Supplier<T> - 공급자 : 매개변수는 없고 반환값만 있다
    • get()
  • Consumer<T> - 사용자 : 매개변수는 있고, 반환값이 없다
    • accept()
  • Function<T, R> - 함수 : 일반적인 함수형태, 하나의 매개변수를 받아 결과를 반환
    • apply()
  • Predicate<T> - 매개변수 하나를 받아서 boolean타입으로 반환한다
    • test()

T는 제네릭타입을 뜻하고, R은 리턴타입을 뜻한다.

추가로 Bi가 붙은 형태가 있는데 다른 방법은 똑같고 매개변수가 두개 들어간다는 의미이다.

 

스트림

스트림은 jdk1.8버전부터 도입이 되었는데, 도입 이유는 Collection 인터페이스의 자식인 List, Set, Map과 배열등은 이전 버전까지는 같은 메서드여도 동작하는 형태가 달랐다. 때문에 이를 통일된 방식으로 처리를 하기 위해 표준화해서 등장한 것이다.

ex) 배열, List, Set, Map의 정렬방식이 서로 다름

장점으로는 데이터 소스를 추상화하여 표준화 된 방식으로 사용이 가능하고, 또 원본의 코드를 수정하지 않기 때문에 코드의 재사용성이 높아진다. 또한 간결하게 표현이 가능해 가독성이 높아진다.

단점으로는 단순한 로직에서 데이터의 양이 적다면 순환하는데 드는 비용이 기본형의 래퍼클래스로 인해 더 크다는 것을 인지할 수 있다.(박싱 언박싱 반복)

스트림은 중간연산, 최종연산이 있고, 유의해야 할 점으로는 스트림으로 변환하면 1회만 사용되고 버려지는데, 이러한 특징으로 인해 최종연산을 실행하면 해당 스트림이 사라지는 것을 인지하고 데이터 처리를 해야한다.

중간연산 : 순차적이지 않고 상황에 맞게 커스텀된다.(스트림의 지연연산특징)

최종연산 : 중간연산을 상황에 맞게 활용 이후 출력된 데이터를 최종처리할 연산을 작성

 

Optional<T> - T타입 객체의 래퍼클래스

  • 해당 객체가 null인지 판단을 하기 때문에 nullSafe하다
  • null체크를 하는데 드는 비용이 줄어든다(if문, try catch 사용필요x)

 

 

반응형
저작자표시 비영리 변경금지

'공부 > Java' 카테고리의 다른 글

우테코 프리코스 6기 1주차 숫자야구 회고  (0) 2023.10.26
BufferedReader, StringTokenizer  (0) 2023.01.14
nextInt()입력 후 nextLine()사용 시 주의점  (0) 2022.12.18
반응형

14494번 다이나믹이 뭐예요?

https://www.acmicpc.net/problem/14494

 

14494번: 다이나믹이 뭐예요?

(1, 1)에서 (n, m)에 도달하는 경우의 수를 구하여라. 단, 경우의 수가 엄청 커질 수 있으므로 경우의 수를 1,000,000,007(=109+7)로 나눈 나머지를 출력한다.

www.acmicpc.net

Comment

DP문제의 기초격 문제

DP는 기초라고해도 왜이리 생각하기 어려운지 모르겠다..

hint

dp배열의 저장값 : 해당 지점에 도달하는 경우의 수

점화식 : 우측, 하단, 우하단 세가지 경우의 수를 활용

Solution

DP의 기초격 문제라 그런가 DP를 조금 맛본 상태에서 접했더니 점화식이 생각났던 얼마안되는 문제

먼저 dp배열을 만들고 해당 dp배열의 상단(우측으로만 진행하는 경우의 수) 하단(아래로만 진행하는 경우의 수)의 값은 도달하는 방법이 한가지 뿐이다. 때문에 먼저 초기화해서 쭉 1로 채워준 후에 해당 값을 가지고 남은 dp배열 모두를 채워나가면 되는데, 점화식은 위에 hint에 적었던 우측, 하단, 우하단 을 받는 이전dp배열을 가져오면 된다.

즉, dp[i][j] = dp[i - 1][j] + dp[i][j-1] + dp[i-1][j-1]; 로 해결이 된다

그림예시

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.io.*;
import java.util.*;
 
/**
 * dp 다차원배열 도달할 수 있는 경우의 수
 */
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int n, m;
 
        StringTokenizer st =new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        int[][] dp = new int[1001][1001];
 
        for(int i = 1; i <= n; i++){
            dp[i][1] = 1;
        }
 
        for(int i = 1; i <= m; i++){
            dp[1][i] = 1;
        }
        //값 초기화 끝
 
        for(int i = 2; i <= n; i++){
            for(int j = 2; j <= m; j++){
                dp[i][j] = (((dp[i-1][j] + dp[i][j-1]) % 1000000007) + dp[i-1][j-1]) % 1000000007;
            }
        }
 
        System.out.println(dp[n][m]);
        
    }
}
cs

 

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 2310번 어드벤처 게임 자바로 풀어 본 짧은 글  (0) 2023.11.28
백준 12755번 수면 장애 자바로 풀어 본 짧은 글  (0) 2023.11.21
백준 1680번 쓰레기 수거 자바로 풀어 본 짧은 글  (0) 2023.09.07
백준 1417번 국회의원 선거 자바로 풀어 본 짧은 글  (0) 2023.08.17
백준 골드5 달성!  (0) 2023.08.11
반응형

1680번 쓰레기 수거

https://www.acmicpc.net/problem/1680

 

1680번: 쓰레기 수거

쓰레기장에서 출발한 쓰레기차가 여러 지점들을 방문하며 쓰레기를 모으고 있다. 쓰레기차는 쓰레기장에서 가까운 지점부터 방문하며, 쓰레기를 모으다가 다음과 같은 경우에 쓰레기장으로 돌

www.acmicpc.net

Comment

일반 시뮬레이션 구현문제라서 평소처럼 풀까하다가 자바스럽게 풀어보고싶어서 객체지향(?)적으로 설계를 하기 위해 노력하면서 구현해보았다.

알고리즘을 풀 때 클래스를 잘 활용하지 않아서 생각보다 많이 오래걸렸던 문제

hint

문제를 잘 읽고 테스트케이스 또한 해당 지문에 맞춰서 잘 이해해야한다.

Solution

메모리나 시간이나 상관없이 구현만 잘하면 되는 문제였다. 때문에 클래스를 만들어서 써보기에 더 좋았던 것 같다.

일단 해당 문제의 1, 2, 3번 조건을 항상 잘 생각해서 염두에 두고 조건을 넣는다면 쉽게 풀리는 문제일 것이다.

1번의 시점은 다음 지점으로 이동하기 전이고, 2번의 시점은 쓰레기를 싣기 전, 3번은 가장 마지막. 이렇게 해당 분기를 잘 확인해서 조건처리만 잘 해준다면 문제 해결은 쉽게 될 것이다.

클래스 활용해서 구현하면 속도가 안나온다....

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
import java.io.*;
import java.util.*;
 
public class p1680 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int t = Integer.parseInt(br.readLine());
        int weight, point;
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
 
        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());
            weight = Integer.parseInt(st.nextToken());
            point = Integer.parseInt(st.nextToken());
            p1680TrashCar garbageTruck = new p1680TrashCar(weight, 0);
 
            for (int i = 0; i < point; i++) {
                st = new StringTokenizer(br.readLine());
                int pointDistance = Integer.parseInt(st.nextToken());   //해당 위치의 거리값(원점기준)
                int pointWeight = Integer.parseInt(st.nextToken());     //해당 위치의 쓰레기양
 
                garbageTruck.movePoint(pointDistance); // 해당 포인트로 이동
 
                while (pointWeight > 0) {
 
                    if (!garbageTruck.possibleCollect(pointWeight)) { //용량을 넘게될때
                        garbageTruck.movePoint(0);
                        garbageTruck.movePoint(pointDistance);
                    }
 
                    if (garbageTruck.possibleCollect(pointWeight)) { // 용량이 넘지않으면 True반환
                        pointWeight = garbageTruck.collectTrash(pointWeight); // 쓰레기 수집 -> 해당 위치의 쓰레기는 0이됨
                    }
 
                    if (garbageTruck.isFull() && i != point - 1) { // 마지막 지점이 아닐 때 쓰레기가 꽉차면 수거장에 가서 비우고 와야함
                        garbageTruck.movePoint(0);
                        garbageTruck.movePoint(pointDistance);
                    }
                }
                if (i == point - 1) {
                    garbageTruck.movePoint(0);
                }
            }
            sb.append(garbageTruck.getMeter()).append("\n");
            System.out.println(garbageTruck.getPoints()); // 쓰레기를 담기위해 문제제출할 땐 주석처리해야함
        }
        System.out.println(sb);
    }
}
 
/**
 * 기본 차 인터페이스
 * recentDestination : 목적지에 이동할 때 이동한 거리를 매 순간 담음
 */
interface p1680Car {
 
    public int getMeter();
 
    public void movePoint(int distance);
 
    ArrayList<Integer> recentDestination = new ArrayList<>();
 
    default public void pointAdd(int n) {
        recentDestination.add(n);
    }
 
    default public ArrayList<Integer> getPoints() {
        return recentDestination;
    }
 
    default public void resetDestList() {
        recentDestination.clear();
    }
 
}
 
/**
 * TrashCar는 p15979Car의 상속을 받아 Meter와 movePoint를 반드시 사용해야한다.
 * 추가로 쓰레기를 담을 capacity, 쓰레기의 용량상태확인이 필요한 trashWeight이 필요
 */
class p1680TrashCar implements p1680Car {
    private int capacity;
    private int trashWeight;
    private int meter;
    private int nowLocation;
 
    public p1680TrashCar(int capacity, int nowLocation) {
        this.capacity = capacity;
        this.nowLocation = nowLocation;
        resetDestList();
    }
 
    @Override
    public int getMeter() {
        return meter;
    }
 
    @Override
    public void movePoint(int point) {
        if (point == 0) {
            pointAdd(nowLocation);
            meter += nowLocation;
            nowLocation = 0;
            trashWeight = 0;
            return;
        }
        pointAdd(point - nowLocation);
        meter += point - nowLocation;
        nowLocation += point - nowLocation;
 
    }
 
    public boolean possibleCollect(int weight) {
        if (capacity < trashWeight + weight) {
            return false;
        }
        return true;
    }
 
    public boolean isFull() { // 비었을 때는 꽉차는지 체크
        if (trashWeight >= capacity) {
            return true;
        }
        return false;
    }
 
    public int collectTrash(int weight) {
        trashWeight += weight;
        return 0;
    }
}
cs
반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 12755번 수면 장애 자바로 풀어 본 짧은 글  (0) 2023.11.21
백준 14494번 다이나믹이 뭐예요? 자바로 풀어 본 짧은 글  (0) 2023.09.15
백준 1417번 국회의원 선거 자바로 풀어 본 짧은 글  (0) 2023.08.17
백준 골드5 달성!  (0) 2023.08.11
백준 2644번 촌수 계산 자바(BFS,DFS)로 풀어 본 짧은 글  (0) 2023.08.03
반응형

1417번 국회의원 선거

https://www.acmicpc.net/problem/1417

 

1417번: 국회의원 선거

첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같

www.acmicpc.net

Comment

자료구조를 활용하는 문제중에서 난이도가 쉬웠기에 여러가지 시도해보기 좋았던 문제같다.

처음엔 그냥 자료구조 클래스만 활용할까 하다가 객체도 같이 써보면 재밌지 않을까 해서 같이 사용해봤다

hint

우선순위 큐를 활용했다.

객체를 사용한다면 해당 객체에 Comparable를 상속받아야함

Solution

전체 입력값 자체가 적어서 시간은 볼 필요 없긴 할듯하다

우선순위 큐를 써봤는데 객체에서는 자동정렬을 계속 해주지 않는건지 처음 입력된 우선순위 큐 객체에서만 투표수를 가져가고 있었다. 때문에 이를 해결하기 위해 우선순위 큐에서 득표 수에 변경이 있을 때마다 큐에서 꺼냈다가 다시 넣어주는 형식으로 반복을 했다.

그래도 객체를 기준으로 우선순위 큐를 다루는게 은근 재밌었던 문제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.io.*;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class p1417 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int count = 0;
        int n = Integer.parseInt(br.readLine());
        Queue<Candidate> candiQ = new PriorityQueue<>(n+8);
 
        Candidate dasom = new Candidate(1, Integer.parseInt(br.readLine()));
 
        for(int i = 2; i < n+1;i++){
            int receveVote = Integer.parseInt(br.readLine());
            candiQ.offer(new Candidate(i, receveVote));
        }
 
        if(candiQ.isEmpty()){
            System.out.println(0);
            return;
        }
 
        //기호1번을 1등으로
        while (dasom.getReceveVote() <= candiQ.peek().getReceveVote()){
            candiQ.peek().voteControl(0);
            Candidate temp = candiQ.poll();
            candiQ.offer(temp);
            dasom.voteControl(1);
            count++;
        }
 
        System.out.println(count);
    }
}
 
 
/**
 * 후보자번호, 받은 득표수가 들어있는 후보객체
 * 우선순위큐를 위해 Comparable을 상속받음
 */
class Candidate implements Comparable<Candidate>{
    private final int number;
 
    private int receveVote = 0;
 
    Candidate(int number) {
        this.number = number;
    }
 
    Candidate(int number, int receveVote) {
        this.number = number;
        this.receveVote = receveVote;
    }
 
    @Override
    public int compareTo(Candidate o) {
        //receveVote 내림차순정렬
        return o.receveVote - receveVote;
    }
 
    public int getReceveVote() {
        return receveVote;
    }
 
    public int getNumber() {
        return number;
    }
 
    public void voteControl(int mode){
        if(mode == 0){
            receveVote--;
            return;
        }
        receveVote++;
 
    }
}
 
cs
 
반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 14494번 다이나믹이 뭐예요? 자바로 풀어 본 짧은 글  (0) 2023.09.15
백준 1680번 쓰레기 수거 자바로 풀어 본 짧은 글  (0) 2023.09.07
백준 골드5 달성!  (0) 2023.08.11
백준 2644번 촌수 계산 자바(BFS,DFS)로 풀어 본 짧은 글  (0) 2023.08.03
백준 2023번 신기한 소수 자바로 풀어 본 짧은 글  (0) 2023.07.25
반응형

다들 각잡고 준비하면 금방들 찍으시는거 같던데 저는 약 3개월이 걸렸네요...

안좋은 공부머리 억지로 풀어가면서 꾸준히 진행해서 도달했다는거에 만족하고 더 노력해야겠습니다.

참 기분좋은날 이네요

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 1680번 쓰레기 수거 자바로 풀어 본 짧은 글  (0) 2023.09.07
백준 1417번 국회의원 선거 자바로 풀어 본 짧은 글  (0) 2023.08.17
백준 2644번 촌수 계산 자바(BFS,DFS)로 풀어 본 짧은 글  (0) 2023.08.03
백준 2023번 신기한 소수 자바로 풀어 본 짧은 글  (0) 2023.07.25
백준 2583번 영역 구하기 자바로 풀어 본 짧은 글  (0) 2023.07.23
반응형

2644번 촌수 계산

https://www.acmicpc.net/problem/2644

 

2644번: 촌수계산

사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어

www.acmicpc.net

Comment

 DFS, BFS를  첫 입문할 때 하기 좋은 그래프 문제이다. 해당 문제는 DFS적으로 접근하면 Depth를 잘 활용할 수 있었는데, BFS를 활용해서 풀어볼 때 문제가 생겼었다. 직면했던 문제는 BFS에서는 Depth를 어떤 기준으로 체크할 수 있을까? 라는 고민을 많이 하게 한 문제였다.

hint

DFS, BFS 두가지 방법 모두 풀린다.

하지만 체감 난이도는 BFS가 더 어려웠던 것 같다.

Solution

  • DFS

재귀호출할 때 매개변수를 통해서 해당 깊이를 더해가며 풀어보니 잘 해결되었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.io.*;
import java.util.*;
 
public class Main {
 
    static boolean[] check;
    static ArrayList<Integer>[] al;
    static int n, m, start, target;
    static boolean flag;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        target = Integer.parseInt(st.nextToken());
 
        m = Integer.parseInt(br.readLine());
 
        al = new ArrayList[n + 1];
        check = new boolean[n + 1];
 
        for (int i = 0; i < n + 1; i++) {
            al[i] = new ArrayList<>();
        }
 
        int x, y;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
 
            al[x].add(y);
            al[y].add(x);
        }
        check[start] = true;
        dfs(start, 0);
        if (!flag) {
            System.out.println(-1);
        }
 
    }
 
    static void dfs(int n, int count) { //7 3
        if (n == target) { //도착하면 flag 변경 후 종료
            flag = true;
            System.out.println(count);
            return;
        } else if (flag) { //이미 찾았으면 더이상 dfs를 돌 필요 없음
            return;
        } else {
            for (int a : al[n]) {
                if (!check[a]) {
                    check[a] = true;
                    dfs(a, count + 1);
                }
            }
        }
    }
}
cs
  • BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.io.*;
import java.util.*;
 
public class Main {
 
    static boolean[] check;
    static ArrayList<Integer>[] al;
    static int n, m, start, target;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        target = Integer.parseInt(st.nextToken());
 
        m = Integer.parseInt(br.readLine());
 
        al = new ArrayList[n + 1];
        check = new boolean[n + 1];
 
        for (int i = 0; i < n + 1; i++) {
            al[i] = new ArrayList<>();
        }
 
        int x, y;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
 
            al[x].add(y);
            al[y].add(x);
        }
 
        bfs(start, target);
 
    }
 
    static void bfs(int start, int target) { // null을 활용해서 깊이 구분자를 생성
        int count = 0;
 
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        q.add(null);
        check[start] = true;
 
        while (!q.isEmpty()) {
            Integer now = q.poll();//null을 활용하기 위해 Integer로 
 
            if(now == null) {//null을 만날 때마다 깊이가 깊어짐 count++
                if(!q.isEmpty()) {
                    q.add(null);
                    count++;
                }
            }else {
                for (int y : al[now]) {
                    if (!check[y]) {
                        check[y] = true;
                        if (y == target) { // bfs깊이에 따라서 체크 후 해당 깊이 출력
                            System.out.println(count + 1);
                            return;
                        }
                        q.add(y);
                    }
                }
            }
        }
        System.out.println(-1);
    }
}
cs

내가 만질 때는 null을 Queue에 넣어서 구분자로 생각하고 null을 만날 때마다 count가 1씩 증가하도록 구현했었는데, 좀 더 직관적인 방법이 좋았을거라 생각했고, 스터디를 진행하는 다른 사람이 푼 것을 봤을 때 distance라는 배열을 만들어서 해당 값을 누적되게 구현했는데 더 좋은 방법 같았다.

어쨌든 그래프에서 DFS, BFS를 둘 다 사용해보기에 좋은 문제였던 것 같다!

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 1417번 국회의원 선거 자바로 풀어 본 짧은 글  (0) 2023.08.17
백준 골드5 달성!  (0) 2023.08.11
백준 2023번 신기한 소수 자바로 풀어 본 짧은 글  (0) 2023.07.25
백준 2583번 영역 구하기 자바로 풀어 본 짧은 글  (0) 2023.07.23
알고리즘 근황  (0) 2023.07.23
반응형

2023번 신기한 소수

https://www.acmicpc.net/problem/2023

 

2023번: 신기한 소수

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수

www.acmicpc.net

Comment

 처음에는 소수판별이기 때문에 이전에 배워뒀던 에라토스테네스의 체를 사용하려고 했다. 하지만 이 문제는 메모리제한이 4MB에 N의 범위가 8 즉 최대 10,000,000 천만의 범위이기 때문에 자바의 데이터 최소단위 byte - boolean크기: 1byte로 지정되었을 때 에토체의 boolean배열만 어림잡아 100mb가 넘게된다 때문에 기각.

일반 소수판별 메서드를 생성해서 처리했다.

hint

DFS, 소수판별을 해야한다

Solution

 최종적으로 가지치기 등등 다양하게 하니까 속도가 좀 빨라졌다. 1,3,5,7,9가 아닌 0~10까지 돌렸을 때는 속도가 좀 느렸었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.io.*;
import java.util.*;
 
 
public class Main {
    static int[] firstPrime = {2, 3, 5, 7};
    static int n;
    static ArrayList<Integer> magicPrime = new ArrayList<>();//신기한 소수를 담을 리스트
 
//    static int count = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
//        int jari = (int)Math.pow(10, n); // 끝자리까지보기
 
        //4메가면 에토체가 가능한가?
        // 1000000 백만에 1M 4백만이면 끝나는데 안된다.
        //나중에 에토체로 구현되나만 체크해보면 재밌을듯
 
        //한자릿수는 배열을만들자 이걸 가지고 시작
        //이걸로 조합을 다하면 그건 브루트포스아닌가?
        //그래서 DFS느낌으로 가는건가?
 
        //슈도흐름을 생각해보자.
        //1. 한자릿수 prime등록 이후는 전부됨......
        //2. 두번째부터 그 수를 붙여서 prime인지 확인 (n을 입력받은 중단점까지)
        //2_1. DFS를 활용, String에 붙여서 다음 DFS로 이동
        //2_2. 백트래킹도 무조건 넣어야할듯? 한 Depth에서 같은 소수를 여러번 반복해야함
        //3. 중단점을 찾았으면 그 수를 리스트에 추가
        //4. 리스트에 추가된거 출력!
 
        for (int i = 0; i < firstPrime.length; i++) {
            dfs(String.valueOf(firstPrime[i]), 1);
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < magicPrime.size(); i++) {
            if(i == magicPrime.size()-1){
                sb.append(magicPrime.get(i));
            }else {
                sb.append(magicPrime.get(i) + "\n");
            }
        }
        System.out.print(sb);
 
    }
 
    static void dfs(String s, int count) {
        if (count == n && isPrime(Integer.valueOf(s))) {//중단점
            magicPrime.add(Integer.valueOf(s));
        }
        if (isPrime(Integer.valueOf(s))) {
            for (int i = 1; i < 10; i += 2) {
                    dfs(s.concat(String.valueOf(i)), count + 1);
            }
        }
    }
 
    static boolean isPrime(int isPrimeNum) {
        for (int i = 2; i <= (int) Math.sqrt(isPrimeNum); i++) {
            if (isPrimeNum % i == 0) {
                return false;
            }
        }
        return true;
    }
}
cs
반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 골드5 달성!  (0) 2023.08.11
백준 2644번 촌수 계산 자바(BFS,DFS)로 풀어 본 짧은 글  (0) 2023.08.03
백준 2583번 영역 구하기 자바로 풀어 본 짧은 글  (0) 2023.07.23
알고리즘 근황  (0) 2023.07.23
백준 11822번 Document 자바로 풀어 본 짧은 글  (0) 2023.06.08
반응형

2583번 영역 구하기

문제 링크 : https://www.acmicpc.net/problem/2583

 

2583번: 영역 구하기

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오

www.acmicpc.net

 

Comment

DFS공부를 시작하면서 만나게 된 문제다. 처음 떠올랐던 아이디어는 이전에 풀었던 색종이 문제처럼 먼저 구현해둔 맵 배열에 칠하고 나머지 갈라진 부분을 DFS로 채워나가자고 생각하고 접근했다.

hint

  • Map을 칠하고 구분된 빈곳을 돌 때마다 count를 해주면 될듯?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.io.*;
import java.util.*;
 
public class Main {
 
    static boolean map[][];
    static int count = 0;
 
    static int n, m, k;
 
    static int rectangleSize = 0;
    static ArrayList<Integer> rectangleSizeList = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
 
        map = new boolean[m][n];
 
        for(int i = 0; i < k; i++){
            st = new StringTokenizer(br.readLine());
            drawRectangle(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())
                    ,Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
        }
 
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(!map[i][j]){
                    count++;
                    dfs(i, j);
                    rectangleSizeList.add(rectangleSize);
                    rectangleSize = 0;
                }
            }
        }
        Collections.sort(rectangleSizeList);
        StringBuilder sb = new StringBuilder();
        sb.append(count).append("\n");
 
        for(int i = 0; i < rectangleSizeList.size(); i++){
            sb.append(rectangleSizeList.get(i) + " ");
        }
        System.out.println(sb);
    }
 
    static void dfs(int x, int y){
        if(x >= 0 && y >= 0 && x < m && y < n) {
            if (!map[x][y]) {
                map[x][y] = true;
                rectangleSize++;
                dfs(x + 1, y);
                dfs(x - 1, y);
                dfs(x, y + 1);
                dfs(x, y - 1);
            }
        }
    }
    static void drawRectangle(int x1, int y1, int x2, int y2){
        for(int i = y1; i < y2; i++) {
            Arrays.fill(map[i], x1, x2, true);
        }
    }
}
cs

 

Arrays.fill 메서드를 활용해보고 싶어서 사용했고, fill메서드를 안쓰고 각 좌표별로 true체크를 한 후에 칠했으면 조금 더 효율이 좋을 것 같다.

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 2644번 촌수 계산 자바(BFS,DFS)로 풀어 본 짧은 글  (0) 2023.08.03
백준 2023번 신기한 소수 자바로 풀어 본 짧은 글  (0) 2023.07.25
알고리즘 근황  (0) 2023.07.23
백준 11822번 Document 자바로 풀어 본 짧은 글  (0) 2023.06.08
백준 21771 가희야 거기서 자는 거 아니야 자바로 풀어 본 짧은 글  (0) 2023.05.31
반응형

 

백준을 건든지는 좀 됐는데 요 최근 실력을 끌어올리고 싶어서

하루 1문제이상 풀이를 목표로 최대한 노력해왔고, 현재 연속 9주 풀이에 도달했다.

수준 낮은 문제더라도 억지로 계속 해왔더니 실력이 좀 늘었다는게 느껴져서 뿌듯하다.

 

일기는 끝이고 앞으로는 약간 재밌는 문제가 있고, 시간 여유가 있으면 다시 포스팅을 신경써서 해보려고 합니다.

공부하는 모두 파이팅!!🔥🔥🔥🔥🔥🔥🔥

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 2023번 신기한 소수 자바로 풀어 본 짧은 글  (0) 2023.07.25
백준 2583번 영역 구하기 자바로 풀어 본 짧은 글  (0) 2023.07.23
백준 11822번 Document 자바로 풀어 본 짧은 글  (0) 2023.06.08
백준 21771 가희야 거기서 자는 거 아니야 자바로 풀어 본 짧은 글  (0) 2023.05.31
백준 13717 포켓몬Go 자바로 풀어 본 짧은 글  (0) 2023.05.25
반응형

인텔리제이 하단에 git 관련된 버튼이 있습니다. 단축키 : (Alt + 9)

해당 버튼을 누르면 각 브랜치별로 표시가 되어 있는데, 본인이 수정하려고 하는 브랜치에 들어가서 커밋 목록을 확인하신다면 커밋메시지 목록이 나와있습니다.

해당 커밋 메시지 우클릭 후 커밋 메시지 편집 버튼을 통해서 손쉽게 변경이 가능합니다..!

 

 

커밋 삭제 : 이전 커밋단계로 돌아가게 됩니다. 주의할 점은 커밋 하기 이전의 내용은 날아갈 수 있다는 것을 확실하게 인지 해두셔야 합니다

커밋 실행 취소 : git add까지 했던 staged까지 보내둔 상태로 변경합니다

커밋 되돌리기 : 커밋메시지를 남기며 이전 커밋상태로 변경해줍니다.

이번에 이 부분을 알게되면서 매번 깃 배시만 사용하면서 힘들었는데 이런 간단한 기능들은 ide상에서 편하게 수정할 수 있어서 참 편하네요

반응형
저작자표시 비영리 변경금지

'공부 > IT관련' 카테고리의 다른 글

서버란 무엇인가요?  (0) 2023.02.22
인터넷은 어떻게 작동되나요?  (0) 2023.02.22
윈도우 단축키 관련  (0) 2023.02.21

+ Recent posts

티스토리툴바