모각코 2회차 활동 내용 정리

2023.7.14 모각코 2회차 목표 

백준 알고리즘 문제 풀고 블로그에 정리하기

 

https://ethereal-coder.tistory.com/48

백준 [자바 java] 14719 : 빗물

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

14719번: 빗물

 

풀 문제 찾다가 우리학교 문제 발견해서 풀어봤어요.

처음 양 옆에가 벽인 것만 물을 채웠는데 그럼 절대 안되더라구요.

그래서 for문을 이용해서 가로로 한 줄씩 왼쪽부터 탐색하면서 벽이 나오면 다음 벽이 나올 때까지 세고.. 뭐 이런 알고리즘을 생각했는데 너무너무 복잡했어요.

생각해보니까 아래부터 가로로 한 줄씩 벽 사이의 간격을 재면 되더라구요!
그래서 stack을 이용해서 벽이 있는 곳의 위치를 넣고 차례로 빼서 간격을 세어주었답니다.

근데 제 코드에 한가지 문제점이 있는데, 제가 수를 입력받고 배열을 벽으로 채우는 과정에서 뭔가 잘못했는지 웅덩이가 뒤집어진(?) 형태가 되어버렸어요. 근데 문제푸는데 지장은 없어서(어차피 한 줄씩 보니까) 그냥 풀었습니다!

 

 

 

풀이코드

 

import java.util.*;
import java.io.*;
import java.math.*;


public class Main {



    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int arr[][] = new int[n][m];

        st = new StringTokenizer(br.readLine());

        for(int i = 0;i<m;i++){
            int k = Integer.parseInt(st.nextToken());

            for(int j = k-1 ;j>=0;j--){
                arr[j][i] = 1;
            }
        }

        

        int ans = 0;

        Stack<Integer> s = new Stack<>();

        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(arr[i][j] == 1){
                    s.push(j);
                }
            }

            if(s.isEmpty()) continue;
            int front = s.pop();

            while(s.isEmpty()!= true){
                int k = s.pop();
                ans += Math.abs(k-front)-1;
                front = k;
            }
        }

        System.out.println(ans);




    }
}

 

 

 

https://ethereal-coder.tistory.com/49

백준 [자바 java] 1461 : 도서관

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

1461번: 도서관

사실 한번에 통과하긴 했지만 4번은 갈아엎었던 것 같다.

처음에는 그냥 음수, 양수 나누어서 가장 끝에서부터 차례로 한번에 들을 수 있는 책 만큼 건너뛰면서 세면 되지 않을까라고 생각했지만 다시 0으로 돌아오지 않아도 된다는 조건 때문에 실패했다.

그리고 받는 수를 다 우선순위큐에 넣어서 차례로 빼려고 했지만 그렇게 하면 양수부분에서는 절댓값이 작은 부분부터 탐색해서 옳은 답이 나오지 않는다. 

최종적으로 지금 한 대로 양수는 양수대로 음수는 음수대로 절댓값이 큰 순서대로 탐색하고 두 값들을 우선순위큐(내림)으로 처리했지만, 모든 수가 양수, 음수인 경우는 고려하지 않아 테케에 통과하지 못했었다.

 

앞으로 주의할 점 : 두 과정으로 나누는 방식을 사용했을 때 하나의 과정만 사용해야 하는 경우 꼭 고려하기

 

풀이코드

import java.util.*;
import java.io.*;
import java.math.*;


public class Main {



    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());


        PriorityQueue<Integer> q2 = new PriorityQueue<>(Collections.reverseOrder());

        int[] arr = new int[n];

        for(int i =0;i<n;i++) {
            int k = Integer.parseInt(st.nextToken());
            arr[i] = k;
        }

        Arrays.sort(arr);

        int ans = 0;

        int now = 0;

        while(true){
            if(arr[0] > 0) break;
            //System.out.println(arr[now]);
            q2.offer(Math.abs(arr[now]));
            now += m;
            if(now >= n || arr[now] >= 0) break;
        }

        now = n-1;



        while(true){
            if(arr[n-1] < 0) break;
            //System.out.println(arr[now]);
            q2.offer(Math.abs(arr[now]));
            now -= m;
            if(now < 0 || arr[now] < 0) break;
        }

        if(q2.isEmpty() != true) ans += q2.poll();

        while(q2.isEmpty() != true){
            ans += (q2.poll())*2;
        }

        System.out.println(ans);

    }
}

 

느낀점 

앞으로 알고리즘을 더 빠르게, 효율적으로 풀기 위해 알고리즘 개념을 많이 알아야 할 것 같고 감을 잃지 않게 꾸준하게 풀어야겠다.