쌉쌀한 무화과의 개발로그

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12927

📝문제

문제 설명

📝풀이

우선순위 큐를 이용하여 문제 해결

import java.util.*;
class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int i=0; i<works.length; i++){
            pq.offer(works[i]);
        }
        
        int max;
        while(n>0){
            if(pq.peek()==0)
                return 0;
            pq.offer(pq.poll()-1);
            n--;
        }
        
        while(!pq.isEmpty()){
            answer+= Math.pow(pq.poll(), 2);
        }
        
        return answer;
    }
}

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162

📝문제

[문제 설명]

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

📝풀이

bfs 풀이

import java.util.*;

class Solution {
    static boolean[] visit;
    static Queue<Integer> queue= new LinkedList<Integer>();
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visit = new boolean[n];
        
        for(int i=0; i<n; i++){
            if(visit[i]) {
                continue;
            }
            answer++;
            bfs(computers, i, n);
        }
        
        return answer;
    }
    
    public void bfs(int[][] arr, int start, int len){
        int x;
        queue.offer(start);
        
        while(!queue.isEmpty()){
            x= queue.poll();
            
            for(int y=0; y<len; y++){
                if((arr[y][x]==1 || arr[x][y]==1) && !visit[y]){
                    visit[y]= true;
                    queue.offer(y);
                }
            }
        }
    }
}

반례

dfs / bfs 풀 때 보통 input 배열 기준으로 상하좌우로 움직이다보니, 처음에 이 문제를 잘못 이해했었는데요.

'프로그래머스 질문하기' 에서 어떤 분이 알려주신 반례로 문제를 다시 생각해보니 올바르게 이해가 되었습니다.

혹시 문제가 안풀리시는 분들 참고하세요.

[문제 설명]

다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다.

지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.

만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다.

단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다.

즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다.

다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없습니다.

한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없습니다.

지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.

​

제한사항

rectangle의 세로(행) 길이는 1 이상 4 이하입니다.

rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태입니다.

직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.

서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다.

문제에 주어진 조건에 맞는 직사각형만 입력으로 주어집니다.

charcterX, charcterY는 1 이상 50 이하인 자연수입니다.

지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.

itemX, itemY는 1 이상 50 이하인 자연수입니다.

지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.

캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.

전체 배점의 50%는 직사각형이 1개인 경우입니다.

전체 배점의 25%는 직사각형이 2개인 경우입니다.

전체 배점의 25%는 직사각형이 3개 또는 4개인 경우입니다.

​

입출력 예

​

입출력 예 설명

입출력 예 1)

캐릭터 위치는 (1, 3)이며, 아이템 위치는 (7, 8)입니다. 위 그림과 같이 굵은 선을 따라 이동하는 경로가 가장 짧습니다.

​

입출력 예 2)

캐릭터 위치는 (9, 7)이며, 아이템 위치는 (6, 1)입니다. 위 그림과 같이 굵은 선을 따라 이동하는 경로가 가장 짧습니다.

​

입출력 예 3)

캐릭터 위치는 (1, 1)이며, 아이템 위치는 (4, 7)입니다. 위 그림과 같이 굵은 선을 따라 이동하는 경로가 가장 짧습니다.

​

입출력 예 4, 5)

설명 생략

>문제 풀이

길을 찾으려면 도형들의 테두리가 필요합니다.

도형 하나 받고 다음 도형을 받을 텐데, 테두리를 제외하고 내부는 필요가 없습니다.

​

​

1) int map[101][101]

- 꺾이는 코너 부분에서 쉽게 계산하기 위해,

입력되는 좌표는 1~50이지만 2배로 확장해서 그려줄 것입니다.

​

2) 주어진 rectangle[][] 도형 정보에 따라 map에 채워넣습니다.

이처럼 테두리를 표시할 때, 겹쳐서 테두리가 될 수 없는 부분과 진짜 테두리를 구분해줘야합니다.

- 1. 테두리에는 1을 넣어주고, 내부에는 2를 넣어줄 것입니다.

- 2. 다음 그려질 도형이, 앞에 이미 그려진 도형이랑 겹칠 수 있습니다.

- 도형의 내부이면 2를 넣습니다.

- 테두리에는 1을 넣되, 이미 값이 2로 채워져 있는 경우는 2로 남겨둡니다.

(어차피 다른 도형의 내부니까 전체 테두리가 될 수 없음)

​

3) bfs로 출발점에서 목표 지점까지 양쪽에서 출발합니다.

만든 map이 2배 확장된 공간이기 때문에 좌표도 x2 해서 계산합니다.

​

4) return answer;

앞서 좌표를 x2해서 계산해주었으므로 정답을 반환할 때는 /2 해야합니다.

>전체 코드

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

class Solution {
    static int[][] map;
    static int answer;
    //character->item(목표 포인트)
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        answer=0;
        
        //1) map을 만든다.
        map= new int[101][101];
        
        //2) 좌표에 따라 map에 값을 넣을건데, 테두리에만 1을 넣을것이다.(*좌표는 두배로)
        for(int i=0; i<rectangle.length; i++){
            fill(2*rectangle[i][0], 2*rectangle[i][1], 2*rectangle[i][2], 2*rectangle[i][3]);
        }
        
        //3) bfs로 테두리 따라 양쪽으로 가보고 min값 채택
        bfs(2*characterX, 2*characterY, 2*itemX, 2*itemY);
        
        return answer/2;
    }
    
    //x1,y1,x2,y2 => (x1,y1)~(x2,y1), (x1,y2)~(x2,y2), (x1,y1)~(x1,y2), (x2,y1)~(x2,y2)
    //편하게 x2 해준 좌표를 받는다.
    public void fill(int x1, int y1, int x2, int y2){
        for(int i=x1; i<=x2; i++){
            for(int j=y1; j<=y2; j++){
                if(map[i][j]==2) continue;
                map[i][j]=2;
                if(i==x1||i==x2||j==y1||j==y2){
                    map[i][j]=1;
                }
            }
        }
    }//fill
    
    static int[] dx= {-1, 0, 0, 1};
    static int[] dy= {0, -1, 1, 0};
    public void bfs(int startx, int starty, int itemx, int itemy){
        boolean[][] visited= new boolean[101][101];
        Queue<Integer> queue= new LinkedList<>();
        queue.add(startx);
        queue.add(starty);
        
        while(!queue.isEmpty()){
            int x= queue.poll();
            int y= queue.poll();
            
            for(int i=0; i<4; i++){
                int nx= x+dx[i];
                int ny= y+dy[i];
                if(!check(nx, ny)) continue; //범위 아웃
                if(map[nx][ny]!=1||visited[nx][ny]) continue;
                
                //map[nx][ny]==2이고 방문한적없음
                map[nx][ny]=map[x][y]+1;
                if(nx==itemx&&ny==itemy){ //목표점 도달
                    answer= (answer==0)? map[nx][ny]:Math.min(answer,map[nx][ny]);
                    continue;
                }
                visited[nx][ny]= true;
                queue.add(nx);
                queue.add(ny);
            }
        }
    }//bfs
    
    public boolean check(int x, int y){
        if(x<0||y<0||x>100||y>100) return false;
        return true;
    }
}

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

[문제]

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

​

제한사항

k는 1 이상 5,000 이하인 자연수입니다.

dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.

dungeons의 가로(열) 길이는 2 입니다.

dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.

"최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.

"최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.

서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

​

입출력 예

​

입출력 예 설명

현재 피로도는 80입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.

남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.

남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.

남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.

남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

>문제 풀이

어떤 유저가 던전을 탐험합니다.

int k : 유저에게 남은 피로도

int[][] dungeons : 던전을 탐험하는데 필요한 "최소 필요 피로도"와 "소모 피로도"

​

주어지는 던전의 세로행은 1이상 8이하입니다.

전체 경우를 따져봐야 4만 정도 밖에 안되고, 특정한 패턴이 안보이기 때문에 완전탐색으로 풀면 됩니다.

>전체 코드

class Solution {
    static int answer;
    static boolean[] visited;
    
    public int solution(int k, int[][] dungeons) {
        answer= 0;
        visited= new boolean[dungeons.length];
        
        dfs(k, dungeons, 0, 0);
        
        return answer;
    }
    
    public void dfs(int k, int[][] dungeons, int idx, int cnt){
        if(idx==dungeons.length){
            answer= answer>cnt ? answer:cnt;
            return;
        }
        
        for(int i=0; i<dungeons.length; i++){
            if(dungeons[i][0]>k||visited[i]) continue;
            visited[i]= true;
            dfs(k-dungeons[i][1], dungeons, idx+1, cnt+1);
            visited[i]= false;
        }
        dfs(k, dungeons, idx+1, cnt);
    }//dfs
}

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

[문제]

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

​

제한사항

word의 길이는 1 이상 5 이하입니다.

word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

​

입출력 예

​

입출력 예 설명

입출력 예 1

사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. "AAAAE"는 사전에서 6번째 단어입니다.

​

입출력 예 2

"AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다.

​

입출력 예 3

"I"는 1563번째 단어입니다.

​

입출력 예 4

"EIO"는 1189번째 단어입니다.

>문제 풀이

'A', 'E', 'I', 'O', 'U' 모음을 이용해서 만들 수 있는 단어를 사전순으로 정렬한 다음, 입력되는 String word의 순서를 int answer에 담아 return 하면 됩니다.

​

풀이 1)

저는 'A', 'E', 'I', 'O', 'U' 로 만들 수 있는 모든 조합을 list에 넣고 사전순으로 정렬한 다음 indexOf를 이용해서 순서를 찾았습니다.

모든 경우의 수가 얼마 안된다고 생각해서 간단하게 생각하고 풀었는데, 다 풀고나서 보니 통과는 했는데 시간이 오래 걸렸더라고요. 그래서 다시 생각해보니 경우의 수를 잘못 생각했었습니다.

​

풀이 2)

총 5+25+125+625+3125= 3905개 인데,

가장 먼저, 각 알파벳으로 시작할 수 있는 단어는 각각 781개

=> a로 시작하는 단어는 781개

그렇다면 e로 시작하는 단어는 앞에 a로 시작하는 단어 뒤에 나올테니까 적어도 781 다음부터 겠죠?

​

자릿수에 따라 781 / 156 / 31 / 6 / 1 이므로, 주어진 word를 한글자씩 쪼개서 자릿수 별로 answer에 더해주면 됩니다.

그래서 이 원리로 코드를 다시 짜보았습니다.

​

>전체 코드

코드 1)

import java.util.ArrayList;
import java.util.Collections;
class Solution {
    static char[] alphabet= {'A','E','I','O','U'};
    static ArrayList<String> list;
    
    public int solution(String word) {
        list= new ArrayList<>();
        int answer = 0;
        
        combination(0, "");
        Collections.sort(list);
        answer= list.indexOf(word)+1;
        
        return answer;
    }
    
    public void combination(int index, String str){
        if(index>=5) return;
        for(int i=0; i<alphabet.length; i++){
            list.add(str+alphabet[i]);
            combination(index+1, str+alphabet[i]);
        }
    }//comb
}

코드 2)

class Solution {
    
    public int solution(String word) {
        int answer = 0;
        int total= 3905;
        String aeiou="AEIOU";
        
        for(String str: word.split("")){
            //781, 156, 31, 6, 1
            total/= 5;
            answer+= total*aeiou.indexOf(str)+1;
        }
        
        return answer;
    }
}

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