LeetCode 1829. Maximum XOR for Each Query

2023/01/04

문제

https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/

정렬된 n개의 음의 아닌 정수 배열 nums와 정수 maximumBit가 주어지고, 아래 쿼리를 n번 수행한다.

nums [0] XOR nums [1] XOR … XOR nums [nums.length-1] XOR k

를 최대화하는 k <2maximumBit의 음이 아닌 정수를 찾는데 이 때, k는 각 쿼리의 정답이다.
쿼리를 반복할 때 마다 배열 nums의 마지막 element를 제거하고, answer 배열을 반환하는데, 여기서 answer[i]는 i번째 쿼리의 정답 즉, k 이다.

코드

public int[] getMaximumXor(int[] nums, int maximumBit) {
    int[] pxor = getPrefixXOR(nums);

    int[] answer = new int[nums.length];

    int answerIndex = 0;
    int maxValue = (1 << maximumBit) - 1;

    for (int i = pxor.length-1; i > 0; --i) {

        answer[answerIndex++] = pxor[i] ^ maxValue;
    }

    return answer;
}

private int[] getPrefixXOR(int[] nums) {
    int[] psum = new int[nums.length + 1];

    for (int i = 1; i <= nums.length; ++i) {
        psum[i] = psum[i-1] ^ nums[i-1];
    }
    return psum;
}

흐름

누적합(prefix sum) 알고리즘을 통해 누적 XOR 배열을 구한다.
이 때, 2의 maximumBit승보다 작은 수 중에 가장 큰 수는 당연히 (2^maximumBit)-1 한 수 이므로, (2^maximumBit)-1 값을 변수에 할당해놓고,
nums.length의 길이인 N 번 만큼 쿼리를 반복하면서 마지막 원소를 제거하면서 k 값을 구해 answer[i]에 저장한다.
끝.

pxor[i] ^ maxValue가 K인 이유

void xorTEST() {
    int x = 93;
    int y = 12;
    int z = x ^ y;

    System.out.println("----- 초기값 -----");
    System.out.println("x = " + x);
    System.out.println("y = " + y);
    System.out.println("z = " + z);

    System.out.println("----- XOR -----");
    System.out.printf("x ^ y = %d(z)\n", x^y);
    System.out.printf("x ^ z = %d(y)\n", x^z);
    System.out.printf("y ^ z = %d(x)\n", y^z);
}

----- 초기값 -----
x = 93
y = 12
z = 81
----- XOR -----
x ^ y = 81(z)
x ^ z = 12(y)
y ^ z = 93(x)

우리가 구해야 하는 값은 쿼리의 값을 가장 크게 할 값인 K이고, 우리는 이미 가장 큰 값을 (2^maximumBit)-1 로 구해놓았으므로,
누적합 알고리즘으로 구한 XOR값에 가장 큰 값을 XOR하면 k가 나오게 된다.

결과

댓글 공유

백준 2485번: 가로수

2021/04/12

문제

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

코드

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    List<Integer> differences = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    int preValue = 0;

    int n = Integer.parseInt(br.readLine());
    while (n-- > 0) {
        int input = Integer.parseInt(br.readLine());
        list.add(input);

        if (preValue != 0) {
            differences.add(Math.abs(preValue - input));
        }

        preValue = input;
    }

    Collections.sort(list);

    int gcd = Integer.MAX_VALUE;
    for (int i = 1; i < differences.size(); i++) {
        int temp = gcd(differences.get(i-1), differences.get(i));
        gcd = temp > gcd ? gcd : temp;
    }

    int answer = 0;
    int pre = list.get(0);
    for (int i = 1; i < list.size(); i++) {
        if (list.get(i) - pre != gcd) {
            answer += ((list.get(i) - pre) / gcd) - 1;
        }
        pre = list.get(i);
    }

    System.out.println(answer);
}

private static int gcd(int a, int b) {
    return b!=0 ? gcd(b, a%b) : a;
}

흐름

입력 받은 값들을 뺀 값의 차를 구한 값으로 약수를 구하기 위한 differences,
입력 받은 값을 그대로 저장하는 list 변수 생성.
두 리스트 모두 n 만큼 돌면서 값을 저장하는데
differences의 경우 첫 번쨰 루프에서 값을 저장 할 수 없으므로(2 번쨰 값부터 첫 번째 값과 뺄 수 있으므로) 이전 값이 있는 경우에만 리스트에 저장한다.
가로수들 사이에 끼워넣어야 되는 가로수의 개수를 구해야 하므로 입력 받은 가로수의 위치를 정렬한다.
가로수 간의 최소 간격을 구하기 위해 아까 저장한 가로수 간의 차이를 구한 리스트 differences를 돌면서 유클리드 호제법을 이용해 최대공약수를 구하고, 구한 최대 공약수 중 가장 작은 값을 저장한다.
가로수 간의 차이값에서 최대 공약수를 구하는 이유는,
문제가 가로수를 일정한 간격으로 최대한 적게 심기게 하기 위한 문제 이므로 두 수에서 공통되는 값들 중 가장 큰 수인 최대 공약수를 구하고,
그 최대 공약수들 중 가장 작은 값이어야 모두 일정한 간격으로 심을 수 있으므로 최대 공약수 중 가장 작을 값을 구한다.
이렇게 잘 구한 값으로 이제 몇 개의 가로수를 더 심어야 하는지 알아내야 하므로
아까 정렬시킨 가로수 리스트를 반복 하면서 이전 가로수 와의 간격이 최대 공약수 보다 큰 녀석들이 있으면
그 녀석들 사이에 가로수를 심어야 되므로,
구한 간격을 최대 공약수로 나눈 값에서 -1 한 값을 더한다.
이 때 -1을 하는 이유는 두 수의 간격이므로 하나는 이미 심어져 있으니 -1 을 한다.
그렇게 추가로 심어야 하는 가로수의 개수를 모두 구하면
끝.

결과

댓글 공유

백준 10527번: Judging Troubles

2021/04/01

문제

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

코드

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());

    Map<String, Boolean> isDuplicate = new HashMap<>();
    Map<String, Integer> domJudge = new HashMap<>();

    for (int i = 0; i < n; i++) {
        String input = br.readLine();

        if (!isDuplicate.containsKey(input)) {
            isDuplicate.put(input, false);
        }

        domJudge.put(input, domJudge.getOrDefault(input, 0) + 1);
    }

    Map<String, Integer> kattis = new HashMap<>();

    for (int i = 0; i < n; i++) {
        String input = br.readLine();

        if (isDuplicate.containsKey(input)) {
            isDuplicate.put(input, true);
        }

        kattis.put(input, kattis.getOrDefault(input, 0) + 1);
    }

    List<Map.Entry<String, Integer>> entries1 = new ArrayList<>(domJudge.entrySet());
    List<Map.Entry<String, Integer>> entries2 = new ArrayList<>(kattis.entrySet());

    entries1.addAll(entries2);
    Collections.sort(entries1, (e1, e2) -> {
        if (e1.getKey().compareTo(e2.getKey()) > 0) {
            return 1;
        } else if (e1.getKey().compareTo(e2.getKey()) < 0) {
            return -1;
        } else {
            return Integer.compare(e1.getValue(), e2.getValue());
        }
    });

    int answer = 0;
    Set<String> set = new HashSet<>();
    for (int i = 0; i < entries1.size(); i++) {
        Map.Entry<String, Integer> entry = entries1.get(i);

        if (isDuplicate.getOrDefault(entry.getKey(), false) && set.add(entry.getKey())) {
            answer += entry.getValue();
        }
    }

    System.out.println(answer);
}

흐름

우선 이 문제는 domJudge와 kattis가 순서대로 n만큼씩 입력 받는 문제다.

예제를 보며 얘기하면

5
correct
wronganswer
correct
correct
timelimit
wronganswer
correct
timelimit
correct
timelimit

이렇게 되어 있을 때 위에 다섯 줄은 domJudge에서 채점한 결과고, 그 아래 다섯 줄은 kattis 채점한 결과다.

이걸 생각하고 프로그램을 작성하면

우선 양 쪽에서 채점된 결과들 중에 작은 녀석의 값을 골라야 하므로 채점 결과를 Key로 하는 Map을 만들고
n 만큼 돌면서 domJudge의 채점 결과를 저장하는데 이 때 처음나온 채점 결과는 Map에 false로 저장하고, 이전에 이미 나온 결과는 +1 해준다.
그 후 다시 n만큼 돌면서 kattis의 채점결과를 저장하는데
이 때는 전에 domJudge에서 나온 채점 결과 인지 확인해야 하므로 중복을 체크하기 위해 만든 Map에 채점 결과가 존재하면 그 key의 값을 true로 변경시켜서 양 쪽에서 모두 나온 결과 임을 저장한다.
그 후 양 쪽에서 모두 나온 채점 결과들 중 작은 값들을 더하기 위해
두 Map을 리스트로 변환 후 합쳐서 key와 value로 sorting 한다.
그 후 합친 리스트를 반복하면서..
채점 결과가 양 쪽 모두에서 나온 녀석이면서 이전에 더한 key가 아니라면 쭉 더하고
출력하고 끝낸다.

결과

다른 분의 코드

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String line = br.readLine().trim();
    int n = Integer.parseInt(line);
    Map<String, Integer> map = new HashMap<>();
    for(int i = 0; i < n; i++){
        String dom = br.readLine();
        map.put(dom, map.getOrDefault(dom, 0) + 1);
    }
    int cnt = 0;
    for(int i = 0; i < n; i++){
        String kattis = br.readLine();
        if(map.containsKey(kattis) && map.get(kattis) > 0){
            cnt++;
            map.put(kattis, map.get(kattis) - 1);
        }
    }
    System.out.println(cnt);
}

나 처럼 바보 같이 Map을 여러 개 쓰지 않고 하나의 맵에 +1, -1로 해서 겹치는 결과 인지 아닌지 판단했다.
나는 왜 이렇게 생각하지 못했을까? 다른 곳에서도 흔히 쓰이는 방식인데
오늘도 역시 반성해본다…

댓글 공유

백준 4796번: 캠핑

2021/03/25

문제

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

코드

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringBuilder sb = new StringBuilder();
    int i = 0;

    String input = "";
    while (!"0 0 0".equals(input = br.readLine())) {
        int[] lpv = convertStringArrayToIntegerArray(input.split(" "));

        int l = lpv[0];
        int p = lpv[1];
        int v = lpv[2];

        sb.append("Case ").append(++i).append(": ").append((v/p) * l + ((v%p) > l ? l : (v%p))).append("\n");
    }

    System.out.println(sb);
}

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

    return array;
}

흐름

V일 중에 연속되는 P일 동안 L일 만큼 휴가를 사용 할 수 있으므로
V에서 P를 나눈 값에서 L일을 곱하면 사용 가능한 휴가 일수가 구해지고
L이 V일에서 P일을 나눈 값보다 작을 땐 L일 만큼 휴가를 더 갈 수 있고
큰 경우엔 V % P 일 만큼 갈 수 있으므로 구한 값을 더하면
총 휴가 일수를 구할 수 있다.

결과

댓글 공유

백준 18870번: 좌표 압축

2020/12/15

문제

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

코드

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    br.readLine();
    Integer[] array = convertStringArrayToIntegerArray(br.readLine().split(" "));
    List<Integer> list = Arrays.asList(array.clone());

    Collections.sort(list);

    Map<Integer, Integer> map = new HashMap<>();
    int index = 0;
    for (int i : list) {
        if (!map.containsKey(i)) {
            map.put(i, index++);
        }
    }

    StringBuilder sb = new StringBuilder();
    for (int i : array) {
            sb.append(map.get(i)).append(" ");
    }

    System.out.println(sb.toString());
}

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

    return array;
}

흐름

입력받은 좌표를 저장한 리스트로 수정하면 출력 순서를 맞출 수 없으니 우선 좌표 list를 복사한다.
복사한 list를 정렬하고 순서대로 반복하면서 좌표값을 key로 index를 저장한다.
1. {-10 : 0}, {-9, 1}… {4,4}
입력받은 좌표를 순서대로 반복하면서 map에 key로 index를 가져온다.
끝

좌표 압축의 이유

문제의 예제인 좌표 {2 4 -10 4 -9}을 위와 같은 알고리즘으로 압축하면 {2 3 0 3 1}이 되는데 위 그림 처럼 압축된 점들도 같은 동일선상 안에 놓이게 된다.
이렇게 범위가 매우 넓은 좌표의 경우에 좌표를 인덱싱해서 처리 할 경우 손쉽게 처리 할 수 있게 된다.

결과

참고 사이트

댓글 공유

백준 1406번: 에디터

2020/12/14

문제

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

코드

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    char[] input = br.readLine().toCharArray();

    LinkedList<Character> list = new LinkedList<>();
    for (char c : input) {
        list.add(c);
    }

    ListIterator<Character> it = list.listIterator();
    while (it.hasNext()) {
        it.next();
    }

    int n = Integer.parseInt(br.readLine());

    while (n-- > 0) {
        String command = br.readLine();

        switch (command) {
            case "L" :
                if (it.hasPrevious()) {
                    it.previous();
                }
                break;
            case "D" :
                if (it.hasNext()) {
                    it.next();
                }
                break;
            case "B" :
                if (it.hasPrevious() && !list.isEmpty()) {
                    it.previous();
                    it.remove();
                }
                break;
            default:
                it.add(command.charAt(2));
                break;
        }
    }

    StringBuilder sb = new StringBuilder();
    for (char c : list) {
        sb.append(c);
    }

    System.out.println(sb);
}

이 문제는 로직보다 걸리는 시간이 문제였다.
처음엔 LinkedList를 그대로 사용해 add, remove를 했지만 시간초과로 인해 ListIterator을 이용해 해결했다.

ListIterator

List를 양방향으로 탐색하고, 루프 중에 리스트를 수정하고, 리스트에서 현재 위치를 가져올 수 있다.
커서는 previous()로 리턴되는 원소와 next()로 리턴되는 원소 사이에 존재한다.

1 2	Element(0) Element(1) Element(2) ... Element(n-1) cursor positions: ^ ^ ^ ^ ^

remove()와 set()를 호출해도 커서의 위치는 움직이지 않는다.
remove() 호출 시 next()혹은 preivous()에 의해 리턴된 마지막 요소를 리스트에서 제거한다.

case "B" :
        if (it.hasPrevious() && !list.isEmpty()) {
            it.previous();
            it.remove();
        }
        break;

결과

참고 사이트

댓글 공유

백준 11724번: 연결 요소의 개수

2020/12/08

문제

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

코드

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int[] nm = convertStringArrayToIntegerArray(br.readLine().split(" "));
    int n = nm[0];
    int m = nm[1];

    boolean[][] graph = new boolean[n+1][n+1];
    while (m-- > 0) {
        int[] xy = convertStringArrayToIntegerArray(br.readLine().split(" "));

        graph[xy[0]][xy[1]] = true;
        graph[xy[1]][xy[0]] = true;
    }

    int answer = 0;

    boolean[] isVisit = new boolean[n+1];
    for (int i = 1; i < graph.length; i++) {
        if (!isVisit[i]) {
            answer += bfs(isVisit, graph, i);
        }
    }

    System.out.println(answer);
}

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

    return array;
}

private static int bfs(boolean[] isVisit, boolean[][] graph,int startIndex) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(startIndex);
    isVisit[startIndex] = true;

    while (!queue.isEmpty()) {
        int x = queue.poll();

        for (int i = 1; i < isVisit.length; i++) {
            if (isVisit[i]) {
                continue;
            }

            if (graph[x][i]) {
                queue.offer(i);
                isVisit[i] = true;
            }
        }
    }

    return 1;
}

흐름

그래프의 연결 관계를 인접행렬로 만들기 위해 정점의 개수 + n한 크기의 2차원 배열을 만들고,
이 문제에서 그래프는 방향이 없는 무방향 그래프이기 때문에 a->b로 가는 간선이 있으면 b->a로 가는 간선도 있는 것이므로 대칭이 되도록 배열에 저장한다.
이후 정점의 개수만큼 루프 돌면서 연결요소의 개수를 구하는데 아직 간선이 연결되지 않은 정점일 경우에만 BFS 탐색을 통해 탐색한다.
queue를 이용해 bfs를 구현하는데 우선 탐색이 시작되는 정점의 index를 queue에 저장하고, isVisit[] 변수에도 true로 해당 index를 탐색했다고 저장한다.
queue가 빌 때 까지 반복하면서 queue에 저장된 index를 poll한다.
정점의 개수 만큼 반복하면서 이미 연결된 정점이면 넘어가고
아직 연결되지 않은 정점이면서 다른 정점과 연결된 정점이면 queue에 해당 index를 저장하고, 방문했으니 true도 저장한다.
queue가 비어 루프가 종료되면 연결 요소 하나가 완성된 것이므로 1을 return 하고 bfs를 종료한다.
return된 1들을 저장해 모든 정점을 탐색 후 종료한다.
끝

결과

참고 사이트

https://sarah950716.tistory.com/12

댓글 공유

백준 5525번: IOIOI

2020/12/02

문제

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

코드

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;
}

흐름

KMP 알고리즘 을 이용해 해결

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

KMP 알고리즘 해설

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

위키백과

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

실패함수

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;
}

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

KMP 알고리즘

실패함수 값 구하는 것과 동일하다.

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]

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

결국 정리하면, 처음 말한 것 처럼 이미 비교한 값은 다시 비교하지 않고 그 다음 부터 비교하는 방식으로 시간을 줄인다.
더 자세한 설명들은 글 마지막 참고 사이트를 찾아가면 다른 분들이 매우 자세하게 설명해주시고 계신다.

결과

테스트 케이스

1
2
3

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

참고 사이트

댓글 공유

프로그래머스: 방금 그 곡

2020/11/12

문제

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

코드

public String solution(String m, String[] musicinfos) {
    String answer = "(None)";

    m = getSharpReplace(m);

    int maxPlayTime = 0;

    for (String music : musicinfos) {
        String[] info = music.split(",");

        int playTimeToMinute = getPlayTime(info[0], info[1]);
        String melody = getMelody(playTimeToMinute, info[3]);

        if (melody.contains(m)) {
            if (maxPlayTime < playTimeToMinute) {
                answer = info[2];
                maxPlayTime = playTimeToMinute;
            }
        }
    }

    return answer;
}

private String getSharpReplace(String arg) {
    return arg.replace("C#", "1")
            .replace("D#", "2")
            .replace("E#", "3")
            .replace("F#", "4")
            .replace("G#", "5")
            .replace("A#", "6");
}

private int getPlayTime(String start, String end) {
    LocalTime startTime = convertLocalTime(start);
    LocalTime endTime = convertLocalTime(end);

    LocalTime playTime = endTime.minusHours(startTime.getHour()).minusMinutes(startTime.getMinute());

    return playTime.getHour() * 60 + playTime.getMinute();
}

private LocalTime convertLocalTime(String time) {
    String[] hourAndMinute = time.split(":");

    return LocalTime.of(Integer.parseInt(hourAndMinute[0]), Integer.parseInt(hourAndMinute[1]), 0);
}

private String getMelody(int playtime, String melody) {
    String sharpReplaceMelody = getSharpReplace(melody);
    StringBuilder sb = new StringBuilder();

    char[] array = sharpReplaceMelody.toCharArray();
    for (int i = 0; i < playtime; i++) {
        sb.append(array[i % sharpReplaceMelody.length()]);
    }

    return sb.toString();
}

흐름

“#”이 붙은 음계들을 유일한 값으로 치환한다.
곡 정보를 담은 musicinfos의 개수만큼 반복한다.
돌면서 “,”로 잘라 시작시간, 끝난시간, 곡 이름, 멜로디 순으로 구분하여 String array에 저장한다.
시작 시간과 끝난 시간을 LocalTime type으로 만들어서 끝난 시간에서 시작 시간을 빼서 얼마나 오래 방송 됐는지 playTime을 구한다.
곡 정보에 있는 멜로디에서도 “#”이 붙은 음계들을 1번에서 한 것과 같은 값으로 치환한다.
playtime에 따라 멜로디에 음계를 추가하기 위해 멜로디를 char array로 변경한다.
playtime 만큼 반복하면서 멜로디를 만든다.
1. playtime보다 멜로디가 짧은 경우엔 지금 멜로디에 음계를 이어 붙여 playtime 길이 만큼 만든다.
2. 멜로디가 더 긴 경우엔 playtime 만큼 자른다.
이렇게 구한 멜로디에 기억 중인 멜로디 m이 포함된다면 playtime이 가장 긴지 확인하고 곡 정보를 저장한다.
끝.

결과

번호	속도
테스트 1	통과 (1.31ms, 54.1MB)
테스트 2	통과 (1.38ms, 52.7MB)
테스트 3	통과 (3.19ms, 52.6MB)
테스트 4	통과 (1.33ms, 51.7MB)
테스트 5	통과 (1.44ms, 52.7MB)
테스트 6	통과 (1.42ms, 52.2MB)
테스트 7	통과 (2.26ms, 52.7MB)
테스트 8	통과 (2.27ms, 53.3MB)
테스트 9	통과 (2.38ms, 52.5MB)
테스트 10	통과 (2.31ms, 52MB)
테스트 11	통과 (2.24ms, 53.4MB)
테스트 12	통과 (2.03ms, 53.2MB)
테스트 13	통과 (2.27ms, 53.2MB)
테스트 14	통과 (2.23ms, 52.2MB)
테스트 15	통과 (2.19ms, 53.2MB)
테스트 16	통과 (2.22ms, 52.1MB)
테스트 17	통과 (1.78ms, 52.4MB)
테스트 18	통과 (2.22ms, 53MB)
테스트 19	통과 (2.66ms, 52.5MB)
테스트 20	통과 (2.42ms, 52.1MB)
테스트 21	통과 (2.41ms, 52.3MB)
테스트 22	통과 (3.55ms, 52.9MB)
테스트 23	통과 (3.94ms, 53.2MB)
테스트 24	통과 (2.15ms, 51.9MB)
테스트 25	통과 (1.24ms, 52.3MB)
테스트 26	통과 (1.30ms, 53.2MB)
테스트 27	통과 (1.41ms, 52.6MB)
테스트 28	통과 (1.12ms, 53.1MB)
테스트 29	통과 (12.67ms, 53.4MB)
테스트 30	통과 (13.24ms, 53.1MB)

테스트 케이스

assertEquals("HELLO", test.solution("ABCDEFG", new String[] {"12:00,12:14,HELLO,CDEFGAB", "13:00,13:05,WORLD,ABCDEF"}));
assertEquals("FOO", test.solution("CC#BCC#BCC#BCC#B", new String[] {"03:00,03:30,FOO,CC#B", "04:00,04:08,BAR,CC#BCC#BCC#B"}));
assertEquals("WORLD", test.solution("ABC", new String[] {"12:00,12:14,HELLO,C#DEFGAB", "13:00,13:05,WORLD,ABCDEF"}));
assertEquals("(None)", test.solution("CDEFGAC", new String[] {"12:00,12:06,HELLO,CDEFGA"}));
assertEquals("FOO", test.solution("CCB", new String[] {"03:00,03:10,FOO,CCB#CCB", "04:00,04:08,BAR,ABC"}));

댓글 공유

프로그래머스: 파일명 정렬

2020/11/12

문제

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

코드

public String[] solution(String[] files) {

    List<File> fileList = new ArrayList<>();
    for (int i = 0; i < files.length; i++) {
        char[] array = files[i].toCharArray();

        String originName = files[i];
        String head = "";
        Integer number = 0;

        boolean isString = true;
        int numberStartIndex = 0;
        for (int j = 0; j < array.length; j++) {
            if (isString && isNumber(array[j])) {
                head = new String(array, 0, j).toUpperCase();
                numberStartIndex = j;
                isString = false;
                continue;
            }

            if (!isString && !isNumber(array[j])) {
                number = Integer.parseInt(new String(array, numberStartIndex, j - numberStartIndex));
                isString = true;
                break;
            }
        }

        if (!isString) {
            number = Integer.parseInt(new String(array, numberStartIndex, array.length - numberStartIndex));
        }

        fileList.add(new File(originName, head, number, i));
    }

    sort(fileList);

    return fileList.stream()
            .map(File::getOriginName)
            .toArray(String[]::new);
}

private void sort(List<File> fileList) {
    fileList.sort((f1, f2) -> {
        if (f1.head.compareTo(f2.head) != 0) {
            return f1.head.compareTo(f2.head);
        } else if (f1.number.compareTo(f2.number) != 0) {
            return f1.number.compareTo(f2.number);
        } else {
            return f1.index.compareTo(f2.index);
        }
    });
}

private boolean isNumber(char ch) {
    return (48 <= ch && ch <= 57);
}

static class File {
    private final String originName;
    private final String head;
    private final Integer number;
    private final Integer index;

    public File(String originName, String head, Integer number, Integer index) {
        this.originName = originName;
        this.head = head;
        this.number = number;
        this.index = index;
    }

    public String getOriginName() {
        return this.originName;
    }

    public String getHead() {
        return this.head;
    }

    public Integer getNumber() {
        return this.number;
    }

    public Integer getIndex() {
        return this.index;
    }
}

흐름

file 개수만큼 반복하면서 파일명을 char array로 만든다.
char array를 숫자가 나올 때 까지 반복한다.
숫자가 나오면 0부터 숫자가 나온 index까지 짤라서 head 변수에 저장시키고 숫자가 시작된 index와 다음에 숫자인지 체크 할 flag 변수를 false로 변경한다.
head를 만들고 난 후엔 숫자만 뽑아서 number로 저장해야 하므로
돌면서 현재 문자가 아니고 지금 값도 숫자가 아니면 지금 index까지 잘라서 number에 저장한다.
만약 tail이 없어서 이번 조건문에 걸리지 않았다면, 숫자가 시직된 index부터 array 길이에서 숫자가 시작된 index를 뺀 크기 만큼 잘라서 number에 저장한다.
구한 head, number를 가지고 원래 파일명, head, number, 원래 순서를 갖는 File Object를 생성하고 List에 추가한다.
리스트를 문제의 제약조건 처럼 정렬한다.
1. head로 비교해서 정렬
2. head가 같으면 number로 비교해서 정렬
3. 둘 다 같으면 원래 순서대로 정렬
정렬한 List를 String[]로 만들어서 return 한다.
끝

결과

번호	속도
테스트 1	통과 (2.80ms, 52.3MB)
테스트 2	통과 (2.92ms, 52.8MB)
테스트 3	통과 (15.41ms, 54.1MB)
테스트 4	통과 (17.89ms, 54.3MB)
테스트 5	통과 (16.74ms, 54.3MB)
테스트 6	통과 (15.07ms, 53.3MB)
테스트 7	통과 (21.21ms, 54.5MB)
테스트 8	통과 (21.20ms, 53.8MB)
테스트 9	통과 (17.57ms, 53.6MB)
테스트 10	통과 (20.00ms, 53.5MB)
테스트 11	통과 (15.30ms, 53.8MB)
테스트 12	통과 (14.44ms, 54.1MB)
테스트 13	통과 (10.24ms, 53.8MB)
테스트 14	통과 (12.50ms, 54.1MB)
테스트 15	통과 (18.61ms, 54.1MB)
테스트 16	통과 (20.40ms, 53.9MB)
테스트 17	통과 (10.36ms, 53.8MB)
테스트 18	통과 (13.84ms, 54.6MB)
테스트 19	통과 (16.07ms, 54.4MB)
테스트 20	통과 (14.91ms, 53.8MB)

정렬을 stream에 추가 할 경우

stream sorted

return fileList.stream()
        .sorted(Comparator.comparing(File::getHead)
        .thenComparing(Comparator.comparing(File::getNumber)
        .thenComparing(File::getIndex)))
        .map(File::getOriginName)
        .toArray(String[]::new);

결과

번호	속도
테스트 1	통과 (10.64ms, 53.2MB)
테스트 2	통과 (18.65ms, 53.2MB)
테스트 3	통과 (25.96ms, 54.7MB)
테스트 4	통과 (24.73ms, 54.8MB)
테스트 5	통과 (20.97ms, 54.3MB)
테스트 6	통과 (29.57ms, 54.3MB)
테스트 7	통과 (30.45ms, 54.3MB)
테스트 8	통과 (24.91ms, 54.3MB)
테스트 9	통과 (26.40ms, 54.8MB)
테스트 10	통과 (28.88ms, 54.1MB)
테스트 11	통과 (22.73ms, 54.7MB)
테스트 12	통과 (25.60ms, 54.4MB)
테스트 13	통과 (22.06ms, 54.2MB)
테스트 14	통과 (19.49ms, 54.9MB)
테스트 15	통과 (17.53ms, 54.2MB)
테스트 16	통과 (20.05ms, 54.1MB)
테스트 17	통과 (18.01ms, 54.7MB)
테스트 18	통과 (18.53ms, 53.7MB)
테스트 19	통과 (26.25ms, 54.2MB)
테스트 20	통과 (20.81ms, 55.2MB)

테스트 케이스

assertArrayEquals(new String[] {"img1.png", "IMG01.GIF", "img02.png", "img2.JPG", "img10.png", "img12.png"}, test.solution(new String[] {"img12.png", "img10.png", "img02.png", "img1.png", "IMG01.GIF", "img2.JPG"}));
assertArrayEquals(new String[] {"A-10 Thunderbolt II", "B-50 Superfortress", "F-5 Freedom Fighter", "F-14 Tomcat"}, test.solution(new String[] {"F-5 Freedom Fighter", "B-50 Superfortress", "A-10 Thunderbolt II", "F-14 Tomcat"}));
assertArrayEquals(new String[] {"img100.p2ng", "img202.png123"}, test.solution(new String[] {"img202.png123", "img100.p2ng"}));
assertArrayEquals(new String[] {"foo010bar020.zip", "foo010bar030.zip"}, test.solution(new String[] {"foo010bar020.zip", "foo010bar030.zip"}));
assertArrayEquals(new String[] {"F-15", "F-17", "F-22"}, test.solution(new String[] {"F-22", "F-17", "F-15"}));

댓글 공유

문제

코드

흐름

pxor[i] ^ maxValue가 K인 이유

결과

문제

코드

흐름

결과

문제

코드

흐름

결과

다른 분의 코드

문제

코드

흐름

결과

문제

코드

흐름

좌표 압축의 이유

결과

참고 사이트

문제

코드

ListIterator

결과

참고 사이트

문제

코드

흐름

결과

참고 사이트

문제

코드

흐름

KMP 알고리즘 해설

실패함수

KMP 알고리즘

결과

테스트 케이스

참고 사이트

문제

코드

흐름

결과

테스트 케이스

문제

코드

흐름

결과

정렬을 stream에 추가 할 경우

stream sorted

결과

테스트 케이스

Junggu Ji