IT Docs

문제 링크 : https://www.acmicpc.net/problem/1789
문제 등급 : Silver V

문제 해결 로직

1. 찾고자 하는 값보다 클 때까지 1부터 n까지 더하면서 count 한다.
2. count - 1을 하여 더한 개수를 구한다.
   1. n이 20일 때, 1, 2, 3, 4, 5, 6으로 21을 구한다.
   2. count는 6이 된다.
   3. 하지만 n과 21은 다르기 때문에 하나의 값을 빼주어야 하는데 n과 21의 차가 더한 값에 있음으로 count에서 1을 빼준다.

이 문제를 보고 백트래킹으로 문제를 풀려고 하였다. 하지만 너무 깊게 생각했다.

너무 오랜 시간 붙잡고 있어도 오기일뿐 효율이 안 나기 때문에 문제의 풀이를 보았다.

문제의 풀이를 보고 무릎을 탁 쳤다.

전혀 생각해보지 못한 풀이였다.

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

public class 수들의 합 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();
        long sum = 0, cnt = 0;
        for (int i = 1; i <= n; i++) {
            if(sum > n) break;
            sum += i;
            cnt++;
        }

        System.out.println(cnt-1);
    }
}

문제 링크 : https://www.acmicpc.net/problem/9012
문제 등급 : Silver IV

문제 해결 로직

1. 문자열을 하나씩 Que에 넣는다.
2. Que에 넣은 문자열과 앞으로 넣을 문자열을 비교하여 합이 맞는 괄호 인지 체크한다.
3. 합이 맞는 괄호라면 que의 최상단 값을 제거한다.
4. 합이 맞지 않는 괄호라면 que에 삽입한다.
5. 문자열의 길이만큼 반복문이 다 돌고 que에 남아있는 문자가 있는지 확인하고 VPS인지 파악하여 결과를 출력한다.

이 문제는 타자 검정 같은 기본적인 문제이다. 지금 이 문제를 푸는 데에도 5분이 안 걸린 것 같다. 하지만 같은 유형의 문제가 기업 코딩 테스트에 나왔는데 결국 해결해내지 못했다. 응용이 안됬던 것일까? 긴장을 한 것일까?

푸념을 하며 나의 실수를 채찍질한다. 다음에는 이런 실수를 하지 않기를 빌며..

이 글을 보는 여러분들은 저와 같은 실수를 하지 않기를... 바랍니다.

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

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

        for(int i = 0; i < n; i++) {
            String[] s = br.readLine().split("");
            Queue<String> que = new LinkedList<>();
            for (int j = 0; j < s.length; j++) {
                if(que.isEmpty()) {
                    que.add(s[j]);
                }else {
                    if(que.peek().equals("(") && s[j].equals(")")) {
                        que.poll();
                    }else {
                        que.add(s[j]);
                    }
                }
            }
            if(que.isEmpty()) sb.append("YES").append("\n");
            else sb.append("NO").append("\n");
        }

        System.out.println(sb.toString());
    }
}

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

문제 해결 로직

1. 서류 순위와 면접 순위 중 서류 순위를 기준으로 오름차순으로 정렬한다.
2. 첫 번째 면접자는 서류 순위 중 1등이기 때문에 합격이다.
3. 첫 번째 면접자의 면접 순위를 기준으로 면접 순위가 작은 면접자를 찾아 합격시킨다.
4. 면접 순위가 작은 면접자를 기준으로 보다 작은 면접 순위를 가진 면접자를 합격시킨다.
5. 4번을 반복하여 합격자의 수를 카운트한다.

이 문제의 핵심은 문제를 잘 읽고 해석하는 것이었다.

다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙에서 많이 헷갈렸다.

처음에는 서류 순위 기준으로 정렬 후 바로 다음 지원자와 비교하여 합격을 판단하였다.

하지만 잘 못된 로직이었고 합격한 사람을 기준으로 더 나은 성적을 가진 지원자가 합격하는 것이었다.

구현 자체는 어렵지 않았으나 문제를 해석하는 게 어려웠다.

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

public class 신입사원 {
    public static class Node {
        int g1, g2, sum;
        Node(int g1, int g2, int sum) {
            this.g1 = g1;
            this.g2 = g2;
            this.sum = sum;
        }
    }
    public static Comparator<Node> compare = new Comparator<>() {
        @Override
        public int compare(Node o1, Node o2) {
            return Integer.compare(o1.g1, o2.g1);
        }
    };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        for (int i = 0; i < n; i++) {
            int t = Integer.parseInt(br.readLine());
            List<Node> list = new ArrayList<>();
            for (int j = 0; j < t; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                int g1 = Integer.parseInt(st.nextToken());
                int g2 = Integer.parseInt(st.nextToken());
                list.add(new Node(g1, g2, g1+g2));
            }

            list.sort(compare);

            int cnt = 1;
            int c = list.get(0).g2;
            for (int j = 1; j < list.size(); j++) {
                if(c > list.get(j).g2) {
                    cnt++;
                    c = list.get(j).g2;
                }
            }

            sb.append(cnt).append("\n");
        }

        System.out.println(sb.toString());
    }
}

문제 링크 : https://www.acmicpc.net/problem/2217
문제 등급 : Silver IV

문제 해결 로직

1. 로프의 길이를 오름 차순으로 나열하여 병렬로 세운다.
2. 가장 작은 로프부터 for문을 돌면서 자기 자신의 길이만큼 남아 있는 루프에서 할당받아 병렬로 물건을 들어 올린다.
   1. 5, 4, 3, 2, 1의 로프가 있다.
   2. 1번의 로프를 활용하면 5개의 로프 모두 1만큼 사용할 수 있다. (1 * 5) = 5
   3. 2번의 로프를 활용하면 4개의 로프를 2만큼 사용할 수 있다. (2 * 4) = 8
   4. 3번의 로프를 활용하면 3개의 로프를 3만큼 사용할 수 있다. (3 * 3) = 9 
   5. 4번의 로프를 활용하면 2개의 로프를 4만큼 사용할 수 있다. (4 * 2) = 8
   6. 5번의 로프를 활용하면 1개의 로프를 5만큼 사용할 수 있다. (5 * 1) = 5
3. 2번은 반복하면서 가장 큰 무게를 구한다.

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

public class 로프 {
    public static List<Integer> list = new ArrayList<>();
    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++) {
            int r = Integer.parseInt(br.readLine());
            list.add(r);
        }

        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Integer.compare(o1, o2);
            }
        });

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < list.size(); i++) {
            int r = list.get(i);

            max = Math.max(max, r * (list.size() - i));
        }

        System.out.println(max);
    }
}