프로그래머스LV2_14

튜플

접근 과정

1. 중복은 없으므로 Set을 활용한다고 판단
2. 주어진 문자열을 적절히 분리
3. 분리된 문자열을 길이 순으로 정렬
4. ,를 기준으로 분리하여 발견되지 않은 원소만 정답 배열에 넣어 해결

시행착오

• 처음에 정규식으로 문자열을 분리하는 부분을 구글링으로 찾았다.

해결 코드

• 접근 과정대로 구현하여 해결

import java.util.*;

class Solution {
    public int[] solution(String s) {
        // 앞 뒤 중괄호 제거
        s = s.substring(2, s.length() - 2);
        // },{ 로 분리
        String[] arr = s.split("\\},\\{");
        Arrays.sort(arr, (s1, s2) -> s1.length() - s2.length());
        List<Integer> ans = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for(String str : arr){
            String[] tuple = str.split(",");
            for(String t : tuple){
                int num = Integer.parseInt(t);
                if(!set.contains(num)){
                    set.add(num);
                    ans.add(num);
                }
            }
        }
        return ans.stream().mapToInt(i -> i).toArray();
    }
}

시간 및 공간 복잡도

• 시간 복잡도(입력 문자열의 길이를 L, 튜플 원소의 개수를 N)

• 공간 복잡도

롤케이크 자르기

접근 과정

1. 전체를 돌면서 토핑과 토핑의 개수를 맵에 저장
2. 전체를 한번 더 돌면서 집합에 각 토핑을 넣고 맵에서 해당 토핑의 개수를 1개 빼면서 0개가 되면 맵에서 제거
3. 집합의 크기와 맵의 크기가 같으면 방법을 늘림

시행착오

• 2개의 집합으로 절반으로 나눴을 때 종류가 같은지 비교했는데 시간 초과가 남
• 시간 복잡도 : O(N^2)

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        for(int i = 0; i < topping.length - 1; i++){
            Set<Integer> s1 = new HashSet<>();
            Set<Integer> s2 = new HashSet<>();
            for(int j = 0; j <= i; j++){
                s1.add(topping[j]);
            }
            for(int j = i + 1; j < topping.length; j++){
                s2.add(topping[j]);
            }
            if(s1.size() == s2.size()) answer++;
        }
        return answer;
    }
}

해결 코드

• 시간 초과 문제를 해결하기 위해 O(N)으로 푸는 방법을 AI의 도움을 받아 해결했다.
• AI의 도움을 최대한 안 받아야 하는데 버릇처럼 받게 된다…안쓰고 생각하는 버릇을 들여야겠다.

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        Set<Integer> s = new HashSet<>();
        Map<Integer, Integer> m = new HashMap<>();
        for(int t : topping){
            m.put(t, m.getOrDefault(t, 0) + 1);
        }
        for(int t : topping){
            s.add(t);
            m.put(t, m.get(t) - 1);
            if(m.get(t) == 0) m.remove(t);
            if(s.size() == m.size()) answer++;
        }
        return answer;
    }
}

시간 및 공간 복잡도

• 시간 복잡도(토핑의 길이를 N이라 했을 때)

• 공간 복잡도(맵과 집합에 저장해야 하므로)

개선

• 자료구조를 쓰지 않고 해결하는 방법을 다른 사람 풀이에서 보고 개선을 시도하였다.
• 원소가 10000까지이므로 10001로 배열을 만들어 오른쪽과 왼쪽의 토핑을 넣고 종류를 카운팅하여 비교하면 해결

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        int n = topping.length;
        int[] rightCount = new int[10001]; 
        int rightType = 0;
        for (int t : topping) {
            if (rightCount[t] == 0) rightType++;
            rightCount[t]++;
        }
        boolean[] leftExists = new boolean[10001];
        int leftType = 0;
        for (int t : topping) {
            if (!leftExists[t]) {
                leftExists[t] = true;
                leftType++;
            }
            rightCount[t]--;
            if (rightCount[t] == 0) {
                rightType--;
            }
            if (leftType == rightType) answer++;
            if (leftType > rightType) break;
        }

        return answer;
    }
}

게임 맵 최단거리

접근 과정

1. 경로를 따라 이동해야 하므로 dfs나 bfs 활용을 생각
2. 방문 했던 곳을 체크하고 현재 좌표와 거리를 생각해야 하므로 boolean 배열과 상태 클래스를 만들어 활용
3. 이동하려는 좌표가 맵을 넘어가는지, 방문하지 않은 곳인지, 벽이 아닌지 체크하여 bfs 수행
4. 큐가 빌 때까지 끝을 못찾으면 -1 반환

시행착오

• 접근 과정대로 해결

해결 코드

• 큰 어려움 없이 접근 과정대로 bfs로 해결

import java.util.*;

class Solution {
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    
    class Status{
        int x;
        int y;
        int d;
        
        Status(int x, int y, int d){
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
    
    public int solution(int[][] maps) {
        int answer = bfs(0, 0, maps);
        return answer;
    }
    
    private int bfs(int sx, int sy, int[][] maps){
        Queue<Status> q = new LinkedList<>();
        q.add(new Status(sx, sy, 1));
        int r = maps.length, c = maps[0].length;
        boolean[][] visited = new boolean[r][c];
        visited[0][0] = true;
        while(!q.isEmpty()){
            int x = q.peek().x;
            int y = q.peek().y;
            int d = q.peek().d;
            q.poll();
            if(x == r - 1 && y == c - 1){
                return d;
            }
            for(int i = 0; i < 4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
                if(maps[nx][ny] == 1 && !visited[nx][ny]){
                    q.add(new Status(nx, ny, d + 1));
                    visited[nx][ny] = true;
                }
            }
        }
        return -1;
    }
}

시간 및 공간 복잡도

• 시간 복잡도 (N: 행, M: 열)

• 공간 복잡도 (N: 행, M: 열)

타겟 넘버

접근 과정

1. 더하거나 빼는 경우의 경로를 관리한다고 생각하여 dfs나 bfs를 활용
2. 현재 인덱스의 정수를 더하거나 빼는 경로를 모두 체크
3. 현재 인덱스가 끝이면 타겟과 같은 비교하여 answer를 +1 하여 해결

시행착오

• 접근 과정에서 이전에 푼 c++풀이를 참고하였다… 😱

해결 코드

• 접근 과정대로 dfs로 구현하여 해결

class Solution {
    int answer = 0;
    
    public int solution(int[] numbers, int target) {
        dfs(0, target, numbers, 0);
        return answer;
    }
    
    private void dfs(int cur, int target, int[] numbers, int idx){
        if(idx == numbers.length){
            if(cur == target) answer++;
            return;
        }
        dfs(cur + numbers[idx], target, numbers, idx + 1);
        dfs(cur - numbers[idx], target, numbers, idx + 1);
    }
}

시간 및 공간 복잡도

• 시간 복잡도 (숫자의 개수를 N)

• 공간 복잡도 (숫자의 개수를 N)

개선

• answer를 지역 변수로 두지 않고 해결하는 방식을 찾아 개선해보았다.

class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(0, target, 0, numbers);
    }
    
    private int dfs(int cur, int target, int idx, int[] numbers){
        if(idx == numbers.length){
            return (cur == target)? 1 : 0;
        }
        return dfs(cur + numbers[idx], target, idx + 1, numbers) 
            + dfs(cur - numbers[idx], target, idx + 1, numbers);
    }
}

뉴스 클러스터링

접근 과정

1. 중복을 허용하므로 맵을 활용하여 해당 문자열의 개수로 저장
2. 2개의 맵의 키를 집합으로 받아 돌면서 합집합과 교집합의 개수를 구함
3. 문제 요구대로 교집합/합집합 * 65536 을 하고 정수 부분만 반환

시행착오

• 중복 허용을 놓쳐서 집합으로 풀었다가 실패했다.

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        double n = 65536.0;
        Set<String> s1 = new HashSet<>();
        Set<String> s2 = new HashSet<>();
        Set<String> s3 = new HashSet<>();
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        for(int i = 0; i < str1.length() - 1; i++){
            String str = str1.substring(i, i + 2);
            if (!str.matches("^[a-zA-Z]+$")) continue;
            s1.add(str);
            s3.add(str);
        }
        for(int i = 0; i < str2.length() - 1; i++){
            String str = str2.substring(i, i + 2);
            if (!str.matches("^[a-zA-Z]+$")) continue;
            s2.add(str);
            s3.add(str);
        }
        int sum = s3.size();
        int cross = (s1.size() + s2.size()) - s3.size();
        double ans = (double) cross / sum * n;
        System.out.println((double) cross / sum);
        return (int)ans;
    }
}

해결 코드

• 중복 허용 케이스를 생각하여 맵을 활용해 구현

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        Map<String, Integer> m1 = new HashMap<>();
        Map<String, Integer> m2 = new HashMap<>();
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        // str1 처리
        for(int i = 0; i < str1.length() - 1; i++){
            String s = str1.substring(i, i + 2);
            if (!s.matches("^[a-z]{2}$")) continue;
            m1.put(s, m1.getOrDefault(s, 0) + 1);
        }
        // str2 처리
        for(int i = 0; i < str2.length() - 1; i++){
            String s = str2.substring(i, i + 2);
            if (!s.matches("^[a-z]{2}$")) continue;
            m2.put(s, m2.getOrDefault(s, 0) + 1);
        }
        // 합, 교집합 계산
        int intersection = 0;
        int union = 0;
        Set<String> keys = new HashSet<>();
        keys.addAll(m1.keySet());
        keys.addAll(m2.keySet());
        for(String key : keys){
            int c1 = m1.getOrDefault(key, 0);
            int c2 = m2.getOrDefault(key, 0);
            intersection += Math.min(c1, c2);
            union += Math.max(c1, c2);
        }
        if(union == 0) return 65536;
        return (int)((double) intersection / union * 65536);
    }
}

시간 및 공간 복잡도

• 시간 복잡도(두 문자열의 길이를 각각 N, M)

• 공간 복잡도(두 문자열의 길이를 각각 N, M)