[PS] BOJ 1157 단어 공부

문제

문제링크

풀이

이 문제는 시간초과에 유의하면서 코드를 작성 해야한다. 2중 for 문으로 접근하는 경우에 대부분 실패하는 것 같다.

첫번째 시도..

        ...

    String s = scan.next();
    int length = s.length();
    int[] arr = new int[length];

    for (int i = 0; i < length; i++) {
      int count = 0;
      for (int j = 0; j < length; j++) {
        if (String.valueOf(s.charAt(i)).equalsIgnoreCase(String.valueOf(s.charAt(j)))) {
          arr[i] = ++count;
        }
      }
    }
          ...

n * n 으로 전체 단어에서 반복되는 문자열의 갯수만큼 증가시키면서 배열에 저장하다보니 문자열의 길이가 커지는 경우엔 테스트케이스를 통과하지 못했다.

두번째 시도..

  String s = scan.next().toUpperCase();
  int length = s.length();
  int[] arr = new int[length];

  for (int i = 0; i < length; i++) {
    char c = s.charAt(i);
    arr[i]++;
    for (int j = 0; j < i; j++) {
      if (c == s.charAt(j)) {
        arr[j]++;
        arr[i]--;
      }
    }
  }
        ...

두번째 반복문에서 반복횟수를 줄이고 처음 문자열을 받을때부터 대문자로 변환해 놓고 풀어도 실패했다. 그리고 이렇게 풀다보니 나중에 카운트가 저장된 배열 인덱스에 해당하는 알파벳 글자를 가져오는 것에 대해서도 생각을 해야했다. 결국엔 2중 for문 자체가 문제가 되는것 같았다.

소스 코드

2중 for 문이 사용된 부분을 수정했다. 입력된 문자열을 하나하나 비교해 가면서 카운트를 셀 필요가 없다.

1. 2중 for 문 제거
2. 인덱스와 해당 알파벳 매핑

이 두가지를 하나의 배열에서 관리 할 수 있도록 각 알파벳이 가지고 있는 고유 ascii 코드를 이용해 배열에 저장해놓고 이걸로 하나씩 비교한다.

  arr[c - 'A']++;

입력되는 문자열에서 문자 하나씩 배열에 저장할때 - 'A' 를 하게되면 배열 인덱스에 맞춰서 넣을 수 있다. 예를 들어 c 에 'A' 가 들어오는 경우 'A' - 'A' 는 0이 되고 그대로 배열 인덱스 0번부터 저장이 가능하다. 추후 배열에서 인덱스로 꺼낸것을 다시 문자로 바꾸는 과정도 간편하다.

  result = (char) ('A' + i);

대부분의 2중 for 문 시간초과가 나오는 경우에 샘플을 미리 준비해놓고 비교해가는 방식을 사용하는 것이 좋아보인다.

---

  ...

  String s = scan.next().toUpperCase();
  int length = s.length();
  int[] arr = new int[26];
  
  for (int i = 0; i < length; i++) {
    char c = s.charAt(i);
    arr[c - 'A']++;
  }
  
  int max = 0;
  char result = '?';
  for (int i = 0; i < arr.length; i++) {
    if (max < arr[i]) {
      max = arr[i];
      result = (char) ('A' + i);
    } else if (max == arr[i]) {
      result = '?';
    }
  }
  
  System.out.println(result);