11월 6일 / 코딩테스트 연습(gwangho)

[SDeung01]

• 이번 문제풀이부터 2단계 문제를 조금씩 풀어보려고 한다. 난이도 어려운 것은 아직 손도 못 대겠고... 쉬운것부터 차근차근...

문제 1 : 귤 고르기

문제

• 문제 링크

• 경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

• 예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

• 경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

• 제한사항

  • 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
  • 1 ≤ tangerine의 원소 ≤ 10,000,000

입출력 예

k | tangerine | result -- | -- | -- 6 | [1, 3, 2, 5, 4, 5, 2, 3] | 3 4 | [1, 3, 2, 5, 4, 5, 2, 3] | 2 2 | [1, 1, 1, 1, 2, 2, 2, 3] | 1

문제풀이

• 익숙한 유형의 문제다. 주어진 배열의 요소(귤의 사이즈)의 빈도를 구하고 그 값이 큰 순으로 상자를 채운다.
• 한 사이즈의 귤을 모두 넣어야 한다는 제한 조건이 없으므로 별도의 조건이 필요없다.
• 귤의 종류와 개수가 일치할 필요 없이 한 종류당 몇개가 있는지만 필요한 문제이므로 Map의 value값을 List에 채워 간단하게 정렬할 수도 있다.
• 하지만 유사한 유형의 문제를 풀게 될 경우(혹은 프로그램 작성에 요구하는 바가 달라질 경우)를 고려해 Map의 keySet을 List로 받아 람다식으로 오버라이딩하여 Map의 value값을 기준으로 keySet을 저장한 리스트를 내림차순 정렬하여 사용하였다.

  
  import java.util.*;

class Solution { public int solution(int k, int[] tangerine) { int answer = 0; int total = 0;

    // 귤 사이즈, 개수 의 형태로 map에 저장
    Map<Integer, Integer> gyulMap = new HashMap<>();

    for(int size : tangerine){
        gyulMap.put(size, gyulMap.getOrDefault(size,0)+1);
    }

    // 개수가 많은 순으로 정렬하기 위해 map의 keySet을 리스트로 받아 내림차순으로 정렬
    List<Integer> sizeList = new ArrayList<>(gyulMap.keySet());
    sizeList.sort((s1,s2) -> gyulMap.get(s2).compareTo(gyulMap.get(s1)));

    // 정렬된 리스트의 요소를 key로 사용
    // 한 사이즈의 귤을 모두 상자에 담고 상자가 넘치면 break
    for(int size : sizeList){
        total += gyulMap.get(size);
        answer++;
        if(total >= k) break;
    }

    return answer;
}

}

## 회고
- 앞서 얘기한 Map의 value만을 받아 정렬하여 사용하는 방법이다.
- List에 저장하는 값과 정렬방식에 차이가 있을 뿐 기본적인 골자는 같다.
```java
        List<Integer> sizeList = new ArrayList(gyulMap.values());
        Collections.sort(sizeList ,Collections.reverseOrder());

        for(int i=0;i<sizeList .size();i++){

            k-=sizeList .get(i);
            answer++;
            if(k<=0){
                break;
            }
        }

Collections.sort(sizeList ,Collections.reverseOrder());

대신 아래와 같은 방법으로도 내림차순 정렬이 가능하다.

sizeList.sort(((o1, o2) -> o2 - o1));

위 방식은 Comparable 인터페이스를 구현하는 comparTo() 메소드를 사용하는 방식이고, 아래의 방식은 Comparator 인터페이스를 구현하여 compare() 메소드를 사용하는 방식이다.

[SDeung01]

문제 2 : 영어 끝말잇기

문제

• 문제 링크

• (문제가 길어 임의로 요약합니다. 자세한 내용은 링크를 참고해주세요.)

• 앞사람이 사용한 단어의 마지막 알파벳으로 시작하는 단어를 말할 것. 앞서 사용한 단어는 다시 사용하지 말 것.

• 차례대로 돌아가며 진행하며 가장 먼저 탈락하는 사람의 번호와 자신의 몇번 차례에서 탈락했는지 반환할 것.

• 제한사항

  • 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
  • words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
  • 단어의 길이는 2 이상 50 이하입니다.
  • 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
  • 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
  • 정답은 [ 번호, 차례 ] 형태로 return 해주세요.
  • 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

입출력 예

n | words | result -- | -- | -- 3 | ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] | [3,3] 5 | ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"] | [0,0] 2 | ["hello", "one", "even", "never", "now", "world", "draw"] | [1,3]

문제풀이

• 모두가 단어를 말한 횟수를 적절히 나누어 몫과 나머지로 참여자의 번호와 차례를 구한다.
• 필요한 조건식을 반환하는 함수를 이용하면 코드의 가독성을 높일 수 있을 것 같아 따로 작성하였다.

  
  import java.util.*;

class Solution { public int[] solution(int n, String[] words) {

    int speak = 0;
    String prevWord = "" + words[0].charAt(0);
    Set<String> wordSet = new HashSet<>();

    for(String myWord : words){
        int playerNo = (speak % n) + 1;
        int turn = (speak / n) + 1;

        if(chainCheck(prevWord, myWord) && dupliCheck(wordSet, myWord)){
            prevWord = myWord;
            wordSet.add(myWord);
            speak++;
        } else {
            return new int[]{playerNo, turn};
        }
    }
    return new int[]{0, 0};
}

// 이전 단어의 마지막 알파벳과 현재 단어의 시작 알파벳이 일치하는지 체크
private boolean chainCheck(String prevWord, String myWord){
    char lastCh = prevWord.charAt(prevWord.length()-1);
    char startCh = myWord.charAt(0);
    return lastCh == startCh;
}

// 현재 단어가 이미 나온 단어인지 체크
private boolean dupliCheck(Set<String> wordSet, String myWord){
    return !wordSet.contains(myWord);
}

}

## 회고
- contains를 사용하지 않고 Set.size()와 변수 speak를 비교하는 방법으로도 중복성을 검사할 수 있다.(Set은 중복값을 허용하지 않으므로  만약 중복된 단어라면 Set.size()와 변수 speak는 그 크기가 다를 수 밖에 없다.)
- `return` 을 잘 사용할 경우 따로 break를 사용할 필요 없이 루프 탈출과 함수 탈출을 동시에 할 수 있어 편리하다.
- 리턴타입이 배열일 경우 반환을 위해 별도의 배열을 선언해줄 필요 없이 리턴값에서 new 연산자를 통해 생성하여 바로 반환 할 수 있다.

[SDeung01]

문제3 : 점프와 순간 이동

문제

• 문제 링크

• OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.

• 예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다. 아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.

  • 처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.
  • 처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.
  • 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.

• 위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.

• 제한사항

  • 숫자 N: 1 이상 10억 이하의 자연수
  • 숫자 K: 1 이상의 자연수

입출력 예

N | result -- | -- 5 | 2 6 | 2 5000 | 5

문제 풀이

• 처음에는 잘못된 접근으로 조건문을 세우는데 한참 고민하고 헤매었다.
• 순간이동 시 값이 무조건 지금까지의 이동거리의 두배로 커진다는 것에서 비트연산자 << (2진수 형태의 값을 왼쪽으로 한칸씩 이동 = 2배로 커짐)와 같은 기능을 할 것이라 예상하여 2진법으로 접근하였다.

• 정수를 2진수 형태로 변환 후 비트가 1인 자리수가 총 점프한 거리(건전지 사용량)을 의미한다.

  public class Solution {
  public int solution(int n) {
      int ans = 0;
  
      String binN = Integer.toBinaryString(n);
  
      for(char ch : binN.toCharArray()){
          if(ch == '1') { ans++; }
      }
  
      return ans;
  }
  }

회고

• 정수의 비트가 1인 자리수는 Integer.bitCount() 메서드를 사용하면 반복문이나 형변환 없이 아주 간단하게 풀 수 있었다.

• 최근 비트를 이용하는 문제가 종종 보여 기록을 위해 남겨둔다.

  public class Solution {
  public int solution(int n) {
  
      return Integer.bitCount(n);
  }
  }