내일은 알고리즘

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXWXMZta-PsDFAST 

간단한 BFS응용 문제입니다. 모든 땅들을 기준으로 물까지의 거리를 생각하면 재귀나 백트래킹으로 계산해야겠지만, 물을 시작점으로 놓고 BFS를 돌리면 땅과의 거리를 쉽게 알 수 있습니다.

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

public class q10966_SWEA_물놀이를가자 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int N, M;

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

		int T = Integer.parseInt(br.readLine());
		int answer;

		for (int tc = 1; tc <= T; tc++) {

			answer = 0;
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			boolean[][] visit = new boolean[N][M];

			Queue<int[]> queue = new LinkedList<>();

			for (int n = 0; n < N; n++) {
				String str = br.readLine();
				for (int m = 0; m < M; m++) {
					if (str.charAt(m) == 'W') {
						visit[n][m] = true;
						queue.add(new int[] { n, m, 0 });
					}
				}
			}

			while (!queue.isEmpty()) {
				int[] now = queue.poll();
				int x = now[0];
				int y = now[1];
				int l = now[2];
				answer += l;

				for (int i = 0; i < 4; i++) {
					int nX = x + delta[i][0];
					int nY = y + delta[i][1];
					
					if(isIn(nX,nY) && !visit[nX][nY]) {
						visit[nX][nY] = true;
						queue.offer(new int[] {nX,nY,l+1});
					}
				}
			}

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}
		System.out.println(sb);
	}

	static boolean isIn(int x, int y) {

		if (0 <= x && x < N && 0 <= y && y < M) {
			return true;
		}

		return false;
	}
}

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://www.acmicpc.net/problem/23559

정렬이 곁들여진 시뮬레이션 문제입니다.

핵심아이디어는 돈이 허락하는 범위 안에서 5000원짜리 메뉴를 먹었을때 얻는 상대적 만족도가 가장 큰 경우를 선택해야 한다는 것입니다.

예를 들어서, 극단적으로 5000원짜리 메뉴의 만족도가 1만이라고 해도 1000원짜리 메뉴의 만족도가 9999라면 상대적 만족도는 1에 불과합니다. 또 역으로 1000원짜리 메뉴가 더 만족스러운 경우도 가능할 수 있습니다.

가장 만족스러운 식사를 하려면 날짜와 만족도에 상관없이 상대적 만족도가 큰 5000원짜리 메뉴부터 골라서 가능한만큼 선택하는것이 해결방법입니다.

따라서 A메뉴와 B메뉴의 만족도의 차이를 기준으로 입력된 데이터를 정렬해주고, 돈이 허락하는 한에서 A메뉴를 선택했습니다. 돈이 가능한지 여부는 (골라야하는 남은 메뉴의 갯수 * 1000) + 4000 보다 현재 자금이 크거나 같으면 가능하다고 조건문을 잡아두었고 메뉴를 하나 고를때 마다 자금에서 5000원씩을 빼 주었습니다.

또, 정렬을 통해서 B메뉴의 만족도가 더 큰 시점이 오면 이후로는 전부 B메뉴를 선택했습니다. B메뉴를 선택하기 시작한 경우는 두가지입니다.

1. 돈이 부족해서 남은 모든 식사는 B메뉴로 골라야 한다. (조건문을 통해 보장됨)

2. 남은 모든 식사들은 B메뉴가 A메뉴보다 맛있다. (정렬을 통해 보장됨)

따라서 이후로는 돈 계산을 하지 않고 B메뉴의 만족도를 계속 더해주었습니다.

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

public class Main {
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long answer = 0;

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int money = Integer.parseInt(st.nextToken());
		int[][] menu = new int[N][2];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			menu[n][0] = Integer.parseInt(st.nextToken());
			menu[n][1] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(menu, (e1, e2) -> {
			return (e2[0] - e2[1]) - (e1[0] - e1[1]);
		});

		int n = 0;

		while (money - ((N - n) * 1000) >= 4000) {
			if(menu[n][1] > menu[n][0]) {
				break;
			}
			answer += menu[n][0];
			money -= 5000;
			n++;
		}
		while (n < N) {
			answer += menu[n][1];
			n++;
		}
		
		System.out.println(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;
    }
}