백준 5525번: IOIOI

문제

https://www.acmicpc.net/problem/5525

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    br.readLine();

    int answer = solution(n, br.readLine());

    System.out.println(answer);
}

public static int solution(int n, String target) {
    int answer = 0;

    char[] s = target.toCharArray();
    char[] targetString = getTargetString(n).toCharArray();
    int[] fail = failFunction(targetString);

    int start = 0;
    int m = 0;

    while (start <= s.length - targetString.length) {
        if (m < targetString.length && s[start + m] == targetString[m]) {
            ++m;
            if (m == targetString.length) {
                answer++;
            }
        } else {
            if  (m == 0) {
                start++;
            } else {
                start += (m - fail[m - 1]);
                m = fail[m - 1];
            }
        }
    }

    return answer;
}

private static String getTargetString(int n) {
    StringBuilder sb = new StringBuilder();
    sb.append("I");

    while (n-- > 0) {
        sb.append("OI");
    }
    return sb.toString();
}

private static int[] failFunction(char[] target) {
    int n = target.length;
    int[] fail = new int[n];

    int start = 1;
    int m = 0;

    while (start + m < n) {
        if (target[start + m] == target[m]) {
            m++;
            fail[start + m - 1] = m;
        } else {
            if (m == 0) {
                start++;
            } else {
                start += (m - fail[m - 1]);
                m = fail[m - 1];
            }
        }
    }

    return fail;
}

흐름

  1. S에서 찾을 문자열(targetString)을 만든다.
  2. 찾을 문자열에서 실패함수 값을 구한다.
  3. 배열의 범위를 벗어나기 전까지 반복한다.
  4. 검색 할 문자열 s에서 찾을 단어을 한 문자씩 비교한다.
  5. 한 문자가 같으면, 그 다음 문자를 비교 할 수 있게 m을 1씩 더해서 최종적으로 문자열에 단어가 포함되어 있으면 answer를 증가시킨다.
  6. 문자가 일치하지 않으면
    1. m이 0이면 시작도 못해본거니깐 검색 할 문자열에서 한 문자 뒤로 간다.
      ex) S = ABCDEF 일 경우, B부터 검색하도록 start를 증가
    2. 0이 아니면 단어에서 어느정도 일치한 문자열이 존재한 것이므로 비교 시작 할 문자의 index를 m에서 실패함수 값을 빼서 구한다.
    3. 일치한 문자열 뒤 부터 검색하면 되므로 m도 실패함수 값에서 구한다.
  7. 반복이 끝나면 answer 값을 return 한다.
  8. 끝.

KMP 알고리즘 해설

문자열에서 특정 패턴을 찾아내는 문자열 검색 알고리즘

위키백과
  • 비교한 정보를 최대한 활용
  • 문자열 S = OOIOIIOIOIOIOIOIOIOIOOIOI 에서 패턴 M = IOIOI 를 찾는다고 가정
  • 우선 패턴 M의 실패함수를 구하기 위해 IOIOI에서 접두사와 접미사의 길이가 가장 긴 부분을 구한다.

실패함수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static int[] failFunction(char[] target) {
    int n = target.length;
    int[] fail = new int[n];

    int start = 1;
    int m = 0;

    while (start + m < n) {
        if (target[start + m] == target[m]) {
            m++;
            fail[start + m - 1] = m;
        } else {
            if (m == 0) {
                start++;
            } else {
                start += (m - fail[m - 1]);
                m = fail[m - 1];
            }
        }
    }

    return fail;
}
  1. IOIOI 패턴에서 index 1에 저장된 ‘O’와 0에 저장된 ‘I’는 같지 않으므로 비교가 시작되는 위치를 1 증가 시킨다. (현재 start = 2, m = 0)
  2. 루프에 의해 다시 비교하면 2에 저장된 ‘I’와 0에 저장된 ‘O’는 같으니 m을 증가시키고 접두사와 접미사가 일치한 값인 m를 저장한다. (현재 start = 2, m = 1)
    1. IOIOI에서 IOI까지 진행한 상태에서 I와 I가 일치 했으므로 길이 1이 일치한 것
  3. 3에 저장된 ‘O’과 1에 저장된 ‘O’가 같으므로, 다시 m을 1 증가 시키고 접두사와 접미사가 일치한 값인 m을 저장한다. (현재 start = 2, m = 2)
    1. IOIOI에서 IOIO까지 진행한 상태에서 ‘IO’와 ‘IO’가 같으므로 길이 2가 일치한 것
  4. 4에 저장된 ‘I’과 2에 저장된 ‘I’가 같으므로, 다시 m을 1 증가 시키고 접두사와 접미사가 일치한 값인 m을 저장한다. (현재 start = 2, m = 3)
    1. IOIOI는 접두사 ‘IOI’와 ‘IOI’의 길이가 3이므로 3
  5. array return
  6. 끝

KMP 알고리즘

  • 실패함수 값 구하는 것과 동일하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static int solution(int n, String target) {
    int answer = 0;

    char[] s = target.toCharArray();
    char[] targetString = getTargetString(n).toCharArray();
    int[] fail = failFunction(targetString);

    int start = 0;
    int m = 0;

    while (start <= s.length - targetString.length) {
        if (m < targetString.length && s[start + m] == targetString[m]) {
            ++m;
            if (m == targetString.length) {
                answer++;
            }
        } else {
            if  (m == 0) {
                start++;
            } else {
                start += (m - fail[m - 1]);
                m = fail[m - 1];
            }
        }
    }

    return answer;
}
  • 실패함수 array [0, 0, 1, 2, 3]
  1. m이 패턴의 길이보다 작고, 문자열 s(OOIOIIOIOIOIOIOIOIOIOOIOI) 에서 start+m 한 index의 문자와 비교할 패턴(IOIOI)의 m 번째 문자가 같지 않으므로 s에서 비교가 시작되는 위치를 1 증가 시킨다. (현재 start = 1, m = 0)
  2. S의 1와 패턴의 0을 비교해도 여전히 같지 않으므로 시작 위치를 또 증가 시킨다. (start = 2, m = 0)
  3. S의 2와 패턴의 0을 비교하면 둘다 ‘I’로 같으므로 m을 증가 시키고 패턴의 길이와 같을 때 까지 반복한다. (start = 2, m = 1)
  4. S의 3와 패턴의 1을 비교하면 둘다 ‘O’로 같으므로 m을 증가 시키고 패턴의 길이와 같을 때 까지 반복한다. (start = 2, m = 2)
  5. S의 4와 패턴의 2을 비교하면 둘다 ‘I’로 같으므로 m을 증가 시키고 패턴의 길이와 같을 때 까지 반복한다. (start = 2, m = 3)
  6. S의 5와 패턴의 3을 비교하면 같지 않고 이제 m이 0이 아니므로,
  7. s의 시작 위치를 증가 시켜야 하는데 1을 증가 시키는게 아니라 이전에 구한 실패 함수 값에서 찾아온다.
    1. (m(3) - 실패함수 값 array[m(3) - 1]) = 2
    2. 즉 현재 시작 위치에서 1을 더한 값이 아닌 2를 더한다.
    3. 이미 index 4까지는 접두사 접미사가 2 자리까지 같기 때문에
  8. m 역시 실패함수 값을 가져온다.
    1. IOIOI에서 IOIO까지 비교한 값에서 실패했기 떄문에
    2. 그 이전 접미사 접두사 길이만큼으로 비교한다.
  9. 이 시점에서 start = 4, m = 1이 되고 루프를 반복한다.
  10. 4와 1은 같지 않으므로 다시 7번부터 8번까지 반복해서 start와 m을 조정한다.
    1. 이 예제로 하면 처음부터 같지 않았으므로 start는 한칸만 뒤로 가고
    2. m 역시 접두사 접미사 1 짜리도 실패했으므로 처음부터 비교한다.
    3. (start = 5, m = 0)
  11. (5, 0), (6, 1), (7, 2), (8, 3), (9, 4) 이 쭉~ 같으므로 드디어 문자열 s에서 패턴을 찾은 것이므로 answer을 증가 시킨다.
  12. 그 이후로 다시 비교하면 m의 길이가 패턴의 길이를 넘어 갔으므로,
  13. start와 m의 위치를 다시 조정한다.
  14. 반복
  15. 끝.
  • 결국 정리하면, 처음 말한 것 처럼 이미 비교한 값은 다시 비교하지 않고 그 다음 부터 비교하는 방식으로 시간을 줄인다.
  • 더 자세한 설명들은 글 마지막 참고 사이트를 찾아가면 다른 분들이 매우 자세하게 설명해주시고 계신다.

결과

테스트 케이스

1
2
3
assertEquals(4, test.solution(1, "OOIOIOIOIIOII"));
assertEquals(6, test.solution(2, "OOIOIIOIOIOIOIOIOIOIOOIOI"));
assertEquals(7, test.solution(1, "IOIOIOIOIOIOIOI"));

참고 사이트

댓글 공유

프로그래머스: 튜플

문제

https://programmers.co.kr/learn/courses/30/lessons/64065

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public int[] solution(String s) {
    String[] strArray = getStringArray(s);
    List<Integer[]> list = convertStringArrayToIntegerArrayList(strArray);
    sortByArraylength(list);

    List<Integer> tuple = getTuple(list);
    int[] answer = convertIntegerArrayToIntArray(tuple);

    return answer;
}

private String[] getStringArray(String s) {
    String[] array = s.substring(2, s.length()-2).replace("},{", "@").split("@");

    return array;
}

private List<Integer[]> convertStringArrayToIntegerArrayList(String[] strArray) {
    List<Integer[]> list = new ArrayList<>();
    for (String str : strArray) {
        String[] stringNumbers = str.split(",");
        Integer[] array = convertStringArrayToIntegerArray(stringNumbers);

        list.add(array);
    }

    return list;
}

private Integer[] convertStringArrayToIntegerArray(String[] stringNumbers) {
    Integer[] array = new Integer[stringNumbers.length];
    int i = 0;
    for (String str2 : stringNumbers) {
        array[i++] = Integer.parseInt(str2);
    }

    return array;
}

private void sortByArraylength(List<Integer[]> list) {
    Collections.sort(list, new Comparator<Integer[]>() {
        @Override
        public int compare(Integer[] o1, Integer[] o2) {
            return o1.length - o2.length;
        }
    });
}

private List<Integer> getTuple(List<Integer[]> list) {
    List<Integer> tuple = new ArrayList<>();

    for (int i = 0; i < list.size(); i++) {
        Integer[] elements = list.get(i);

        for (Integer element : elements) {
            if (!tuple.contains(element)) {
                tuple.add(element);
            }
        }
    }

    return tuple;
}

private int[] convertIntegerArrayToIntArray(List<Integer> list) {
    int[] answer = new int[list.size()];
    int j = 0;
    for (int i : list) {
        answer[j++] = i;
    }

    return answer;
}

흐름

  1. 문자열을 각각 숫자를 저장한 문자열 배열로 만든다. (getStringArray)
  2. 만든 문자열 배열에 저장된 문자열을 “,”로 나눠서 각각 Integer 배열에 저장하고 그 Integer 배열을 담는 List에 저장한다. (convertStringArrayToIntegerArrayList)
  3. List에 저장된 Integer 배열을 배열의 길이가 짧은 순으로 sorting 한다. (sortByArraylength)
  4. 정렬한 list를 돌면서 Integer 배열을 꺼내고 다시 배열을 돌면서 튜플을 저장할 List에 담는데, 이 때 저장하기 전에 이미 List에 저장된 숫자인 경우엔 담을 필요가 없으므로 contain() 를 사용해서 List에 저장되지 않은 숫자만 add 한다.
  5. List형 이었으므로 문제에 맞게 int 배열 형으로 변환해서 return한다.
  6. 끝

최다 좋아요 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] solution(String s) {
    Set<String> set = new HashSet<>();
    String[] arr = s.replaceAll("[{]", " ").replaceAll("[}]", " ").trim().split(" , ");
    Arrays.sort(arr, (a, b)->{return a.length() - b.length();});
    int[] answer = new int[arr.length];
    int idx = 0;
    for(String s1 : arr) {
        for(String s2 : s1.split(",")) {
            if(set.add(s2)) answer[idx++] = Integer.parseInt(s2);
        }
    }
    return answer;
}
  1. 마찬가지로 우선 String을 String[]로 만들고
  2. 배열 길이 순으로 정렬한 다음에
  3. 2중 for문을 돌면서 숫자를 배열에 저장하는데,
  4. Set을 통해 이미 저장된 숫자는 저장하지 않는다.

결과

번호 속도
테스트 1 통과 (2.12ms, 52.3MB)
테스트 2 통과 (2.16ms, 52.2MB)
테스트 3 통과 (2.03ms, 50.3MB)
테스트 4 통과 (2.58ms, 52.4MB)
테스트 5 통과 (6.02ms, 52.4MB)
테스트 6 통과 (7.96ms, 50.9MB)
테스트 7 통과 (38.39ms, 53.8MB)
테스트 8 통과 (68.47ms, 61.7MB)
테스트 9 통과 (51.85ms, 57.6MB)
테스트 10 통과 (142.71ms, 62.2MB)
테스트 11 통과 (91.56ms, 65.7MB)
테스트 12 통과 (111.69ms, 74.1MB)
테스트 13 통과 (104.26ms, 72.1MB)
테스트 14 통과 (113.99ms, 74.5MB)
테스트 15 통과 (1.84ms, 50MB)

테스트 케이스

1
2
3
4
5
6
7
assertArrayEquals(new int[]{2,1,3,4}, test.solution("{{2},{2,1},{2,1,3},{2,1,3,4}}"));
assertArrayEquals(new int[]{2,1,3,4}, test.solution("{{1,2,3},{2,1},{1,2,4,3},{2}}"));
assertArrayEquals(new int[]{111,20}, test.solution("{{20,111},{111}}"));
assertArrayEquals(new int[]{123}, test.solution("{{123}}"));
assertArrayEquals(new int[]{3,2,4,1}, test.solution("{{4,2,3},{3},{2,3,4,1},{2,3}}"));
assertArrayEquals(new int[]{3,2,4,1,100}, test.solution("{{4,2,3},{3},{2,3,4,1},{2,3},{2,3,4,1,100}}"));
assertArrayEquals(new int[]{3,2,4,1,100}, test.solution("{{4,2,3},{3},{2,3,4,1},{2,3},{2,3,4,1,100}}"));

댓글 공유

백준 1152번: 단어의 개수

문제

https://www.acmicpc.net/problem/1152

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static long solution(String args) {
    char[] tochar = args.trim().toCharArray();

    long answer = 0;
    if (tochar.length == 0) {
        return answer;
    }

    for (char ch : tochar) {
        if (ch == ' ') {
            ++answer;
        }
    }

    return answer + 1;
}

흐름

  1. 문자열 앞 뒤로 공백이 존재 할 수 있으므로 trim()
  2. 공백만 있는 문자열인 경우 0 return
  3. char array로 변환된 문자열을 돌면서 공백인 경우 count 증가
  4. 공백을 기준으로 단어가 만들어졌으니 공백 개수 + 1 return
    • ex) hello, wolrd! = 공백 1개, 문자 2개
  5. 끝

결과

결과

테스트 케이스

1
2
3
4
5
assertEquals(6, test.solution("The Curious Case of Benjamin Button"));
assertEquals(3, test.solution(" Mazatneunde Wae Teullyeoyo"));
assertEquals(2, test.solution("Teullinika Teullyeotzi "));
assertEquals(7, test.solution(" a b c d e f g "));
assertEquals(0, test.solution(" "));

전체 코드

https://github.com/jungguji/algorithm_training/blob/master/src/main/java/algorithm/baekjoon/string/%EB%8B%A8%EC%96%B4%EC%9D%98_%EA%B0%9C%EC%88%98.java

댓글 공유

  • page 1 of 1

Junggu Ji

author.bio


author.job