10월 29일 / 코딩테스트 연습 (gwangho)

[SDeung01]

문제 1 : 가장 가까운 같은 글자

문제

• 문제 링크

• 문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다. 예를 들어, s="banana"라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.

  • b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
  • a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
  • n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
  • a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
  • n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다.
  • a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.
• 따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다. 문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.
• 제한사항

  • 1 ≤ s의 길이 ≤ 10,000
  • s은 영어 소문자로만 이루어져 있습니다.

입출력 예

s | result -- | -- "banana" | [-1, -1, -1, 2, 2, 2] "foobar" | [-1, -1, 1, -1, -1, -1]

문제 풀이

• 문자간 거리를 측정하기 위해 indexOf(혹은 lastIndexOf)를 사용한다.
• 현재 위치(i)에서 현재 위치보다 앞에 나온 같은 글자 중 가장 가까운 글자의 위치(lastIndexOf)를 찾아 뺀다.
• 문자열에서 처음 나오는 문자는 인덱스가 i와 일치하므로 조건으로 세운다.

  class Solution {
  public int[] solution(String s) {
      int[] answer = new int[s.length()];
      for(int i = 0; i < s.length(); i++){
          char ch = s.charAt(i);
          if(s.indexOf(ch) != i) {
              answer[i] = i - s.lastIndexOf(ch, i - 1);
          } else answer[i] = -1;
      }
      return answer;
  }
  }

  회고

• indexOf()를 사용할 계획을 우선 세우기는 했으나 lastIndexOf()의 기능을 조금 잘못 알고 있어서 다시 찾아보았다.
• lastIndexOf()를 사용할 시 문자열에서 찾는 문자 중 가장 마지막에 오는 문자의 위치를 반환하는 줄 알고 있었으나 정확히는 문자열의 뒤에서부터 역순으로 문자를 탐색하고 가장 먼저 나오는 문자의 인덱스(= 문자열을 기준으로 봤을 때는 가장 뒤)를 반환한다. 중요한 점은 여기서 반환하는 인덱스는 문자열의 가장 앞을 0으로 하여 1씩 증가하는 기존의 인덱스와 동일하다.
• indexOf(int ch, int fromIndex)와 동일하게 탐색 시작지점을 지정할 수 있다.(lastIndexOf(int ch, int fromIndex) / 시작지점부터 역순으로 탐색)

[SDeung01]

문제 2 : [1차] 비밀지도

문제

• 문제 링크
• 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다.
2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
3. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다.
4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

• 입력 형식

  • 입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.
  • 1 ≦ n ≦ 16
  • arr1, arr2는 길이 n인 정수 배열로 주어진다.
  • 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2n - 1을 만족한다.

• 출력 형식

  • 원래의 비밀지도를 해독하여 '#', 공백으로 구성된 문자열 배열로 출력하라.

입출력 예

매개변수 | 값 -- | -- n | 5 arr1 | [9, 20, 28, 18, 11] arr2 | [30, 1, 21, 17, 28] 출력 | ["#####","# # #", "### #", "# ##", "#####"] 매개변수 | 값 -- | -- n | 6 arr1 | [46, 33, 33 ,22, 31, 50] arr2 | [27 ,56, 19, 14, 14, 10] 출력 | ["######", "### #", "## ##", " #### ", " #####", "### # "]

문제풀이

• Integer.toBinaryString()을 사용하여 주어진 암호 정수를 2진수 형태로 해독한다.
• 해독한 문자열을 다시 정수 형태로 형변환 하여 합친다.(지도1과 2를 결합)
• 합친 2진수의 0은 공백 ' ' 로, 그 외의 숫자는 #으로 치환하고 그 값을 배열 map에 저장한다.

  class Solution {
  public String[] solution(int n, int[] arr1, int[] arr2) {
      String[] answer = new String[n];
      for(int i = 0; i < n; i++){
          String map1 = Integer.toBinaryString(arr1[i]);
          String map2 = Integer.toBinaryString(arr2[i]);
          long longMap1 = Long.parseLong(map1);
          long longMap2 = Long.parseLong(map2);
          String map = String.format("%0"+n+"d", longMap1 + longMap2);
          map = map.replace("0"," ");
          map = map.replace("1","#");
          map = map.replace("2","#");
          answer[i] = map;
      }
      return answer;
  }
  }

  회고

• 충분히 값이 큰 int를 2진수(형태의 문자열)로 변환했다가 다시 정수로 형변환 할 경우 정수의 값이 너무 커져 int로 변환 할 수 없는 경우가 생긴다. 이 경우 Long 타입을 사용한다.
• 변환한 2진수를 무조건 다섯자리로 만들기 위해 String.format을 사용한다. String map = String.format("%0"+n+"d", longMap1 + longMap2);
• %0"+n+"d" : % - d는 문자열의 형식을 10진수 정수로 설정한다는 의미 , 0은 공백을 0으로 표시한다는 의미, n은 해당 문자열의 길이를 의미한다.
• %05d 는 101 과 같은 숫자를 00101로 설정한다.
• 2진수를 이용한 연산에서는 비트연산자를 사용할 수 있다.

  for (int i = 0; i < n; i++) {
    result[i] = Integer.toBinaryString(arr1[i] | arr2[i]);
  }

• (arr1[i] | arr2[i]) 는 각 정수를 2진수(bit)로 변환해 두 비트를 비교하여 둘 중 하나라도 1이면 1로 표현하는 OR연산자다.

[SDeung01]

문제 3 : [1차] 다트 게임

문제

• 문제 링크
• 카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다. 갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다.

1. 다트 게임은 총 3번의 기회로 구성된다.
2. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
3. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수1 , 점수2 , 점수3 )으로 계산된다.
4. 옵션으로 스타상() , 아차상(#)이 존재하며 스타상() 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
5. 스타상()은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상()의 점수만 2배가 된다. (예제 4번 참고)
6. 스타상()의 효과는 다른 스타상()의 효과와 중첩될 수 있다. 이 경우 중첩된 스타상(*) 점수는 4배가 된다. (예제 4번 참고)
7. 스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다. (예제 5번 참고)
8. Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.
9. 스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.

• 0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.

• 입력 형식

  • "점수|보너스|[옵션]"으로 이루어진 문자열 3세트. 예) 1S2D*3T
  • 점수는 0에서 10 사이의 정수이다.
  • 보너스는 S, D, T 중 하나이다.
  • 옵선은 *이나 # 중 하나이며, 없을 수도 있다.

• 출력 형식

  • 3번의 기회에서 얻은 점수 합계에 해당하는 정수값을 출력한다. 예) 37

입출력 예

예제 | dartResult | answer | 설명 -- | -- | -- | -- 1 | 1S2D*3T | 37 | 11 * 2 + 22 * 2 + 33 2 | 1D2S#10S | 9 | 12 + 21 * (-1) + 101 3 | 1D2S0T | 3 | 12 + 21 + 03 4 | 1S*2T*3S | 23 | 11 * 2 * 2 + 23 * 2 + 31 5 | 1D#2S*3S | 5 | 12 * (-1) * 2 + 21 * 2 + 31 6 | 1T2D3D# | -4 | 13 + 22 + 32 * (-1) 7 | 1D2S3T* | 59 | 12 + 21 * 2 + 33 * 2

문제 풀이

• 반복문과 조건문을 이용해 충분히 풀 수 있을 것 같지만 효율적인 코드가 나올 것 같지 않아 문제가 의도하는 대로 정규표현식을 이용한 풀이를 시도하였다.

  
  import java.util.regex.Matcher;
  import java.util.regex.Pattern;

class Solution { public int solution(String dartResult) { // 정규표현식을 사용한 패턴을 컴파일 // 정규식의 의미는 (0~9까지의 숫자가 반드시 하나 이상)('S','D','T' 중 하나)('','#' 중 하나가 없거나 혹은 하나) Pattern pattern = Pattern.compile("(?[0-9]+)(?[SDT])(?[#]?)"); Matcher matcher = pattern.matcher(dartResult); // 일관된 식 사용으로 코드를 간결하게 하기 위해 배열의 길이를 4로 만들고 scores[0]에는 0을 넣는다. int[] scores = new int[4]; int chance = 1; while(matcher.find()){ // 일치하는 다음 패턴이 있는동안 반복 // score그룹에 캡처된 문자열을 int타입의 변수 score로 형변환하여 저장 int score = Integer.parseInt(matcher.group("score"));

        // bonus그룹에 캡처된 문자열의 값에 따라 1~3까지의 정수 저장
        int bonus = matcher.group("bonus").equals("S") ? 1 : 
                    matcher.group("bonus").equals("D") ? 2 :
                                                         3 ;

       // option그룹에 캡처된 문자열의 값에 따라 -1,1,2 중 적절한 값 정수 저장
        int option = matcher.group("option").equals("*") ? 2 : 
                     matcher.group("option").equals("#") ? -1 :
                                                           1 ;
        if(option == 2) {
            scores[chance] = (int) Math.pow(score,bonus) * option;
            scores[chance-1] = scores[chance-1] * option;
        } else {
            scores[chance] = (int) Math.pow(score,bonus) * option;
        }

        chance++;
    }

    return scores[1] + scores[2] + scores[3];
}

}

## 회고
- 정규표현식을 사용하면 문자열에 대한 복잡한 검증을 손쉽게 처리할 수 있다.
- 다만 식의 구조가 난해하여 사용에 많은 숙달이 필요해보인다.
- 관련 내용에 대해 공부하여 아래에 링크로 첨부한다.

[SDeung01]

[[Java] 정규표현식과 Pattern/Matcher] 에 대하여 학습한 내용을 정리하였습니다. 정규표현식에 대해 대략적인 해석은 가능해졌으나 실질적인 사용은 아직 많은 시행착오가 필요할 것 같습니다.