백준 10527번: Judging Troubles

2021/04/01

문제

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

코드

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());

    Map<String, Boolean> isDuplicate = new HashMap<>();
    Map<String, Integer> domJudge = new HashMap<>();

    for (int i = 0; i < n; i++) {
        String input = br.readLine();

        if (!isDuplicate.containsKey(input)) {
            isDuplicate.put(input, false);
        }

        domJudge.put(input, domJudge.getOrDefault(input, 0) + 1);
    }

    Map<String, Integer> kattis = new HashMap<>();

    for (int i = 0; i < n; i++) {
        String input = br.readLine();

        if (isDuplicate.containsKey(input)) {
            isDuplicate.put(input, true);
        }

        kattis.put(input, kattis.getOrDefault(input, 0) + 1);
    }

    List<Map.Entry<String, Integer>> entries1 = new ArrayList<>(domJudge.entrySet());
    List<Map.Entry<String, Integer>> entries2 = new ArrayList<>(kattis.entrySet());

    entries1.addAll(entries2);
    Collections.sort(entries1, (e1, e2) -> {
        if (e1.getKey().compareTo(e2.getKey()) > 0) {
            return 1;
        } else if (e1.getKey().compareTo(e2.getKey()) < 0) {
            return -1;
        } else {
            return Integer.compare(e1.getValue(), e2.getValue());
        }
    });

    int answer = 0;
    Set<String> set = new HashSet<>();
    for (int i = 0; i < entries1.size(); i++) {
        Map.Entry<String, Integer> entry = entries1.get(i);

        if (isDuplicate.getOrDefault(entry.getKey(), false) && set.add(entry.getKey())) {
            answer += entry.getValue();
        }
    }

    System.out.println(answer);
}

흐름

우선 이 문제는 domJudge와 kattis가 순서대로 n만큼씩 입력 받는 문제다.

예제를 보며 얘기하면

5
correct
wronganswer
correct
correct
timelimit
wronganswer
correct
timelimit
correct
timelimit

이렇게 되어 있을 때 위에 다섯 줄은 domJudge에서 채점한 결과고, 그 아래 다섯 줄은 kattis 채점한 결과다.

이걸 생각하고 프로그램을 작성하면

우선 양 쪽에서 채점된 결과들 중에 작은 녀석의 값을 골라야 하므로 채점 결과를 Key로 하는 Map을 만들고
n 만큼 돌면서 domJudge의 채점 결과를 저장하는데 이 때 처음나온 채점 결과는 Map에 false로 저장하고, 이전에 이미 나온 결과는 +1 해준다.
그 후 다시 n만큼 돌면서 kattis의 채점결과를 저장하는데
이 때는 전에 domJudge에서 나온 채점 결과 인지 확인해야 하므로 중복을 체크하기 위해 만든 Map에 채점 결과가 존재하면 그 key의 값을 true로 변경시켜서 양 쪽에서 모두 나온 결과 임을 저장한다.
그 후 양 쪽에서 모두 나온 채점 결과들 중 작은 값들을 더하기 위해
두 Map을 리스트로 변환 후 합쳐서 key와 value로 sorting 한다.
그 후 합친 리스트를 반복하면서..
채점 결과가 양 쪽 모두에서 나온 녀석이면서 이전에 더한 key가 아니라면 쭉 더하고
출력하고 끝낸다.

결과

다른 분의 코드

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String line = br.readLine().trim();
    int n = Integer.parseInt(line);
    Map<String, Integer> map = new HashMap<>();
    for(int i = 0; i < n; i++){
        String dom = br.readLine();
        map.put(dom, map.getOrDefault(dom, 0) + 1);
    }
    int cnt = 0;
    for(int i = 0; i < n; i++){
        String kattis = br.readLine();
        if(map.containsKey(kattis) && map.get(kattis) > 0){
            cnt++;
            map.put(kattis, map.get(kattis) - 1);
        }
    }
    System.out.println(cnt);
}

나 처럼 바보 같이 Map을 여러 개 쓰지 않고 하나의 맵에 +1, -1로 해서 겹치는 결과 인지 아닌지 판단했다.
나는 왜 이렇게 생각하지 못했을까? 다른 곳에서도 흔히 쓰이는 방식인데
오늘도 역시 반성해본다…

댓글 공유

백준 1417번: 국회의원 선거

2021/03/30

문제

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

코드

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());

    LinkedList<Integer> queue = new LinkedList<>();
    int dasom = Integer.parseInt(br.readLine());
    for (int i = 0; i < n-1; i++) {
        int input = Integer.parseInt(br.readLine());

        if (dasom <= input) {
            queue.offer(input);
        }
    }

    Collections.sort(queue);

    int answer = 0;
    for (; !queue.isEmpty() && queue.peekLast() >= dasom; answer++) {
        if (queue.peek() < dasom) {
            queue.poll();
        }

        queue.offer((queue.pollLast()-1));
        dasom++;

        Collections.sort(queue);
    }

    System.out.println(answer);
}

흐름

다솜이는 기호 1번이므로 첫 번째 입력을 다솜이의 표로 저장한다.
우선순위 큐로 사용하기 위해 list에 입력들을 저장하는데 다솜이 보다 작을 경우엔 문제의 답과 상관이 없으므로 다솜이의 표보다 적은 표는 큐에 저장하지 않는다.
우선순위 큐로서 동작하게 하기 위해 반복 전에 큐를 한번 정렬시켜준다.
그 후엔 큐가 비거나, 큐의 가장 큰 값이 다솜이가 될 때까지 반복한다.
반복하면서 큐의 맨 앞이 다솜이보다 작다면, 이제 그 사람은 다솜이가 재낀 것 이므로 큐에서 빼주고,
제일 표가 많은 놈한테서 표 하나를 뻇어서 다솜이가 가져가면 되므로 큐의 마지막 값에서 -1 빼서 다시 큐에 넣어준다.
그리고 제일 표가 많은 놈에게 뺏은 표를 다솜이에게 줬으므로 다솜이의 값을 1 증가시키고
우선순위 큐 처럼 동작 할 수 있게 큐를 다시 정렬 시킨다.
반복된 횟수를 출력하면 끝.

결과

여담

반복문에서 소팅을 하기 때문에 시간 초과가 날 것으로 예상했는데 수가 적은 문제라 그런지 무사히 통과되어 참 다행이다…

댓글 공유

백준 1406번: 에디터

2020/12/14

문제

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

코드

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

    LinkedList<Character> list = new LinkedList<>();
    for (char c : input) {
        list.add(c);
    }

    ListIterator<Character> it = list.listIterator();
    while (it.hasNext()) {
        it.next();
    }

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

    while (n-- > 0) {
        String command = br.readLine();

        switch (command) {
            case "L" :
                if (it.hasPrevious()) {
                    it.previous();
                }
                break;
            case "D" :
                if (it.hasNext()) {
                    it.next();
                }
                break;
            case "B" :
                if (it.hasPrevious() && !list.isEmpty()) {
                    it.previous();
                    it.remove();
                }
                break;
            default:
                it.add(command.charAt(2));
                break;
        }
    }

    StringBuilder sb = new StringBuilder();
    for (char c : list) {
        sb.append(c);
    }

    System.out.println(sb);
}

이 문제는 로직보다 걸리는 시간이 문제였다.
처음엔 LinkedList를 그대로 사용해 add, remove를 했지만 시간초과로 인해 ListIterator을 이용해 해결했다.

ListIterator

List를 양방향으로 탐색하고, 루프 중에 리스트를 수정하고, 리스트에서 현재 위치를 가져올 수 있다.
커서는 previous()로 리턴되는 원소와 next()로 리턴되는 원소 사이에 존재한다.

1 2	Element(0) Element(1) Element(2) ... Element(n-1) cursor positions: ^ ^ ^ ^ ^

remove()와 set()를 호출해도 커서의 위치는 움직이지 않는다.
remove() 호출 시 next()혹은 preivous()에 의해 리턴된 마지막 요소를 리스트에서 제거한다.

case "B" :
        if (it.hasPrevious() && !list.isEmpty()) {
            it.previous();
            it.remove();
        }
        break;

결과

참고 사이트

댓글 공유

백준 10527번: Judging Troubles

문제

코드

흐름

결과

다른 분의 코드

백준 1417번: 국회의원 선거

문제

코드

흐름

결과

여담

백준 1406번: 에디터

문제

코드

ListIterator

결과

참고 사이트

Junggu Ji