[Algorithm] 6월21일 알고리즘 연습(프로그래머스 LEVEL2) - 에이젠

Lv. 2 괄호 변환 - 실패

내 풀이(1) : 정확도 20%

중간에 문제를 안 읽은 것이 원인... 처음부터 다시 구현했어야 한다.

import java.io.*;
import java.util.*;

class Solution {
    public String solution(String p) {
        String answer = "";
        StringBuilder sb = new StringBuilder();
        StringBuilder tempSb = new StringBuilder();
        
        Stack<Character> stack = new Stack<Character>();
        char[] arr = p.toCharArray();
        int reverseCount = 0; //괄호 반전시킬 개수
        
        for(int i = 0; i < p.length(); i++){
            if(arr[i] == '(' && reverseCount == 0){
                stack.push(arr[i]);
                sb.append(tempSb.toString());
                tempSb.setLength(0);
                sb.append('(');
            }else if(!stack.isEmpty() && stack.peek() == '(' && arr[i] == ')'){
                stack.pop();
                
                sb.append(tempSb.toString());
                tempSb.setLength(0);
                sb.append(')');
            }else if(arr[i] == ')' && stack.isEmpty()){//먼저 닫는 괄호가 나타난다면
                reverseCount++;
                tempSb.append('('); //반전시키고 임시 저장소에 넣어두기
            }else if(arr[i] == '(' && reverseCount != 0){
                reverseCount--;
                tempSb.append(')');//반전시키고 임시 저장소에 넣어두기.
            }
        }
            
        if(tempSb.length() != 0){
            sb.append(tempSb.toString());
        }
        
        answer = sb.toString();
        return answer;
    }
}

 

참고한 풀이

https://ilmiodiario.tistory.com/91

[프로그래머스] level2. 괄호 변환 (자바 JAVA)

 

 

Lv. 2 [1차] 뉴스 클러스터링

참고한 풀이

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        Map<String, Integer> str1Map = new HashMap<>();
        Map<String, Integer> str2Map = new HashMap<>();

        for (int i = 0; i < str1.length()-1; i++){
            String temp1 = str1.substring(i, i+2);

            if (temp1.matches("[a-z]{2,2}")){
                if (str1Map.containsKey(temp1)){
                    str1Map.replace(temp1, str1Map.get(temp1)+1);
                } else{
                    str1Map.put(temp1, 1);
                }
            }
        }

        for (int i = 0; i < str2.length()-1; i++){
            String temp2 = str2.substring(i, i+2);

            if (temp2.matches("[a-z]{2,2}")){
                if (str2Map.containsKey(temp2)){
                    str2Map.replace(temp2, str2Map.get(temp2)+1);
                } else{
                    str2Map.put(temp2, 1);
                }
            }
        }

        double gyo = 0;
        double hap = 0;
        // 1:2, 2:2, 3:1   1:1, 2:2, 4:1, 5:1
        for (String key : str1Map.keySet()){
            if (str2Map.containsKey(key)){
                gyo += Math.min(str1Map.get(key), str2Map.get(key));
                hap += Math.max(str1Map.get(key), str2Map.get(key));
                str2Map.replace(key, 0);
            } else{
                hap += str1Map.get(key);
            }
            str1Map.replace(key, 0);
        }
        for (String key : str2Map.keySet()){
            hap += str2Map.get(key);
        }

        if (gyo == 0 && hap == 0){
            answer = 65536;
        } else{
            double div = gyo / hap * 65536;
            answer = (int)div;
        }
        return answer;
    }
}

https://tmdrl5779.tistory.com/204

[프로그래머스] [1차] 뉴스 클러스터링 (Java 자바)

 

Lv. 2 거리두기 확인하기 - 실패 

파티션(X)를 벽이라고 생각하고 각각 응시자의 위치로부터 BFS를 수행한다. 거리 2 이하에 있는 경우 발견시 false를 리턴하면 되겠다.

스택이나 배열에 배열 넣으면 안되나??

내풀이(1) : 메모리 초과

거리를 저장해두는 배열때문에 메모리를 초과한 것 같다.

 

부끄럽지만 스택을 써버리는 실수... BFS는 Queue를 써야한다.

 

import java.util.*;
import java.io.*;

class Solution {
    String[][] matrix = {{}};
    int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    int[][] count = new int[5][5];
    int[] answer = new int[5];
    
    //bfs를 위한 스택
    Stack<Integer> stack = new Stack<Integer>();
    public int[] solution(String[][] places) {
        
        matrix  = places;
       
        
       
        for(int i = 0; i < 5; i++){
            //각 대기실 자리 탐색
            for(int j = 0; j <5; j++){
                for(int k = 0; k < 5; k++){
                    if(matrix[i][j].charAt(k) == 'P') {
                        stack.push(i); //행 넣기
                        stack.push(j); //열 넣기
                    }
                }
            }
            while(!stack.empty()){
                int row = stack.pop();
                int col = stack.pop();
                bfs(i,row,col);
            }
            //대기실 옮기기 전 스택 초기화
            Arrays.fill(count, 0);
            stack.clear();
        }
        
        return answer;
    }
    //row행 col열의 자리에서 탐색 시작.
    public void bfs(int room,int row, int col){
        //벽이라면
        if(matrix[room][row].charAt(col) == 'X'){
            return;
            //사람이라면
        }else if(matrix[room][row].charAt(col) == 'P'){
            return;
            //규칙을 어긴 사람을 만나면
        }else if(matrix[room][row].charAt(col) == 'P'&& count[row][col] >=2){
            answer[room] = 0;
            return;
        }else if(count[row][col] > 2){
            //가까운 거리에 없다면 
             answer[room] = 1;
            return;
        }
        
        //탐색 후보 추가.
        for(int i = 0 ; i < 4; i++){
            Integer nx = row + dir[i][0];
            Integer ny = col + dir[i][1];
            if(nx >= 0 && nx < 5 && ny >=0 && ny < 5){
                stack.push(nx);
                stack.push(ny);
                count[nx][ny] = count[row][col]+1;
            }else{
                continue;
            }
        }

    }
}

BFS안에서 큐를 생성하고 그 안에서 반복문을 통해 탐색해야함.

탐색 시작점으로부터 거리를 따로 저장해두지 않아도 됨.

참고한 풀이

class Solution {
    public static int[] solution(String[][] places) {
        int[] answer = new int[places.length];

        for (int i = 0; i < places.length; i++) {
            String[] p = places[i];

            boolean isOk = true;
            for (int r = 0; r < 5 && isOk; r++) {
                for (int c = 0; c < 5 && isOk; c++) {
                    if (p[r].charAt(c) == 'P') {
                        if (!bfs(r, c, p))
                            isOk = false;
                    }
                }
            }
            answer[i] = isOk ? 1 : 0;
        }

        return answer;
    }

    private static boolean bfs(int r, int c, String[] p) {
        int dr[] = { -1, 1, 0, 0 };
        int dc[] = { 0, 0, -1, 1 };

        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[] { r, c });

        while (!queue.isEmpty()) {
            int[] position = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nr = position[0] + dr[i];
                int nc = position[1] + dc[i];

                if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5 || (nr == r && nc == c))
                    continue;

                int d = Math.abs(nr - r) + Math.abs(nc - c);

                if (p[nr].charAt(nc) == 'P' && d <= 2)
                    return false;
                else if (p[nr].charAt(nc) == 'O' && d < 2)
                    queue.offer(new int[] { nr, nc });
            }
        }

        return true;
    }
}

https://jisunshine.tistory.com/m/148

[level2] 프로그래머스 - 거리두기 확인하기(JAVA)