2022 프로그래머스 코딩테스트 모의고사 1 (1, 2, 3번 문제)

출처) 프로그래머스 Facebook

 

 

어제 프로그래머스에서 진행하는 코딩테스트 모의고사가 있다고 듣고 모의고사 1 문제를 풀었다.

1 ~ 3 번 문제는 어찌저찌해서 풀었는데, 4 번 문제는 손을 대질 못하겠어서 넘김 .. 🥲 감도 안잡히더라 어떻게 푸는 걸까 ㅋㅋ??

한 문제당 만점이 100점이고, 총 300점이 나왔는데 상위 58% 정도로 나와서 굉장히 놀랬다 ;;

일단 풀어낸 1 ~ 3 번 문제에 대해 간단하게 기록하려고 한다.

 

 

---

 

 

1 번 문제 설명 💡

정수로 이루어진 String Type 의 X, Y를 입력받습니다. 
X 와 Y 각 인덱스 마다 같은 숫자를 짝을 짓는데, 이를 짝궁이라 합니다.

예를들어, X = 1120, Y = 2134 라면, 짝궁은 "21" 이 됩니다.
짝이 지어지는 숫자들로 만들 수 있는 가장 큰 수를 리턴하는 프로그램을 작성하세요.

 

X, Y의 짝궁이 하나도 존재하지 않으면 "-1"을 리턴합니다.
또한 짝궁이 0으로만 구성 되어있다면 "0"을 리턴합니다.

 

제한사항과 입출력 예시

• 3 ≤ X, Y 의 길이(자릿수) ≤ 3,000,000 입니다.
• X, Y 는 0으로 시작하지 않습니다.
• X, Y 의 짝꿍은 상당히 큰 정수일 수 있으므로 문자열(String)로 반환

"100"	"2345"	"-1"
"100"	"203045"	"0"
"100"	"123450"	"10"
"12321"	"42531"	"321"
"5525"	"1255"	"552"

 

1번 풀이 코드

HasgMap Collection 과 getOrDefault() 메서드를 활용해 풀었다.

받아온 X, Y 문자열을 하나씩 떼어내고 각각의 Map 에 넣어준다. (Key 는 Charcter 문자, Value 는 해당 문자의 갯수)

두 개의 Map 에서 포함되는 짝궁을 찾기 위해서 똑같은 Key(문자) 가 있는지 먼저 확인한다.

 

여기서 두 가지의 경우가 생길 수 있다고 판단했는데,

1. Key(문자) 는 같지만 Value(해당 문자의 갯수) 가 서로 다른 경우

  - 이 경우에는 더 작은 Value 가 나온만큼 for 문을 사용해 미리 만들어놓은 List 에 Key 를 추가한다.

  - 예를들어, xMap 에서 Key(A), Value(3) | yMap 에서 Key(A), Value(2) 가 존재한다면, 짝궁으로 "AA" 가 만들어지므로, 

     Value 가 더 작은 yMap 의 Value 만큼 반복해 List 에 추가하는 것이다. 

 

2. Key 도 같고, Value 도 같은 경우

  - 이 경우에는 xMap 이나 yMap 이나 상관없이 Value 만큼 for 문을 사용해 List 에 Key 를 추가했다.

 

조금 애먹은 부분이 있다면 짝궁이 0으로만 구성된 경우 어떻게 "0" 하나만을 반환할까 ? 에서 굉장히 고민이 됐고, Set 을 활용해 문제를

풀이할 수 있었다. 54 Line 까지의 작업이 모두 끝나면 List 에는 '0' 2개가 있게되고, List 를 Set 으로 만들어준다.

그리고 Set 의 크기과 List 의 크기를 비교해서 크기가 다르고 Set 의 크기가 1이면서 '0' 을 포함하고 있다면, 짝궁이 0으로만 구성된 경우

이므로 "0" 만을 반환하게 했다.

 

그리고 최종적으로 만들어진 List 를 내림차순 정렬하면서 answer 에 더해준 뒤 반환하면 끝 !

class Solution {
    public String solution(String x, String y) {
        StringBuffer answer = new StringBuffer();
        Map<Character, Integer> xMap = new HashMap<>();
        Map<Character, Integer> yMap = new HashMap<>();
        List<Character> list = new ArrayList<>();

        for (int i = 0; i < x.length(); i++) {
            Character ch = x.charAt(i);
            xMap.put(ch, xMap.getOrDefault(ch, 0) + 1);
        }

        for (int i = 0; i < y.length(); i++) {
            Character ch = y.charAt(i);
            yMap.put(ch, yMap.getOrDefault(ch, 0) + 1);
        }

        for (Character key : xMap.keySet()) {
            if (yMap.containsKey(key)) {
                // 키는 같지만 value 가 다르다면,
                if (!xMap.get(key).equals(yMap.get(key))) {
                    if (xMap.get(key) > yMap.get(key)) {
                        for (int i = 0; i < yMap.get(key); i++) {
                            list.add(key);
                        }
                    } else {
                        for (int i = 0; i < xMap.get(key); i++) {
                            list.add(key);
                        }
                    }
                // 키도 같고 value 도 같다면,
                } else {
                    for (int i = 0; i < xMap.get(key); i++) {
                        list.add(key);
                    }
                }
            }
        }

        Set<Character> set = new HashSet<>(list);
        if (set.size() != list.size()) {
            if (set.size() == 1 && set.contains('0')) {
                return "0";
            }
        }

        list.sort(Comparator.reverseOrder());

        // 짝꿍이 없는 경우
        if (list.isEmpty()) {
            return "-1";
        }

        for (int i = 0; i < list.size(); i++) {
            answer.append(list.get(i));
        }

        return answer.toString();
    }
}

 

 

---

 

2번 문제 설명 💡

XYZ 마트에서는 회원을 대상으로 매일 한 가지 제품을 할인하는 행사를 진행합니다.

회원은 할인 제품을 하루에 하나씩만 구매할 수 있습니다.

정현이는 자신이 원하는 제품과 각각의 제품 수량이 10일 연속으로 일치하는 경우에 회원가입을 하려고 합니다.

여기서 정현이가 원하는 제품을 모두 할인받을 수 있는 회원등록 날짜의 총 일수를 반환하는 프로그램을 작성하세요.

 

제한사항과 입출력 예시

• 1 ≤ want의 길이 = number의 길이 ≤ 10
  • 1 ≤ number의 원소 ≤ 10
  • number[i]는 want[i]의 수량을 의미하며, number의 원소의 합은 10
• 10 ≤ discount의 길이 ≤ 10
• want와 discount의 원소들은 알파벳 소문자로 이루어진 문자열
  • 1 ≤ want의 원소의 길이, discount의 원소의 길이 ≤ 12

want	number	discount	result
["banana", "apple", "rice", "pork", "pot"]	[3, 2, 2, 2, 1]	["chicken", "apple", "apple", "banana", "rice", "apple", "pork", "banana", "pork", "rice", "pot", "banana", "apple", "banana"]	3
["apple"]	[10]	["banana", "banana", "banana",, "banana", "banana", "banana", "banana", "banana", "banana", "banana",]	0

 

2번 풀이 코드

이 문제는 보고 슬라이딩 윈도우를 활용해 풀이하면 되겠다 라고 생각이 들었고, 어떻게 구현할까 생각하다 Map getOrDefalt() 메서드를 통해 문제를 풀이했다.

먼저 2개의 Map<String, Integer> 을 만들고 하나는 정현이가 원하는 물품과 물품을 원하는 갯수를 넣어준다.

나머지 하나는 최초 윈도우로써 할인하는 물품과 갯수를 getOrDefault() 를 사용해 넣어준다.

그리고 최초 설정한 윈도우를 한 칸씩 밀면서 전진하기전에, 처음부터 정현이가 원하는 물품, 갯수가 윈도우와 일치하는 경우가 있을 수 

있으므로, 이 경우에 리턴 값인 answer 를 증가시켜준다.

 

그러고 슬라이딩 윈도우 알고리즘을 사용해서 할인하는 물품, 갯수를 담은 윈도우를 전진시키고 원하는 물품, 갯수가 윈도우와 동일한 경우

answer 를 증가시켜주면 끝 !

class Solution {
     public int solution(String[] want, int[] number, String[] discount) {
         int answer = 0;
         Map<String, Integer> wantMap = new HashMap<>();
         Map<String, Integer> window = new HashMap<>();

         // key = banana, value = 3
         for (int i = 0; i < want.length; i++) {
             wantMap.put(want[i], number[i]);
         }

         // 최초 윈도우 설정
         for (int i = 0; i < 10; i++) {
             window.put(discount[i], window.getOrDefault(discount[i], 0) + 1);
         }

         if (wantMap.equals(window)) {
            answer ++;
         }

         // 초기 윈도우를 하나 씩 전진시키면서 want[] 와 비교한다.
         for (int i = 10; i < discount.length; i++) {
             // 1. 한 칸 뒤로 넘기면서 맨 뒤의 값 + 1
             window.put(discount[i], window.getOrDefault(discount[i], 0) + 1);

             // 2. 한 칸 뒤로 넘기면서 맨 앞의 값 - 1
             window.put(discount[i - 10], window.get(discount[i - 10]) - 1);

             // 위에서 value 를 하나 지우고 해당 value 가 0이 되었다면 window 에서 삭제한다.
             if (window.get(discount[i - 10]) == 0) {
                 window.remove(discount[i - 10]);
             }

             if (wantMap.equals(window)) {
                 answer ++;
             }
         }

         return answer;
     }
}

 

 

---

 

 

3번 문제 설명 💡

택배 기사님의 오더에 따라 컨테이너 벨트에서 알맞은 박스를 실어야 합니다.

컨테이너 벨트에는 항상 ... 5,4,3,2,1 순으로 오고, 오더 순서에 맞지 않는 택배 박스가 온다면 보조 컨테이너 벨트에 쌓아야합니다.

만약, 오더가 4,3,1,2,5 라면, 4번 박스가 올 때 까지 나머지 1,2,3 박스는 보조 컨테이너 벨트에 쌓고, 그 다음에 나온 4번 박스를 트럭에 적재합니다. 그 다음 오더 순서로 봤을 때 3번 박스를 적재해야하는데, 컨테이너 벨트에는 5번 박스라 적재하지 못하고, 보조 컨테이너 벨트 맨 위에 있는 3번 박스를 적재합니다. 그 다음 오더 순서로 1번 박스가 적재되어야 하지만, 더 이상 적재할 수 없기 때문에 트럭에는 4,3 박스만 적재되어있는 상태가 됩니다.

 

제한사항과 입출력 예시

• 1 ≤ order의 길이 ≤ 1,000,000
• order는 1이상 order의 길이 이하의 모든 정수가 한번씩 등장
• order[i]는 기존의 컨테이너 벨트에 order[i]번째 상자를 i+1번째로 트럭에 실어야 함을 의미

order	result
[4, 3, 1, 2, 5]	2
[5, 4, 3, 2, 1]	5

 

3번 풀이 코드

Stack, Queue 관련 문제인줄은 빨리 눈치챘지만, 정말 애먹은 문제다 .. 계속 50점이 나오는게 ;;

Stack, Queue 자료구조로 풀어내는 문제를 많이 연습하지 못해서 반복문 돌릴 때 정말 고통받은 문제 ㅠㅠ

먼저 Queue 에 컨테이너 벨트로 차례대로 들어오는 박스를 ComingBox 라 하여 넣어줬고, Stack 을 보조 컨테이너 벨트로 활용했다.

 

먼저 order 를 기준으로 작업을 해야하니까 order 변수를 셋팅해주고, 컨테이너 벨트의 박스들인 Queue 가 모두 비워질 때 까지 반복을

실시하여 풀이했다. 처음에는 order.length 만큼 for 반복을 사용해 풀이했는데, 딱 컨테이너 벨트의 초기 상자 갯수까지만 반복을 돌려

모든 작업을 실시하기도 전에 for 문이 종료되어 버리기 때문에 while() 반복을 사용했다. 이거 덕분에 풀이할 수 있었다 ㅎㅎ;;

class Solution3 {
    public int solution(int[] orders) {
        int count = 0;
        Queue<Integer> comingBox = new LinkedList<>();
        Stack<Integer> stackBox = new Stack<>();

        for (int i = 0; i < orders.length; i++) {
            comingBox.offer(i + 1);
        }

        int orderIndex = 0;
        while(!comingBox.isEmpty()) {
            Integer checkOrder = orders[orderIndex];

            if (!comingBox.peek().equals(checkOrder)) {
                if (!stackBox.isEmpty() && stackBox.peek().equals(checkOrder)) {
                    stackBox.pop();
                    count++;
                    orderIndex += 1;
                    continue;
                }
                stackBox.push(comingBox.poll());
            } else {
                comingBox.poll();
                count++;
                orderIndex += 1;
            }
        }

        if (!stackBox.isEmpty()) {
            int stackLength = stackBox.size();
            for (int i = 0; i < stackLength; i++) {
                int checkOrder = orders[orderIndex];

                if (stackBox.peek().equals(checkOrder)) {
                    stackBox.pop();
                    count++;
                    orderIndex += 1;
                }
            }
        }

        return count;
    }
}

 

 

---

소감

4번 문제는 정말 어떻게 풀어야할지 감도 잡히지 않아서 손을 뗐는데 300 점도 상위 58% 인걸 보고 참 잘하는 분들이 많구나 싶었다.. 👍 

그래도 열심히 알고리즘 공부한지 2주정도 되는데 옛날처럼 아예 손 못대는 그런 불상사는 없어서 다행이라고 생각하고, 느리지만 꾸준히 학습하다 보면 언젠가 코딩 테스트가 재밌는 날이 오지 않을까..라는 생각을 해본다.