평범한 배낭이지만 절대 평범하지가 않다. 알고 보니 배낭 문제 (knapssack problem)로 Dynamic Programming의 대표적인 문제라고 한다. Knapsack Algorithm이라고도 불리는 배낭 문제는 두 가지 문제로 분류된다. 짐을 쪼갤 수 있는 경우와, 짐을 쪼갤 수 없는 경우이다. 전자는 Fraction Knapsack Problem이라고 하고, Greedy를 사용한다.

🔗 문제 링크

🔎 문제 풀이

평범한 배낭이지만 절대 평범하지가 않다. 

알고 보니 배낭 문제 (knapsack problem)로 Dynamic Programming의 대표적인 문제라고 한다.

Knapsack Algorithm이라고도 불리는 배낭 문제는 두 가지 문제로 분류된다.

짐을 쪼갤 수 있는 경우와, 짐을 쪼갤 수 없는 경우이다.

전자는 Fraction Knapsack Problem이라고 하고,  Greedy를 사용한다.

후자는 0/1 Knapsack Problem이라고 하고, 보통 DP를 사용한다.

나무위키와 블로그를 참고해서 배낭 문제에 대해 이해했다.

이 문제는 짐을 쪼갤 수 없는 경우이므로 DP로 푼다.

아래 블로그에 나오는 테이블 그림을 참고하면 이해하는데 도움이 된다.

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[][] dp = new int[N + 1][K + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            int W = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());

            for (int j = 1; j <= K; j++) {
                if (j < W) {
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }

                dp[i][j] = Math.max(V + dp[i - 1][j - W], dp[i - 1][j]);
            }
        }

        System.out.println(dp[N][K]);
    }
}

🔗 문제 링크

N-Queen

🔎 문제 풀이

백준 'N과 M' 4문제를 통해 백트래킹 원리를 조금 이해하게 되었고 ,, 그 유명한 (?) N-Queen 문제를 도전했다.

퀸은 가로, 세로, 대각선으로 이동할 수 있다.

즉, 퀸을 서로 공격할 수 없게 놓기 위해서는 퀸 위치의 가로, 세로, 대각선에 또 다른 퀸이 존재하면 안 된다는 것이다.

퀸 위치 좌표는 배열을 통해 저장한다.

처음에는 x, y 좌표가 떠올라 2차원 배열로 놓았는데

풀다가 어려워서 찾아보니 1차원 배열로 해결하더라 ,,!

나 빼고 다 천재가 틀림이 없다 ,,

배열의 index를 열로 두고, 해당 index의 값을 행으로 두면 되는 것이다 ,,,! 

그럼 같은 행에 위치하거나 대각선에 위치하는지에 대해서만 검사하면 된다.

퀸을 놓을 수 있다면 depth에 1을 증가시켜 재귀 함수를 호출시키고,

depth == N이라면 문제 조건에 맞는 경우의 수를 찾은 것이므로 count를 1 증가한다.

그리고 count를 출력하면 된다.

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
        
public class Main {
	static int N;
	static int[] queenPlace;
	static int count = 0;
    
	public static void main(String[] args) throws IOException {
    
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	N = Integer.parseInt(br.readLine());
    	queenPlace = new int[N];
    	findNQueen(0);	
    	System.out.println(count);
    }
    
	
    public static void findNQueen(int depth) {
    	if (depth == N) {
    		count++;
    		return;
    	}
    	
    	for (int i = 0; i < N; i++) {
    		queenPlace[depth] = i;
    		
    		if (getPossibillity(depth)) {
        		findNQueen(depth+1);
        	}
    	}
   
    }
    
    public static boolean getPossibillity(int column) {
    	for (int i = 0; i < column; i++) {
    		if (queenPlace[column] == queenPlace[i])
    			return false;
    		
    		if (Math.abs(column - i) == Math.abs(queenPlace[column] - queenPlace[i]))
    			return false;
    	}
    	
    	return true;
    }
}

Reference

🔗 문제 링크

하노이 탑 이동순서

🔎 문제 풀이

어릴 때 엄청 좋아했던 추억의 하노이 탑 ! ! 

하노이 탑은 재귀를 활용하여 풀 수 있는 유명한 예제 중 하나라고 한다.

출력해야 하는 값은 두 가지이다.

첫째 줄에 옮긴 횟수 K, 두 번째 줄부터 수행 과정을 출력하면 된다.

하노이 원반 수가 홀수이면 제일 작은 맨 위 원반을 맨 오른쪽 장대에 옮기면서 시작하고, 짝수이면 중간 장대에 옮기면서 시작한 기억이 있어서 그런 식으로 접근했는데, 전혀 관계없는 무의미한 접근이었다 ,,^^

위키백과에 보면 하노이 탑 알고리즘이 설명되어있다.

원판이 n개 일 때, 옮긴 횟수는 " 2의 n제곱 - 1 " 이다.

이러한 수를 메르센 수(Mersenne number)라고 부른다고도 한다.

하노이 탑을 옮기는 수행 과정은 재귀 호출을 통해 구현할 수 있다.

출력은 StringBuilder를 활용하였다.

Key Point

🔑재귀 함수를 활용한다.

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static StringBuilder result = new StringBuilder(); 
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		// 옮긴 횟수
		
		int movingCount = (int)Math.pow(2, N) - 1;
		result.append(movingCount + "\n");
		
		// 하노이 원반을 옮기는 수행 과정
		
		moveHanoiDisk(N, 1, 2, 3);
		
		System.out.print(result);
		
	}
	
	static void moveHanoiDisk(int N, int startingPoint, int mid, int destination) {
		
		if (N == 1) {
			result.append(startingPoint + " " + destination + "\n");
			return;
		}
		
		moveHanoiDisk(N-1, startingPoint, destination, mid);
		result.append(startingPoint + " " + destination + "\n");
		moveHanoiDisk(N-1, mid, startingPoint, destination);
		
	}
}

+

뭔가 100% 이해하지 못해서 찜찜했는데, 자기 전에 우연히 이 영상을 발견했다 !

설명을 너무 잘 해주신다 ! 

최고다 !

🔗 문제 링크

별 찍기 - 10

🔎 문제 풀이

재귀 문제이다. 처음에 예제가 한 눈에 잘 들어오지 않아서 캡처해서 그림판으로 그려보니 별을 찍는 방법은 쉽게 이해가 갔다. 다음은 크기 27의 패턴이다.

크기 3의 패턴(= 분홍색 정사각형)은 가운데를 제외한 모든 칸에 별이 하나씩 있다.

크기 9의 패턴(= 보라색 정사각형)은 크기 3의 패턴이 가운데를 제외한 모든 칸에 있다.

크기 27의 패턴(= 노란색 정사각형)은 크기 9의 패턴이 가운데를 제외한 모든 칸에 있다.

2차원 배열을 활용하고, boolean 변수를 이용해 공백인지 아닌지 구분하여 별 또는 공백을 자기 자리에 넣어주면 되겠다는 생각을 했다. 뭔가 N을 N/3으로 더 이상 쪼갤 수 없을 때까지 재귀 함수를 계속 호출해서 별을 찍는 느낌은 알겠는데 막상 코드를 짜려니 막막했다 ,, 별을 찍는 재귀 함수의 파라미터를 입력값 N만 두고 생각했는데, 풀이를 찾아보니 2차원 배열의 인덱스이자 별의 위치인 x, y와 공백인지 구분하는 boolean 변수도 파라미터로 둔 것을 보고 힌트를 얻었다.

메인 함수에서 별을 찍을 때에는 StringBuilder를 활용해 한 번에 출력했다. 

찾아보니 StringBuilder 보다는 BufferedWriter가 출력이 많은 경우 성능이 더 좋은 편이라고 한다.

Key Point

🔑 재귀 함수를 활용한다.

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static char[][] stars;
	static int N;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		stars = new char[N][N];
		
		drawStar(0, 0, N, false);
		
		StringBuilder result = new StringBuilder();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				result.append(stars[i][j]);
			}
			result.append('\n');
		}
		
		System.out.println(result);
		
	}
	
	public static void drawStar(int x, int y, int N, boolean blank) {
		
		if (blank) { // 공백인 경우
			for (int i = x; i < x+N; i++) {
				for (int j = y; j < y+N; j++) {
					stars[i][j] = ' ';
				}
			}
			return;
		}
		
		if (N == 1) { // 더 이상 쪼갤 수 없는 경우
			stars[x][y] = '*';
			return;
		}
		
		int size = N / 3;
		int count = 0;
		
		for (int i = x; i < x+N; i += size) {
			for (int j = y; j < y+N; j += size) {
				count++;
				if (count == 5) drawStar(i, j, size, true);
				else drawStar(i, j, size, false);
			}
		}
	
	}
}

🔗 문제 링크

짝지어 제거하기

🔎 문제 풀이

Stack 문제이다! 대표적인 Stack 유형 문제인 괄호 문제와 비슷하게 풀어주면 된다. 반복문을 활용해 문자열 s를 한 문자씩 char 변수로 떼어서 차례대로 검사한다. 해당 char 변수가 Stack에 들어있는 맨 위의 값과  동일하다면 stack.pop()을 하여 같은 알파벳이 2개 붙어 있는 짝을 제거하는 역할을 해주고, 그렇지 않다면 stack.push()를 한다. 만약 최종적으로 Stack이 비었다면 짝지어 제거하기를 성공적으로 수행한 것이므로 1을 리턴하고, 그렇지 않다면 0을 리턴해준다.

Key Point

🔑 Stack을 활용한다.

Java 코드

import java.util.*;

class Solution
{
    public int solution(String s)
    {    
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if(!stack.isEmpty() && stack.peek() == c) stack.pop();
            else stack.push(c);
        }

        return stack.isEmpty() ? 1 : 0;
    }
}

+

근데 이거 괄호가 왜 독특한지는 모르겠다 ,,?

뭔가 ,,, 괄호에게 한 칸 전부를 수여해주는 ,, 2017 팁스타운만의 차별화 방식인가 ,,,?

🔗 문제 링크

길 찾기 게임

🔎 문제 풀이

트리를 순회하면 된다. 이 문제는 좌표 값으로 주어지는 노드들을 트리로 구성해야한다는 점이 핵심이다.

이런 유형의 문제는 처음이라 ,, 트리에 대해 간단히 정리하면서 이해했다.

트리를 순회하는 알고리즘은 코드만 처음 딱 보았을 때는 어렵다고 느꼈는데,

트리에 대해 이해하고 다시 보니 직관적이라서 오히려 이해하기가 쉬웠다.

그리고 이 문제에서 트리를 만드는 과정은 다음과 같다.

1) x 좌표, y 좌표, 노드 번호(=value), 왼쪽 자식,노드 오른쪽 자식 노드를 저장할 수 있도록 Node 클래스를 만든다.

2) 조건에 맞는 트리 구조로 만들기 위해 Comparator 인터페이스를 활용해 정렬한다. 

    • y 값은 더 큰 값이 먼저 오도록, y 값이 같다면 x 값이 더 작은 값이 먼저 오도록 한다.

3)  정렬 후 0번 인덱스 값을 root로 지정하고, root를 기준으로 노드를 insert 한다.

트리를 만들었으면 재귀를 활용해 전위 순회와 후위 순회를 해주면 된다.

특히, 트리를 만들기 위해 Node 클래스를 객체 배열로 선언하는 부분에서 객체 배열에 대해 새롭게 배웠다.

마찬가지로 Node 클래스를 변수로 선언하는 것도 새로웠다. 이런 경우는 참조변수로만 쓸 수가 있다고 한다.

Kakao Tech 블로그 문제 해설을 보니 이 문제 정답률이 7.4% 이다 ,, 

원리는 이해했지만, 막상 문제를 마주치면 당황할 것 같다.

트리 순회 알고리즘도 백준에서 몇 개 더 풀어봐야겠다 !

해당 문제 풀이는 객체 배열을 만드는 방법을 사용했지만 !

Kakao Tech에서는 Queue를 만들어 x축 기준으로 오름차순 정렬된 노드들을 y축 값이 같은 노드끼리 각 Queue에 넣어두고, Queue의 front를 확인하는 방법을 알려준다.

Key Point

🔑 좌표 값으로 주어지는 노드들을 트리로 구성한다.

🔑 트리 순회 알고리즘을 활용한다.

🔑 전위 순회는 노드 - 왼쪽 자식 - 오른쪽 자식 순이고, 후위 순회는 왼쪽 자식 - 오른쪽 자식 - 노드 순이다.

Java 코드

import java.util.*;

class Solution {
    
    int[][] answer;
    int idx;
    
    public int[][] solution(int[][] nodeinfo) {
       
        // 노드를 입력받는다.
        
        Node[] node = new Node[nodeinfo.length];
        for (int i=0; i<nodeinfo.length; i++) {
            node[i] = new Node(nodeinfo[i][0], nodeinfo[i][1], i+1, null, null);     
        }
        
        // y값이 큰 순서대로, y값이 같다면 x값이 작은 순서대로 정렬한다.
        
        Arrays.sort(node, new Comparator<Node>() {
            @Override
            public int compare(Node n1, Node n2) {
                if (n1.y == n2.y) return n1.x - n2.x;
                else return n2.y - n1.y;
            }
        });
        
        // 트리를 만든다.
        
        Node root = node[0];
        
        for (int i=1; i<node.length; i++) {
            insertNode(root, node[i]);
        }
        
        answer = new int[2][nodeinfo.length];
        idx = 0;
        preorder(root); // 전위 순회
        idx = 0;
        postorder(root); // 후위 순회
        
        return answer;
    }
    
    public void insertNode(Node parent, Node child) {
        if (parent.x > child.x) {
            if (parent.left == null) parent.left = child;
            else insertNode(parent.left, child);
        }
        else {
            if (parent.right == null) parent.right = child;
            else insertNode(parent.right, child);
        }
    }
    
    public void preorder(Node root) {
        if (root != null) {
            answer[0][idx++] = root.value;
            preorder(root.left);
            preorder(root.right);
        }
    }
    
    public void postorder(Node root) {
        if (root != null) {
            postorder(root.left);
            postorder(root.right);
            answer[1][idx++] = root.value;
        }
    }
    
    public class Node {
        int x;
        int y;
        int value;
        Node left;
        Node right;
        
        public Node(int x, int y, int value, Node left, Node right) {
            this.x = x;
            this.y = y;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}

Reference

🔗 문제 링크

파일명 정렬

🔎 문제 풀이

Comparator 혹은 Comparable 인터페이스를 활용해 조건에 맞게 정렬을 해주면 된다.

한 블로거의 코드가 이해가 잘 되어서, 해당 코드로 풀며 이해를 했다.

Key Point

🔑 Comparator 혹은 Comparable 인터페이스를 활용한다.

Java 코드

import java.util.*;

class Solution {
    public String[] solution(String[] files) {
        
        // Comparator 인터페이스를 활용해 조건에 맞게 정렬한다.
        
        Arrays.sort(files, new Comparator<String>() {
        @Override
        public int compare(String s1, String s2) {
            String[] file1 = fileInfo(s1);
            String[] file2 = fileInfo(s2);
            
            int headValue = file1[0].compareTo(file2[0]);
            
            if (headValue == 0) {
                int num1 = Integer.parseInt(file1[1]);
                int num2 = Integer.parseInt(file2[1]);
                
                return num1 - num2;
            }
            else {
                return headValue;
            }
        }
        
        // head, number, tail 정보를 담은 배열을 리턴하는 함수이다.
            
        private String[] fileInfo(String s) {
            String head = "";
            String number = "";
            String tail = "";
            
            int idx = 0;
            for ( ; idx<s.length(); idx++) {
                char ch = s.charAt(idx);
                if (ch>='0' && ch<='9') break;
                head += ch;
            }
            
            for ( ; idx<s.length(); idx++) {
                char ch = s.charAt(idx);
                if (!(ch>='0' && ch<='9')) break;
                number += ch;
            }
            
            for ( ; idx<s.length(); idx++) {
                char ch = s.charAt(idx);
                tail += ch;
            }
            
            String[] file = {head.toLowerCase(), number, tail};
            return file;
            }
        });
        
        return files;
    }
}

💡 Comparable과 Comparator 

객체를 정렬해주는 인터페이스이다.

즉, Comparable 혹은 Comparator를 사용하고자 한다면 인터페이스 내에 선언된 메소드를 반드시 구현해야 한다.

Comparable 인터페이스에는 compareTo (T o) 메소드 하나가 선언되어있다.

즉, Comparable을 사용하고자 한다면 compareTo 메소드를 재정의 (Override/구현) 해주어야 한다.

✔ 자기 자신과 매개변수 객체를 비교한다.

✔ lang 패키지에 있기 때문에 import 해줄 필요가 없다.

Comparator 인터페이스에는 선언된 메소드가 많지만, 실질적으로 구현해야 하는 메소드는 compare(T o1, T o2) 하나이다.

✔ 두 매개변수 객체를 비교한다.

✔ util 패키지에 있다.

💡 정렬 알고리즘

이번 문제는 코딩의 기초 문제인 정렬 문제이다.

정렬 기준에 따라 차이가 없다면 원래 입력에서 주어진 순서를 유지하는 안정 정렬 (Stable Sort)을 사용한다.

이번 문제를  풀면서 아직까지 정렬 알고리즘에 대해 완벽히 숙지하고 있지 못하다는 것을 깨달았다.

정렬 알고리즘에 대해 조만간 공부해야겠다 !

+ 다른 사람의 풀이

프로그래머스에서 다른 사람의 풀이를 보니, 정규식을 활용해서 푸는 방법도 있었다.

Java에서는 정규식을 활용해 문자열 검증 및 탐색을 돕는 Pattern, Matcher 클래스를 제공해준다.

새롭게 알게 된 것은 Matcher의 find()와 group() 메서드이다.

 boolean find()

패턴이 일치하는 다음 문자열을 찾고, 다음 문자열이 있으면 true를 반환한다.

String group()

매치와 일치하는 문자열을 반환한다.

groupt(int i)는 매칭 되는 문자열 중 i번째 그룹의 문자열을 반환한다.

0은 그룹의 전체 패턴을 의미한다.

- group(0) = group()

아래는 정규식을 활용한 풀이 중 깔끔하다고 생각하는 Java 코드이다.

import java.util.*;
import java.util.regex.*;

class Solution {
    public String[] solution(String[] files) {
        Pattern p = Pattern.compile("([a-z\\s.-]+)([0-9]{1,5})");

        Arrays.sort(files, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                Matcher m1 = p.matcher(s1.toLowerCase());
                Matcher m2 = p.matcher(s2.toLowerCase());
                m1.find();
                m2.find();

                if(!m1.group(1).equals(m2.group(1))) {
                    return m1.group(1).compareTo(m2.group(1));
                } else {
                    return Integer.parseInt(m1.group(2)) - Integer.parseInt(m2.group(2));
                }
            }
        });

        return files;
    }
}

+ 비슷한 유형의 더 쉬운 문제

🔗 문제 링크 : 문자열 내 마음대로 정렬하기

compareTo 메서드는 알고리즘을  풀면서 몇 번 사용한 적이 있지만 Comparable과 Comparator 인터페이스는 처음 접해보았다 ,, 아니면 까먹었거나 ,,^^  인터페이스 사용법을 검색하다가 우연히 "문자열 내 마음대로 정렬하기" 문제를 만났다. 문제가 훨씬 직관적이어서 이 문제를 먼저 풀고 나니 Java에서의 객체 정렬을 이해하는데 도움이 되었다.

Java 코드

import java.util.*;

class Solution {
    public String[] solution(String[] strings, int n) {
        
        Arrays.sort(strings, new Comparator<String>() {
            
            // 앞의 값(o1)과 뒤의 값(o2)을 비교해서 리턴값을 양수로 주면 값을 바꾼다. (오름차순)
            // 앞의 값(o1)과 뒤의 값(o2)을 비교해서 리턴값을 음수로 주면 값을 바꾸지 않는다. (내림차순)          
            @Override
            public int compare(String o1, String o2) {
                if (o1.charAt(n) > o2.charAt(n)) {
                    return 1;
                }
                else if (o1.charAt(n) == o2.charAt(n)) {
                    
                    // compareTo() 함수는 두 개의 값을 비교하여 int 값으로 반환해준다. 
                    
                    return o1.compareTo(o2); 
                }
                else {
                    return -1;
                }             
            }
            
        });
        return strings;
    }
}

Reference

🔗 문제 링크

N진수 게임

🔎 문제 풀이

진법 변환만 하면 되는 문제이다!

카카오 코테는 같은 Lv.2여도 느껴지는 난이도가 왜 천지차이일까 ,,?

직접 코드를 구현하여 진법 변환을 하거나,

진법 변경을 알아서 해주는 Integer.toString(숫자, 진법)을 사용하면 된다.

간단하게 후자의 방법을 택했다.

Key Point

🔑 숫자를 특정 진법으로 변환한다.

Java 코드

import java.util.*;

class Solution {
    public String solution(int n, int t, int m, int p) {
        String answer = "";
        StringBuilder sb = new StringBuilder();
        int num = 0;
        
        // m명이 t번 말하는 경우를 StringBuilder로 저장한다.
        
        while(sb.length() < m*t) {
            sb.append(Integer.toString(num++, n));
        }
        
        // 튜브가 말해야 하는 숫자 부분만 answer에 더해준다.
        
        for (int i=p-1; i<m*t; i+=m) {
            answer += sb.charAt(i);
        }
        
        return answer.toUpperCase();
    }
}

Kakao Tech 블로그에서 문제 해설을 보니 이 문제는 챔퍼나운 수라는 수학 상수를 이용한 문제라고 한다.

챔퍼나운 상수(Champernowne constant) 란 ?

초월수이자 실수인 수학 상수 중 하나로 소수점 이하 자릿수에 특이한 점이 있는 수이다.

십진법에서 챔퍼나운 수는 소수 전개가 1부터 시작하여 연속적인 정수를 쭉 이은  수열인 실수이다.

이 급수를 10과 9 대신에 b와 b-1로 각각 바꿔서 임의의 b진법으로 일반화할 수 있다고 한다.

Reference

🔗 문제 링크

실패율

🔎 문제 풀이

쉬워보이면서도 은근히 푸는데 오래 걸렸다 ,,

HashMap을 사용해 key값은 스테이지 번호, value값은 실패율을 저장한 후 정렬하면 되겠다는 생각을 했다.

HashMap 정렬에 대해 구글링 해보니 map의 keySet을 이용해 정렬이 가능한 것을 알게 되었다.

각 스테이지마다 실패율을 구하기 위해서 주어진 배열 stages를 참고하여 배열 두 개를 만들었다. 

1) 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수를 담은 배열

2) 스테이지에 도달한 플레이어 수를 담은 배열

배열의 인덱스가 스테이지 번호라고 생각하고, 각 스테이지 번호와 일치하는 인덱스에 수를 저장한다.

두 배열의 같은 인덱스에 들어있는 원소 값을 나누어 실패율을 계산하고, HashMap에 저장하면 된다.

만약 스테이지에 도달한 유저가 없는 경우, 실패율을 0으로 정의하는 예외 처리도 해주어야 한다.

Key Point

🔑 배열을 활용해 실패율을 구한다.

🔑 HashMap을 사용해 스테이지 번호(key)와 실패율(value)을 저장한다.

🔑 스테이지에 도달한 유저가 없는 경우(실패율 = 0)를 고려한다.

🔑 실패율(value)을 기준으로 내림차순으로 정렬한 후, 스테이지 번호(key)를 배열 answer에 넣어준다.

Java 코드

import java.util.*;

class Solution {
    public int[] solution(int N, int[] stages) {
        int[] answer = new int[N];
        
        // 스테이지에 도달했으나 아직 클리어하지 못한 플레이어 수 정보를 담은 배열
        
        int[] stageCount = new int[N+2];
        
        for (int stage : stages) {
            stageCount[stage]++;
        }
        
        // 스테이지에 도달한 플레이어 수 정보를 담은 배열
        
        int[] stagePassCount = new int[N+1];
        
        stagePassCount[N] = stageCount[N] + stageCount[N+1];
        
        for (int i=N-1; i>=1; i--) {
            stagePassCount[i] = stageCount[i] + stagePassCount[i+1];
        }
        
        // HashMap을 사용해 실패율 저장 (Key: 스테이지 번호, value: 실패율)
        
        HashMap<Integer,Double> map = new HashMap<>();
        
        for (int i=1; i<=N; i++) {
            
            if (stagePassCount[i] == 0) {
                map.put(i, (double)0);
            }
            else {
                map.put(i, (double)stageCount[i]/stagePassCount[i]);
            }
        }
        
        // 각 스테이지 번호(key)를 실패율(value)의 내림차순으로 정렬
        
        List<Integer> keySet = new ArrayList<>(map.keySet());
        keySet.sort((o1, o2) -> map.get(o2).compareTo(map.get(o1)));
        
        int idx = 0;
        for (int stage : keySet) {
            answer[idx++] = stage;
        }
        
        return answer;
    }
}

🔗 문제 링크

[3차] 방금그곡

🔎 문제 풀이

부분 문자열 비교를 묻는 문제이다.

재생 시간이 음악 길이보다 긴 경우는 음악이 끊김 없이 처음부터 반복해서 재생되고,

재생 시간이 음악 길이보다 짧은 경우는 음악이 처음부터 재생 시간만큼만 재생된다.

따라서 재생 시간과 음악 길이를 구해 아래 두 가지 조건으로 나누어 실제 재생되는 악보를 만들면 된다.

1) 재생 시간 > 음악 길이

실제 재생되는 악보는 "재생 시간 / 음악 길이" 만큼 악보를 반복한 후, 나머지 "재생 시간 % 음악 길이 " 만큼 뒤에 덧붙여주면 된다.

2) 재생 시간 <= 음악 길이

실제 재생되는 악보는 재생 시간만큼만 악보를 잘라주면 된다.

여기까지 풀다가 #이 붙은 음을 어떻게 처리할지 고민하는 부분에서 막혔다.

C#은  두 글자이지만 사실 하나의 음이기 때문이다.

Kakao Tech 블로그 문제 해설에서는 문자열 비교에서 이런 문제를 처리할 때 두 가지 방법을 이용하라고 알려준다.

1) 토큰화(Tokenizing)를 통해 ["A", "B" "C#"] 식의 배열로 변환한 후 비교한다.
2) 두 글자로 된 "C#", "D#", "F#" 등을 악보에서 사용되지 않는 문자 "c", "d", "e" 등으로 치환(Substitution)한 후 문자열 비교 함수를 이용한다.

개인적으로는 치환하는 것이 더 편할 것 같아서 #이 붙은 음을 치환하는 함수를 만들었다.

그리고 마지막으로 실제 재생되는 악보 중 네오가 기억하는 멜로디인 문자열 m을 포함하는 악보의 음악 제목을 찾으면 된다.

여기서 놓치면 안되는 점이 있다. 만약 조건이 일치하는 음악이 여러 개인 경우는 제일 재생 시간이 긴 음악을 찾아야 하기 때문에 변수 maxPlayingTime을 하나 만들어서 조건이 일치하는 음악 중 제일 긴 재생 시간을 업데이트해주어야 한다. 

이렇게 풀고 채점하니 테스트 케이스 몇 개가 실패라고 떠서 헤맸는데, 조건이 일치하는 음악이 없는 경우를 고려하지 못한 것이 원인이었다.

조건이 일치하는 음악이 없는 경우에는 "(None)"을 리턴한다는 점을 포함하면 테스트 케이스가 전부 통과된다.

Key Point

🔑 재생 시간 > 음악 길이인 경우, 재생 시간 <= 음악 길이인 경우를 나누어 처리한다.

🔑 #이 붙은 음을 치환하는 함수를 만든다.

🔑 조건이 일치하는 음악이 여러 개인 경우와 없는 경우를 고려한다.

Java 코드

import java.util.*;

class Solution {
    public String solution(String m, String[] musicinfos) {
        int maxPlayingTime = 0;
        String answer = "";
        
        // 네오가 기억한 멜로디를 치환한다.
        
        m = changeCode(m);
        
        for (String musicInfo : musicinfos) { 
        	String[] info = musicInfo.split(",");

        	// 재생된 시간 구하기
            
        	int playingTime = (Integer.parseInt(info[1].substring(0, 2)) 
            				- Integer.parseInt(info[0].substring(0, 2)))*60  
        				+ Integer.parseInt(info[1].substring(3)) 
                    			- Integer.parseInt(info[0].substring(3));
        	
        	// 악보 정보(=info[3]) #이 붙은 음 치환하기
        	
        	info[3] = changeCode(info[3]);
        	
        	// 음악 길이 구하기
        	
        	int musicLength = info[3].length();
        	
        	// 실제 재생된 음악 악보 구하기
        	
        	String musicCode = "";
        	
        	// 재생 시간 > 음악 길이 : 처음부터 음악 반복 재생
        	
        	if (playingTime > musicLength) {
        		for (int j=0; j<playingTime/musicLength; j++) {musicCode += info[3];}
        		musicCode += info[3].substring(0, playingTime%musicLength);
        	}
        	
        	// 재생 시간 <= 음악 길이 : 처음부터 재생된 시간만큼 재생
        	
        	else {musicCode += info[3].substring(0, playingTime);}
        	
            	// answer = 네오가 기억하는 멜로디를 포함하면서 
            	// 제일 재생 시간이 긴 음악 제목(=info[2])
            
        	if (musicCode.contains(m) && playingTime > maxPlayingTime) {
        		answer = info[2];
        		maxPlayingTime = playingTime;
        	}
        	
        }	
        
        // 조건이 일치하는 음악이 없는 경우 answer = (None)
        
        if (maxPlayingTime == 0) { answer = "(None)"; }
        
        return answer;
    }
    
    // #이 붙은 음을 치환하는 함수
    
    public static String changeCode(String code) {
        code = code.replaceAll("C#", "c");
        code = code.replaceAll("D#", "d");
        code = code.replaceAll("F#", "f");
        code = code.replaceAll("G#", "g");
        code = code.replaceAll("A#", "a");
        
        return code;
    }
}