IT Docs

문제 링크 : https://www.acmicpc.net/problem/2531
등급 : Silver I

프로세스

1. 내가 먹을 수 있는 초밥의 개수만큼 먹는다.
2. 처음 먹은 초밥(원포인트), 마지막 먹은 초밥(투 포인트)을 기준으로 잡는다.
3. 처음 먹은 초밥을 버리고, 먹을 초밥을 삽입한다.
4. 3번을 반복하면서 시작 지점 직전까지 초밥을 먹는다.
   1. 4개의 초밥을 먹을 수 있을 때 1, 2, 3, 4, 5, 6, 7, 8의 초밥이 있다고 가정한다.
   2. 초밥을 먹을 수 있는 조합은 1234, 2345,... 8123까지 먹을 수 있다.
5. 최대 먹을 수 있는 접시를 한번 먹을 때마다 쿠폰으로 먹을 수 있는 접시가 있는지 파악한다.
6. 3~5번을 반복하여 가장 많이 먹을 수 있는 초밥의 가지 수를 찾는다.

문제 핵심

이 문제의 핵심은 내가 먹을 수 있는 초밥의 가짓수를 찾는 것이어서 내가 먹은 초밥의 가지수를 중복 제거하는 게 필요하다.

일반적인 stream으로 distinct하거나 for문을 돌려 중복 제거하면 시간 초과가 발생한다.

그래서 HashMap을 이용하여 초밥을 먹을때 이미 먹은 초밥인지 체크하여 중복을 제거한다.

아래와 같이 소스를 공유합니다.

public class Main {

    public static int[] sushis;
    public static int nu, ma, di, cp;
    public static int max = Integer.MIN_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] commend = br.readLine().split(" ");

        nu = Integer.parseInt(commend[0]);
        ma = Integer.parseInt(commend[1]);
        di = Integer.parseInt(commend[2]);
        cp = Integer.parseInt(commend[3]);

        sushis = new int[nu];
        Map<Integer, Integer> eat = new HashMap<>();

        eat.put(cp, 1);

        for(int i = 0; i < nu; i++) {
            int sushi = Integer.parseInt(br.readLine());
            sushis[i] = sushi;
            if(i < di) {
                if(eat.containsKey(sushi)) {
                    eat.put(sushi, eat.get(sushi)+1);
                }else {
                    eat.put(sushi, 1);
                }
            }
        }

        for(int i = di; i < sushis.length + di; i++) {
            counting(eat.size());

            int e = sushis[Math.abs(di-i)];

            if(eat.containsKey(e) && eat.get(e) > 1) {
                eat.put(e, eat.get(e)-1);
            }else {
                eat.remove(e);
            }

            int sushi = sushis[(i >= sushis.length) ? Math.abs(sushis.length - i) : i];

            if(!eat.containsKey(sushi)) {
                eat.put(sushi, 1);
            }else {
                eat.put(sushi, eat.get(sushi)+1);
            }
        }

        System.out.println(max);
    }

    public static void counting(int num) {
        max = Math.max(num, max);
    }
}

문제 링크 : https://www.acmicpc.net/problem/1374
등급 : Gold IV

문제 해설

강의의 개수가 최대 100,000개이고 강의 시간은 최대 10억이다. 이 문제는 모든 강의를 정렬하면 시간 초과가 발생하는 문제이다. 그래서 모든 강의를 정렬하지 않고 이전 강의의 끝 시간과 다음 강의의 시작 시간을 비교하여 로직을 구현한다. 아래는 로직의 순서를 나열하였다.

1. 강의의 시작 시간 순으로 정렬한다.
2. 첫 강의가 끝나고 다음 강의가 시작된다면 다음 강의를 제거한다.
3. 첫 강의가 끝나기 전에 강의가 시작된다면 강의실을 추가하고 강의실 개수를 갱신한다.
4. 2번과 3번을 모든 강의가 진행될 때까지 반복한다.

아래와 같이 소스를 공유합니다.

public class 강의실 {
    public static class Node {
        int o, s, e;
        Node(int o, int s, int e) {
            this.o = o;
            this.s = s;
            this.e = e;
        }
    }
    public static List<Node> list = new ArrayList<>();
    public static PriorityQueue<Integer> que = new PriorityQueue<>();
    public static Comparator<Node> comparator = new Comparator<>() {
        @Override
        public int compare(Node o1, Node o2) {
            return Integer.compare(o1.s, o2.s);
        }
    };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int o = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            list.add(new Node(o, s, e));
        }

        Collections.sort(list, comparator);

        int max = Integer.MIN_VALUE;

        for(int i = 0; i < n; i++) {
            while(!que.isEmpty() && que.peek() <= list.get(i).s) {
                que.poll();
            }

            que.add(list.get(i).e);
            max = Math.max(max, que.size());
        }

        System.out.println(max);
    }
}

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

문제 풀이

1. 각 별들의 이동 경로(양방향)를 기록한다.
2. 스피카 별의 주변의 별들의 특성대로 이동 경로의 개수를 확인하여 스피카를 찾는다.
   1. 이동 경로가 3개인 별
   2. 이동 경로가 2개인 별
   3. 이동 경로가 1개인 별

아래와 같이 소스를 공유합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static int ans = 0;
    public static List<List<Integer>> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str = "";

        for(int i = 0; i <= 12; i++) list.add(new ArrayList<>());
        while(!(str = br.readLine()).equals("")) {
            StringTokenizer st = new StringTokenizer(str, " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            list.get(s).add(e);
            list.get(e).add(s);
        }

        for(int i = 0; i < list.size(); i++) {
            boolean first = false, second = false, third = false;
            if(list.get(i).size() == 3) {
                for(int j = 0; j < 3; j++) {
                    int side = list.get(list.get(i).get(j)).size();
                    
                    if(!third && side == 3) third = true;
                    if(!second && side == 2) second = true;
                    if(!first && side == 1) first = true;
                }
            }

            if(third && second && first) ans = i;
        }

        System.out.println(ans);
    }
}

처음 문제를 접했을 때 예제 입력을 보고 단방향으로 진행되는 문제라고 생각했다.

나에게 오는 별이 2개, 나가는 별이 1개를 체크하는 로직을 구현했으나 틀렸다.

최근에 올라온 문제라서 다른 사람들이 구현한 로직을 볼 수 없었다.

그래서 스터디 원에게 물어보니 이 문제는 단방향이 아닌 양방향이라는 힌트를 주었다.

양방향이라는 말을 듣고 다시 문제를 풀어 해답을 찾았다.

이 문제에는 방향에 대한 명확한 제시가 없다.

당연히 단방향이 아니면 양방향으로 문제를 풀어봤어야 했는데 판단을 잘못해 문제를 한 번에 풀지 못하였다.

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

문제 풀이

1. 음수의 책의 거리와 양수의 책의 거리를 각 리스트에 삽입한다.
2. 절댓값으로 가장 멀리 있는 책의 위치를 찾는다.
3. 각 리스트를 내림차순으로 정렬한다.
4. 옮길 수 있는 최대 책의 수만큼 책을 들고 가장 멀리 있는 책의 위치를 계산한다.
5. 옮길 수 있는 최대 책의 수 보다 작은 수의 책이 남았을 경우 남아 있는 책 중 가장 멀리 있는 책의 위치를 계산한다.
6. 계산된 거리에서 가장 멀리 있는 책의 위치를 빼준다.

아래와 같이 소스 공유 합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 도서관 {
    public static int max, num, res, farthest;
    public static List<Integer> plusList = new ArrayList<>();
    public static List<Integer> minusList = new ArrayList<>();
    // 음수와 양수 구분하여 정렬
    public static Comparator<Integer> compare = new Comparator<Integer>() {

        @Override
        public int compare(Integer o1, Integer o2) {
            if(o1 > 0 && o2 > 0) {
                return (o1 > o2) ? -1:(o1 == o2) ? 0:1;
            }

            return (o1 > o2) ? 1:(o1 == o2) ? 0:-1;
        }
    };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] strs = br.readLine().split(" ");

        num = Integer.parseInt(strs[0]);
        max = Integer.parseInt(strs[1]);
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        while(st.hasMoreTokens()) {
            int val = Integer.parseInt(st.nextToken());
            if(val > 0) plusList.add(val);
            if(val < 0) minusList.add(val);
            // 가장 먼 거리를 구하여 모든 계산이 끝난 후 뺄셈을 한다.
            farthest = Math.max(farthest, Math.abs(val));
        }

        Collections.sort(plusList, compare);
        Collections.sort(minusList, compare);

        int cnt = 0;

        for(int i = 0; i < plusList.size(); i += cnt) {
            // 이동 횟수 초기화
            cnt = 0;
            int select = 0;
            for(int j = 0; j < max; j++) {
            	// 최대로 옮길 수 있는 책의 수 보다 작은 개수가 남았을 경우
                if(i + j < plusList.size()) {
                    select = Math.max(select, Math.abs(plusList.get(i + j)));
                    cnt++;
                }
            }
            res += select * 2;
        }

        for(int i = 0; i < minusList.size(); i += cnt) {
            // 이동 횟수 초기화
            cnt = 0;
            int select = 0;
            for(int j = 0; j < max; j++) {
            	// 최대로 옮길 수 있는 책의 수 보다 작은 개수가 남았을 경우
                if(i + j < minusList.size()){
                    select = Math.max(select, Math.abs(minusList.get(i + j)));
                    cnt++;
                }
            }
            res += select * 2;
        }

        System.out.println(res - farthest);
    }
}

그리디 문제에 대한 경험이 부족하여 스터디에서 그리디 문제를 풀자고 요청하였다.
스터디를 진행하는 3시간 동안 문제를 풀지 못하였다. 역시나 어려웠다.
그래서 힌트를 받았지만 받은 풀이를 그대로 구현하기는 싫었다.
지금 당장 풀지 못하더라도 내가 스스로 고민하고 내가 생각한 로직대로 풀고 싶었고 그 노력이 이 문제를 내 것으로 만들어줄 것이라고 믿었다.
스터디 끝나고 집에 돌아와 반례를 보고 나서 문제를 맞힐 수 있었다.

부족한 실력 때문에 자존심이 많이 상해서 주저리 적었습니다.

읽어주셔서 감사합니다.