정철
71
2022-01-14 22:39:29 작성 2022-01-14 22:51:11 수정됨
9
352

코딩테스트 문제인데 이방법으로 풀수가 있나요?


오늘 면접본 회사에서 다음과같은 문자열에서 자르는 문제를 받아서

substring과 indexOf를 써서 문제를 풀었더니 틀렸다네요? 그러더니 substring이랑 indexOf를 쓰지말고 풀어보라는데.. 전혀 모르겠어서 모르겠다고 했는데 무슨 자바 스트링 자체만으로 풀수가 있다는군요 쉬운 방법을 놔두고 어렵게 풀었다고.. 안배웠냐고 묻더군요? 그래서 도저히 모르겠어서 어떻게 푸냐고 물어봤더니 대괄호를 붙여서 푸는걸 보여줬는데 그래서 그냥 아 그런가보다 하고 면접보고 나왔는데 아무리 찾아봐도 그런 방법이 없는것같아서 질문드립니다
참고로 언어 상관없이 자유롭게 풀라했고 연봉은 3500~ 이라고 했고 보안/암호화/난독화 하는 회사였습니다. 제생각에는 면접관이 파이썬 슬라이싱이랑 헷갈리신거같은데 이런 방법이 있나요?

2. 그리고 제가 푼 방식은 자리수 전체만큼 루프를 도는거라 성능이 느리다는데 break로 탈출하면 되서 상관없지않나요? 신입이라 잘 몰라 질문드립니다!




0
  • 답변 9

  • 드루이드
    181
    2022-01-14 23:48:58 작성 2022-01-15 00:01:33 수정됨

    2번째 문제는 만약 문자열이 "ccccccccccccccab" 일경우 indexOf를 loop 도는 동안 계속 실행하고 틀린 결과 값이 나올거 같습니다.

    "ccccccccccccccab".indexOf("ab")

    "cccccccccccccab".indexOf("ab")

    "ccccccccccccab".indexOf("ab")

    "cccccccccccab".indexOf("ab")
    ...

    이런식으로요. 음 substring을 안쓴다면..

    for(int j=0; j<s.length()-1; j++) {

      if(s.charAt(j) =='a' && s.charAt(j +1) == 'b') {

          result ++;

      }

    }

    이런식으로 하거나 s.split("ab", -1).length - 1 하는것도 하나의 방법일 거 같습니다. 

  • _우리사이
    505
    2022-01-14 23:55:44 작성 2022-01-15 17:05:15 수정됨

    틀린 내용이 있어서 수정합니다


        public static void main(String args[]) {
            String str = "asdfsdfabasdfasfdab";
            String keyword = "ab";
    
            int result = str.split(keyword, -1).length - 1;
    
            System.out.println(result);
        }


  • 스토리
    107
    2022-01-15 00:01:21 작성 2022-01-15 00:03:19 수정됨

    푸신 것에서 맞고 틀린 지는 논외로 하고, 문자열의 길이만큼 루프를 돌면서 index를 찾을 필욘 없죠.


    indexOf 자체에서 해당 문자열이 존재하는 지를 찾는 건 결국 O(n)이니까 푸신 것에선 O(n^2)이 됩니다.


    그냥 쉬운 방법으론 0 ~ n-2까지 2글자씩 읽어서 확인하면 되겠죠 뭐 => O(n)


  • 정철
    71
    2022-01-15 00:16:40 작성 2022-01-15 00:20:22 수정됨

    드루이드 그렇게 되겠군요 설명 감사합니다

  • 정철
    71
    2022-01-15 00:23:04

    스토리 그렇죠 근데 어차피 값이 다 찾아지면 반복문을 탈출할거고 최대 횟수는 있어야하니까 길이로 해도 괜찮겠다 싶어서 저렇게 했네요 손코딩을 처음해봐서 답은 틀렸지만요

  • 정철
    71
    2022-01-15 00:24:49 작성 2022-01-15 00:26:35 수정됨

    _우리사이 반복을 빠트리신듯하네요! 답변 감사합니다

  • _우리사이
    505
    2022-01-15 10:15:47

    반복문 없어도 되는거에요

    복붙해서 실행해보세요

  • 씨커
    32
    2022-01-15 14:35:25 작성 2022-01-15 15:23:17 수정됨
    1번은 String 클래스만 써서 푸는건 모르겠고, 정규표현식으로 푼다면 아래처럼 하면 됩니다.
    String str = "9938483963433447344436887444657";
    Pattern pattern = Pattern.compile("6[^7]+7");
    Matcher matcher = pattern.matcher(str);
    StringBuilder sb = new StringBuilder();
    matcher.results().forEach(m -> sb.append(m.group()));
    System.out.println(sb.toString());
    2번
    public static void main(String[] args) {
    String str = "asdfsdfabasdfasfdababab";
    String key = "ab";

    System.out.println(getOccurCountByIndexOf(str, key));

    System.out.println(getOccurCountByRegex(str, key));
    }

    private static int getOccurCountByIndexOf(String str, String key) {
    int fromIndex = 0;
    int count = 0;
    while (true) {
    int index = str.indexOf(key, fromIndex);
    if (index == -1) break;
    fromIndex = index + 1;
    count++;
    }
    return count;
    }

    private static long getOccurCountByRegex(String str, String key) {
    Pattern pattern = Pattern.compile(key);
    Matcher matcher = pattern.matcher(str);
    return matcher.results().count();
    }
  • 정철
    71
    2022-01-16 17:15:17

    그렇군요 답글달아주신분들 모두 감사합니다

  • 로그인을 하시면 답변을 등록할 수 있습니다.