내일은 알고리즘

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

이분탐색의 기본적인 응용문제입니다.

가능한 정답의 최소시간 = 1과 확실하게 가능한 정답중의 하나 = ((대기자의 수 / 심사관의 수) + 1 ) * 가장 느린 심사속도 두개를 시작점으로 해서 이분탐색을 돌리면 됩니다.

이분 탐색 문제는 언제나 탐색을 멈추는 조건을 정하는게 어려운데, 문제가 보통 정답의 최댓값이나 최솟값을 요구합니다. 우리는 문제에 따라 확실하게 가능한 정답과 확실하게 정답이 아닌 것+1을 줄여가다가 둘이 겹치는 곳에서 문제가 요구하는 답을 찾을 수 있습니다.

public class q43238_Programmers_입국심사 {

	public static void main(String[] args) {

		int n = 6;
		int[] times = { 7, 10 };

		System.out.println(solution(n, times));
	}

	private static long solution(int n, int[] times) {
		long answer = 0;

		long max = 0;

		for (int t = 0; t < times.length; t++) {
			max = Math.max(max, times[t]);
		}

		long left = 1;
		long right = ((n / times.length) + 1) * max;

		while (left < right) {
			long center = (left + right) / 2;
			long count = 0;

			for (int t = 0; t < times.length; t++) {
				count += (center / times[t]);
			}
			
			if(count >= n) {
				right = center;
			}else {
				left = center + 1;
			}

		}

		answer = right;
		return answer;
	}
}

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

Lv.3치고 간단한 조합 응용문제입니다.

전체 사용자 리스트 Y개에서 불량 사용자 리스트에 대하여 대입이 가능한 X개를 뽑아 만들면 됩니다. (yCx)

조합과 다른 점은 아이디를 넣을 수 있는 경우가 제한되어 있어 사용자 Y가 아닌 불량 사용자 X에 대해 찾는다는 점입니다. 

모든 경우(Y x X)에 대하여 가능 여부를 미리 계산한 뒤, 재귀를 통해 불량 사용자 리스트마다 사용자를 대입하고 X개를 뽑았을 때 저장했습니다.

입력 데이터의 최대 사이즈가 8개이기 때문에 중복체크는 bitmask를 이용해 간단히 구현했습니다. 

가능한 리스트 최대 길이가 64이기 때문에 HashMap을 이용해도 구현이 가능할 것 같습니다. 

package programmers;

public class q64064_Programmers_불량사용자 {

	public static void main(String[] args) {
		String[] user_id = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
		String[] banned_id = { "fr*d*", "*rodo", "******", "******" };
		System.out.println(solution(user_id, banned_id));
	}

	private static int solution(String[] user_id, String[] banned_id) {
		int answer = 0;
		boolean[] bitmask = new boolean[1 << user_id.length];

		boolean[][] possible = new boolean[user_id.length][banned_id.length];

		for (int u = 0; u < user_id.length; u++) {
			for (int b = 0; b < banned_id.length; b++) {
				boolean flag = true;

				if (user_id[u].length() != banned_id[b].length()) {
					flag = false;
				} else {
					for (int i = 0; i < user_id[u].length(); i++) {
						if (banned_id[b].charAt(i) == '*')
							continue;
						else if (user_id[u].charAt(i) != banned_id[b].charAt(i)) {
							flag = false;
							break;
						}
					}
				}

				possible[u][b] = flag;
			}
		}

		recur(possible, bitmask, 0, 0);

		for (int i = 0; i < bitmask.length; i++) {
			if (bitmask[i])
				answer++;
		}
		return answer;
	}

	private static void recur(boolean[][] possible, boolean[] bitmask, int mask, int idx) {
		if (idx == possible[0].length) {
			bitmask[mask] = true;
			return;
		}

		for (int u = 0; u < possible.length; u++) {
			if (possible[u][idx] && (mask & (1 << u)) == 0) {
				recur(possible, bitmask, mask | (1 << u), idx + 1);
			}
		}
	}
}

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

https://nodingco.tistory.com/50

접근 방법은 위의 JAVA 풀이에서 확인할 수 있습니다.

Python에서 String을 List로 바꿔주는 메소드는 split()이나 List의 생성자인 list()를 이용하면 됩니다. Python의 경우엔 정수 나눗셈의 몫을 구하고 싶을때 // 연산자를 활용할 수 있습니다.

def solution(s):
    # strArr = s.split('')
    strArr = list(s)

    answer = len(strArr)

    for i in range(1, len(strArr)//2 + 1):
        count = i
        idx = 0
        duple = 0
        for now in range(i, len(strArr) - (len(strArr) % i), i ):
            flag = True
            for j in range(0, i):
                if (strArr[idx + j] != strArr[now + j]):
                    flag = False
                    break
            if (flag):
                if(duple == 0):
                    duple = 2
                else:
                    duple +=1
            else :
                idx = now

                if (duple // 100 != 0):
                    count += 3
                elif (duple // 10 != 0):
                    count += 2
                elif (duple != 0):
                    count+=1
                count += i
                duple = 0
        if(duple // 100 != 0):
            count += 3
        elif (duple // 10 != 0):
            count += 2
        elif (duple != 0):
            count+=1
        
        duple = 0
        answer = min(answer, count + (len(strArr) % i))

    return answer

input = ["aabbaccc","ababcdcdababcdcd","abcabcdede","abcabcabcabcdededededede","xababcdcdababcdcd"]

for i in range(5):
    print(solution(input[i]))

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

https://nodingco.tistory.com/50

접근 방법은 위의 JAVA 풀이에서 확인할 수 있습니다.

JavaScript에서 String을 Array로 바꿔주는 방법은 스프레드연산자, Array.from() 메소드, split()메소드 등 여러가지가 있습니다. 결과는 동일합니다.JavaScript에서 / 연산은 기본적으로 소수점까지 나눠버리기 때문에 몫을 구하고 싶으면 parseInt()로 계산식을 감싸줘야합니다.

function solution(s) {
    const strArr = [...s]
    //const strArr = Array.from(s)
    //const strArr = s.split('')

    let answer = strArr.length;

    //console.log(strArr)

    for (let i = 1; i <= strArr.length / 2; i++) {
        let count = i;
        let idx = 0;
        let now = i;
        let duple = 0;
        for (; now < strArr.length - (strArr.length % i); now += i) {
            let flag = true;
            for (var j = 0; j < i; j++) {
                if (strArr[idx + j] !== strArr[now + j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                duple = (duple === 0) ? 2 : ++duple;
            } else {
                idx = now;

                if (parseInt(duple / 100) != 0) {
                    count += 3;
                } else if (parseInt(duple / 10) !== 0) {
                    count += 2;
                } else if (duple !== 0) {
                    count++;
                } 
                count += i;
                duple = 0;
            }
            //console.log("count", count, " duple",duple)
        }
        if (parseInt(duple / 100) !== 0) {
            count += 3;
        } else if (parseInt(duple / 10) !== 0) {
            count += 2;
        } else if (duple !== 0) {
            count++;
        } 
        duple = 0;
        //console.log(s,i,count," + ", (strArr.length % i))
        answer = Math.min(answer, count + (strArr.length % i));
    }

    return answer;
}


const input = ["aabbaccc","ababcdcdababcdcd","abcabcdede","abcabcabcabcdededededede","xababcdcdababcdcd"]

for(let i = 0; i < 5; i++){
    console.log(solution(input[i]))
}

//console.log(solution(input[0]))

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

지문이 한 번에 이해가 되지 않아 여러 번 읽어본 문자열 압축 문제입니다. 문제를 이해하면 구현하는것은 크게 어렵지 않지만, 고려해야할 상황이 두 개 있습니다.

1. 문자열이 압축되는 경우 중복된 문자열은 생략되고 중복갯수를 더해주어야 합니다.

2. 압축된 문자열의 갯수가 10,100처럼 한 자리가 아닌 여러 자릿수인 경우를 고려해야합니다.

저는 중복이 가능한 문자열의 모든 길이 (1 ~ 문자열의 총 길이/2)를 순회하며 문자열의 중복을 체크하고, 이 체크 갯수를 카운팅 한 뒤 중복이 끝나는 경우 갯수에 따라 길이를 늘려주는 식으로 구현했습니다.

문자열이 아닌 문자열의 길이가 필요한 정답이기에 문자열 대신 숫자만 카운트했습니다.

public class q60057_Programmers_문자열압축 {
	public static void main(String[] args) {
		String[] strArr = { "aabbaccc", "ababcdcdababcdcd", "abcabcdede", "abcabcabcabcdededededede",
				"xababcdcdababcdcd",  "aaaaaaaaaaaabcd", "xxxxxxxxxxyyy"};
		
		for (int i = 0; i < strArr.length; i++) {
			System.out.println(solution(strArr[i]));
		}
//		System.out.println(solution(strArr[5]));
	}

	private static int solution(String s) {
		char[] strArr = s.toCharArray();
		int answer = strArr.length;

		for (int i = 1; i <= strArr.length / 2; i++) {
			int count = i;
			int idx = 0;
			int now = i;
			int duple = 0;
			for (; now < strArr.length - (strArr.length % i); now += i) {
				boolean flag = true;
				for (int j = 0; j < i; j++) {
					if (strArr[idx + j] != strArr[now + j]) {
						flag = false;
						break;
					}
				}
				if (flag) {
					duple = (duple == 0) ? 2 : ++duple;
				} else {
					idx = now;

					if (duple / 100 != 0) {
						count += 3;
					} else if (duple / 10 != 0) {
						count += 2;
					} else if (duple != 0) {
						count++;
					} 
					count += i;
					duple = 0;
				}
			}
			if (duple / 100 != 0) {
				count += 3;
			} else if (duple / 10 != 0) {
				count += 2;
			} else if (duple != 0) {
				count++;
			} 
			duple = 0;
			answer = Math.min(answer, count + (strArr.length % i));
		}

		return answer;
	}
}

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

주어진 조건에 따라 동작하는 프로그램을 구현하는 문제입니다.

채팅방의 입장,퇴장에 따른 출력은 그대로 구현하면 되지만 uid와 달리 nickname은 변할 수 있으므로 uid를 기준으로 최종 상태의 nickname을 찾고 방의 기록을 다시 한 번 순회하면서 return할 String 배열을 만들었습니다.

Case문을 이용하여 입력된 기록을 입장,퇴장,이름변경으로 구분해 필요한 작동이 이루어지게하고

최종상태의 nickname은 HashMap을 활용해서, uid를 Key로 하고 각 uid마다 부여한 index를 Value로 정해주고 이 값을 String을 담은 ArrayList의 index와 맞춰서 갱신하는 식으로 구현했습니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class q42888_Programmers_오픈채팅방 {
	public static void main(String[] args) {
		String[] record = { "Enter uid1234 Muzi", "Enter uid4567 Prodo", "Leave uid1234", "Enter uid1234 Prodo",
				"Change uid4567 Ryan" };
		System.out.println(Arrays.toString(solution(record)));
	}

	private static String[] solution(String[] record) {
        Map<String, Integer> userMap = new HashMap<String, Integer>();
		ArrayList<String> userNick = new ArrayList<String>();
		int[][] log = new int[record.length][2];
		int index = 0;
		int count = 0;

		for (int i = 0; i < record.length; i++) {
			StringTokenizer st = new StringTokenizer(record[i]);
			String act = st.nextToken();
			switch (act) {
			case "Enter":
				String id1 = st.nextToken();
				if (!userMap.containsKey(id1)) {
					userMap.put(id1, index);
					log[i][0] = index;
					userNick.add(st.nextToken());
					index++;
				} else {
					userNick.set(userMap.get(id1), st.nextToken());
					log[i][0] = userMap.get(id1);
				}
				log[i][1] = 1;
				count++;
				break;
			case "Leave":
				String id2 = st.nextToken();
				log[i][0] = userMap.get(id2);
				log[i][1] = 2;
				count++;
				break;
			case "Change":
				String id3 = st.nextToken();
				userNick.set(userMap.get(id3), st.nextToken());
				break;
			default:
				break;
			}
		}

		String[] answer = new String[count];
		index = 0;

		for (int i = 0; i < log.length; i++) {
			if (log[i][1] == 1) {
				answer[index++] = new StringBuilder().append(userNick.get(log[i][0])).append("님이 들어왔습니다.").toString();
			}else if(log[i][1] == 2){
				answer[index++] = new StringBuilder().append(userNick.get(log[i][0])).append("님이 나갔습니다.").toString();
			}
		}

		return answer;
    }
}

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

https://nodingco.tistory.com/45

접근 방법은 위의 JAVA 풀이에서 확인할 수 있습니다.

function solution(lottos, win_nums) {
    let answer = [0,0];
    const grade = [ 6, 6, 5, 4, 3, 2, 1 ];

    let p = 0;
    let c = 0;

    for (let i = 0; i < 6; i++) {
        if (lottos[i] == 0) {
            p++;
        } else {
            for (let j = 0; j < 6; j++) {
                if (lottos[i] == win_nums[j]) {
                    c++;
                    break;
                }
            }
        }
    }
    
    answer[0] = grade[p+c];
    answer[1] = grade[c];
    
    return answer;
}

lottos = [ 44, 1, 0, 0, 31, 25 ]
win_nums = [ 31, 10, 45, 1, 6, 19 ]

console.log(solution(lottos, win_nums))

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

https://nodingco.tistory.com/45

접근 방법은 위의 JAVA 풀이에서 확인할 수 있습니다.

def solution(lottos, win_nums):
    grade = [ 6, 6, 5, 4, 3, 2, 1 ]
    answer = []
    p = 0
    c = 0
    
    for i in range(6):
        if(lottos[i] == 0):
            p+=1
        else:
            for j in range(6):
                if(lottos[i] == win_nums[j]):
                    c+=1
    answer.append(grade[p+c])
    answer.append(grade[c])
    
    return answer

lottos = [ 44, 1, 0, 0, 31, 25 ]
win_nums = [ 31, 10, 45, 1, 6, 19 ]

print(solution(lottos, win_nums))