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

Lv. 2 빛의 경로 사이클 - 실패

 

참고한 풀이

https://jisunshine.tistory.com/175

[level2] 프로그래머스 - 빛의 경로 사이클(JAVA)

 

 

 

Lv. 2 전화번호 목록 - 실패

복습할 내용

배열.startsWith()

class Solution {
    public boolean solution(String[] phoneBook) {
        // 1. HashMap을 선언한다.
        Map<String, Integer> map = new HashMap<>();

        // 2. 모든 전화번호를 HashMap에 넣는다.
        for (int i = 0; i < phoneBook.length; i++) 
            map.put(phoneBook[i], i);
        
        // 3. 모든 전화번호의 substring이 HashMap에 존재하는지 확인한다.
        for (int i = 0; i < phoneBook.length; i++)
            for (int j = 0; j < phoneBook[i].length(); j++)
                if (map.containsKey(phoneBook[i].substring(0, j)))
                    return false;

        return true;
    }
}

출처: https://coding-grandpa.tistory.com/entry/프로그래머스-전화번호-목록-해시-Lv-2-자바-Java [개발자로 취직하기:티스토리]

참고한 풀이 

https://coding-grandpa.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A0%84%ED%99%94%EB%B2%88%ED%98%B8-%EB%AA%A9%EB%A1%9D-%ED%95%B4%EC%8B%9C-Lv-2-%EC%9E%90%EB%B0%94-Java

[프로그래머스] 전화번호 목록 (해시 Lv. 2) - 자바 Java

 

Lv. 2 프린터 - 실패

복습할 내용 : equals() 

 

단순하게 중요도가 높으면 앞으로 보내고 같다면 location순서대로 나열해버리는 실수.

import java.util.*;
import java.io.*;
//내가 원하는 프린트가 몇번째로 인쇄되는지.
//프린트를 객체로 만듬(location과 중요도 프로퍼티를 가짐) -> 정렬하는 방법.

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        
        ArrayList<Print> list = new ArrayList<Print>();
        
        for(int i = 0 ; i < priorities.length ; i++){
            list.add(new Print(i,priorities[i]));
        }        
        
        Collections.sort(list);
        
        for(int i = 0 ; i < priorities.length ; i++){
            Print p = list.get(i);
            if(p.location == location){
                answer = i;
                break;
            }
            
        }   
        return answer;
    }
}
//프린트를 객체로 만듬(location과 중요도 프로퍼티를 가짐)
class Print implements Comparable<Print>{
    int location = 0 ;
    int importance = 0;
    
    Print(int loca, int impo){
        location = loca;
        importance = impo;
    }
    
    @Override
    public int compareTo(Print other){
        // 중요도 순 내림차순
        if(other.importance != importance){
            return other.importance - importance;
        }
        else{
            //로케이션 오름차순
            return location - other.location;
        }
        
    }
}

 

참고한 코드

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    class Task{
        int location;
        int priority;
        public Task(int location, int priority) {
            this.location = location;
            this.priority = priority;
        }
    }
    public int solution(int[] priorities, int location) {
        int answer = 0;

        Queue<Task> queue = new LinkedList<>();

        for(int i=0; i<priorities.length; i++){
            queue.add(new Task(i, priorities[i]));
        }

        int now=0;
        while(!queue.isEmpty()){
            Task cur = queue.poll();
            boolean flag = false;
            for(Task t : queue){
                if(t.priority>cur.priority){
                    flag = true;
                }
            }
            if(flag) { // 우선순위 높은게 있으면 뒤로 보낸다
                queue.add(cur);
            }else{
                now++;
                if(cur.location == location) {
                    answer = now;
                    break;
                }

            }
        }
        return answer;
    }
}

 

https://velog.io/@yanghl98/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%94%84%EB%A6%B0%ED%84%B0-JAVA%EC%9E%90%EB%B0%94

[프로그래머스] 프린터 (JAVA/자바)

 

 

Lv. 2 문자열 압축 - 실패

실패한 내 풀이(1) : Map을 쓰는 바람에 바로 옆의 문자열이 아닌 동일한 문자열도 같이 압축해버림...

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

//압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return
class Solution {
    public int solution(String s) {
        int answer = 1000;
        for(int i = 1; i<= s.length(); i++){
            int temp = press(i, s);
            answer = Math.min(temp, answer);
        }
        
        return answer;
    }
   
    public int press(int unit, String s){
        
        int resultCount = 0;
        //(문자열, 겹치는 개수.)
        Map<String,Integer> map = new HashMap<String,Integer>();
        int i = 0;
        while(i < s.length()){
            if(i + unit >= s.length()){
                //겹친다면
                if(map.containsKey(s.substring(i))){
                    int count = map.get(s.substring(i));
                    map.put(s.substring(i),count++);
                }else{
                    map.put(s.substring(i),1);
                }
                
                map.put(s.substring(i),1); //범위 밖이면 그냥 전부 다 뽑아서 추가.    
            }else{
                //겹친다면
                if(map.containsKey(s.substring(i, i+unit))){
                    int count = map.get(s.substring(i, i+unit));
                    map.put(s.substring(i, i+unit),count++);
                }else{
                    map.put(s.substring(i, i+unit),1);
                }    
            }
            i = i + unit;
        }
        
        for(String a : map.keySet()){
            if(map.get(a) ==1 ){
                resultCount =resultCount+ a.length();
            }else if(map.get(a) >1){
                resultCount =resultCount+ a.length() + 1;
            }
        }
        
        
                
        return resultCount;
    }
                         
            
        
        
        
    
}

 

 

참고한 풀이 : 

class Solution {
    public int solution(String s) {
        int answer = s.length();
    
        //i개 단위로 자르며 반복
        for(int i = 1; i <= s.length() / 2; i++) {
            //타겟 문자 패턴 설정
            String target = s.substring(0, i);
            String cur = ""; //현재 문자열
            int cnt = 1; //압축 카운트
            StringBuilder sb = new StringBuilder();
            
            for(int start = i; start <= s.length(); start += i) {
                //비교할 현재 문자열
                //다음 자를 문자열의 길이가 단위보다 작으면 남은 글자를 저장
                if(start + i >= s.length()) {
                    cur = s.substring(start, s.length());
                }
                else {
                    cur = s.substring(start, start + i);
                }
            
                //문자열이 같으면 압축카운트 증가
                if(cur.equals(target)) {
                    cnt++;
                }
                //다르면 압축된 문자열을 추가하고 타겟 패턴 변경
                else if(cnt == 1){
                    sb.append(target);
                    target = cur;
                }
                else {
                    sb.append(cnt).append(target);
                    target = cur;
                    cnt = 1;
                }
            }
            //자르고 마지막에 남는 문자열 추가
            if(i != target.length()) sb.append(target);
        
            answer = Math.min(answer, sb.toString().length());
        }
    
        return answer;
    }
}

출처

https://hyojun.tistory.com/entry/Programmers-%EB%AC%B8%EC%9E%90%EC%97%B4-%EC%95%95%EC%B6%95-Java

[프로그래머스] 문자열 압축 - Java

 

 

 

 

Lv. 2 오픈채팅방 - 성공

처음엔 현재 방에 존재했던 유저의 정보를 ArrayList에 저장하는 방법을 생각하였지만 순회하면서 유저를 찾는 것 보단

map에 저장해서 유저 정보를 갱신하는 것이 효과적이라고 판단하여 바꾸느라 시간이 조금 더 걸림.

class Solution {
    public String[] solution(String[] record) {
        String[] answer = {};
        
        Map<String,User> map = new HashMap<String,User>();
        
        for(String s : record){
            String[] arr = s.split(" ");
            //유저 데이터 추가.
            if(arr.length > 2){
                map.put(arr[1], new User(arr[1],arr[2]));
            }
        }
        
        ArrayList<String> result = new ArrayList<String>();
        for(int i = 0 ; i < record.length; i++){
            String[] arr = record[i].split(" ");
            if(arr[0].equals("Enter")){
                result.add(map.get(arr[1]).nickName +"님이 들어왔습니다.");
            }else if(arr[0].equals("Leave")){
                result.add(map.get(arr[1]).nickName +"님이 나갔습니다.");
            }else{
                continue;
            }
            
        }
        answer = new String[result.size()];
        for(int i = 0 ; i < result.size(); i++){
            answer[i] = result.get(i); 
        }
            return answer;
    }
}

class User {
    String id = "";
    String nickName = "";
    User(String myId, String myNick){
        this.id = myId;
        this.nickName = myNick;
    }
    
}

 

Lv. 2 카카오프렌즈 컬러링북 - 성공

 

 

1. 0도 색으로 포함 시키는 실수. (0인 영역도 dfs탐색을 통해서 별도의 색으로 포함시키는 실수)

2. 0만 아니라면 1이든 3이든 같은 영역으로 dfs탐색이 되도록 만드는 실수

문제의 채점이 조금 이상하다는 말이 있음.

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

//문제를 보자마자 bfs / dfs라는 것을 깨달음.
//몇 개의 영역이 있는지와 가장 큰 영역은 몇 칸으로 이루어져 있는지를 리턴

class Solution {
    
    public int[][] dir = {{1,0}, {-1,0}, {0,1},{0,-1}};
    public int[][] matrix = {};
    public boolean[][] visited = {};
    int area = 0;
    int numberOfArea = 0;
    int maxSizeOfOneArea = 0;
    
    public int[] solution(int m, int n, int[][] picture) {    
        matrix = picture;
        
        
        visited = new boolean[picture.length][picture[0].length];

        
        for(int i = 0 ; i <picture.length ; i++){
            for(int j = 0 ; j < picture[0].length ; j++){
                dfs(i,j,0, matrix[i][j]);
            }
        }
        
        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    
    public void dfs(int x, int y,int start,int color){
        //방문한 적이 있다면 종료, 색이 없다면 종료, 색이 다른 색이면 종료
        if(visited[x][y] == true || matrix[x][y] == 0 || color != matrix[x][y]){
            return;
        }
        if(start == 0){
            //처음 보는 영역인 경우 영역 수 증가.
            area = 1;
            numberOfArea++;
        }else if(start == 1){
            area++;
            maxSizeOfOneArea = Math.max(area, maxSizeOfOneArea);
        }
        
        visited[x][y] = true;
        int nextX = x;
        int nextY = y;
        for(int i = 0 ; i < dir.length; i++){
            nextX = nextX + dir[i][0];
            nextY = nextY + dir[i][1];
            if(nextX >= 0 && nextX < matrix.length && nextY >= 0 && nextY < matrix[0].length){
                dfs(nextX, nextY,1, color);
            }
            
        }
        
    }
    
}