내일은 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/118669

등산코스 정하기 문제입니다.

몇 달이 지났지만 코딩 테스트 당시에도 굉장히 급박하게 풀었던 기억이 나는데요. 

우선 정답으로 통과한 아이디어는 이렇습니다.

입구 -> 정상 -> 출발한 입구로 돌아오는 경로의 최대 Intensity를 최소로 만드는 경로를 구해야 합니다. 이는 정상 -> 입구로 가는 경로의 최대 Intensity의 최솟값과 같습니다. (같은 길을 두 번 왕복해도 Intensity는 똑같기 때문입니다.)

N이 5만으로 큰 값이기 때문에 2차원 배열로 만들시 25억 사이즈가 됩니다. 배열 대신 인접리스트로 그래프를 구현하고, 모든 정상에 대해 적절하게 가지치기를 하며 BFS를 돌려 각 입구까지 가는 최대 Intensity의 최소값을 구했습니다.

이제 구한 값들을 비교해 정답을 찾아내면 됩니다.

굉장히 브루트포스 스럽게 풀었고 가지치기를 잘 한 덕에 모든 테케에 통과는 했지만 효율성이나 구현이 깔끔하지 못합니다.

어차피 Python언어로도 다시 풀 예정이기 때문에 조금 더 다듬어서 Java로도 나은 솔루션을 다시 올리도록 하겠습니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class q118669_Programmers_등산코스정하기 {
	public static void main(String[] args) {

		int[][] paths = new int[][] { { 1, 2, 3 }, { 2, 3, 5 }, { 2, 4, 2 }, { 2, 5, 4 }, { 3, 4, 4 }, { 4, 5, 3 },
				{ 4, 6, 1 }, { 5, 6, 1 } };
		int[] gates = new int[] { 1, 3 };
		int[] summits = new int[] { 5 };

		System.out.println(Arrays.toString(solution(6, paths, gates, summits)));
	}

	static public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
		int[] answer = { -1, 10_000_001 };

		boolean[] gateCheck = new boolean[n + 1];
		boolean[] summitCheck = new boolean[n + 1];

		for (int i = 0; i < gates.length; i++) {
			gateCheck[gates[i]] = true;
		}
		for (int i = 0; i < summits.length; i++) {
			summitCheck[summits[i]] = true;
		}

		ArrayList<ArrayList> pathList = new ArrayList<ArrayList>();

		for (int i = 0; i <= n; i++) {
			pathList.add(new ArrayList<int[]>());
		}

		for (int i = 0; i < paths.length; i++) {
			int from = paths[i][0];
			int to = paths[i][1];
			int dis = paths[i][2];

			pathList.get(from).add(new int[] { to, dis });
			pathList.get(to).add(new int[] { from, dis });
		}

		Arrays.sort(summits);

		for (int i = 0; i < summits.length; i++) {
			Queue<int[]> queue = new LinkedList<int[]>();
			int[] visited = new int[n + 1];
			Arrays.fill(visited, 10_000_001);
			queue.offer(new int[] { summits[i], 0 });
			visited[summits[i]] = 0;
			int minInten = answer[1];

			while (!queue.isEmpty()) {
				int now = queue.peek()[0];
				int maxInten = queue.poll()[1];

				if (maxInten >= minInten) {
					continue;
				}

				ArrayList<int[]> canMove = pathList.get(now);

				for (int j = 0; j < canMove.size(); j++) {
					int to = canMove.get(j)[0];
					int dis = canMove.get(j)[1];
					int nextInten = Math.max(maxInten, dis);

					if (visited[to] > nextInten) {
						if (gateCheck[to]) {
							visited[to] = nextInten;
							minInten = Math.min(nextInten, minInten);
						} else if (!summitCheck[to]) {
							queue.offer(new int[] { to, nextInten });
							visited[to] = nextInten;
						}
					}
				}
			}

			for (int j = 0; j < gates.length; j++) {
				int goal = gates[j];
				if (visited[goal] < answer[1]) {
					answer[0] = summits[i];
					answer[1] = visited[goal];
				}
			}
		}
		return answer;
	}
}

https://nodingco.tistory.com/135

Python 풀이를 Java로 옮기기만 했습니다. 문제링크와 아이디어, 구현 방법은 위 링크에 설명되어 있습니다.

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

public class q118667_Programmers_두큐합같게만들기 {
	public static void main(String[] args) {

		System.out.println(solution(new int[] { 3, 2, 7, 2 }, new int[] { 4, 6, 5, 1 }));

	}

	static int solution(int[] queue1, int[] queue2) {
		Queue<Long> leftqueue = new LinkedList<Long>();
		Queue<Long> rightqueue = new LinkedList<Long>();
		long leftsum = 0;
		long rightsum = 0;
		int count = 0;
		int limit = 2 * (queue1.length + queue2.length);

		for (int i = 0; i < queue1.length; i++) {
			leftsum += queue1[i];
			leftqueue.add((long) queue1[i]);
		}
		for (int i = 0; i < queue2.length; i++) {
			rightsum += queue2[i];
			rightqueue.add((long) queue2[i]);
		}

		if ((leftsum + rightsum) % 2 == 1) {
			return -1;
		}

		while (count < limit) {
			if (leftsum == rightsum) {
				return count;
			}

			if (leftsum < rightsum) {
				leftsum += rightqueue.peek();
				rightsum -= rightqueue.peek();
				leftqueue.add(rightqueue.poll());
			} else {
				rightsum += leftqueue.peek();
				leftsum -= leftqueue.peek();
				rightqueue.add(leftqueue.poll());
			}
			count += 1;
		}

		return -1;

	}
}

https://school.programmers.co.kr/learn/courses/30/lessons/118667

두 큐의 합을 같게 만드는 문제입니다.

그리디 하게 합이 더 큰 쪽의 큐에서 수를 빼서 작은 쪽으로 넣으면 되는데, 이유는 조금만 생각해봐도 떠올릴 수 있습니다.

(큐의 선입선출 구조를 생각하시면 왜 그리디하게 풀이해서 정답이 나오는지 알 수 있습니다.)

입력된 리스트를 두개의 큐에 (Python의 경우 deque) 담고 그리디 하게 값을 빼고 넣어주며 같은 값이 되게 해 주면 됩니다.

실행시간을 단축시키는 가지치기가 몇개 가능한데, 우선 두 큐의 합을 더한 값이 홀수면 어떤 방법을 써도 같게 만들 수가 없습니다. 3을 정수로 2등분 시키는 게 불가능하듯이요.

2로 나눈 나머지가 0이 아니면 -1을 리턴하시면 됩니다. 그리고 큐의 합을 매번 구하지 않도록 초기 상태에서 합을 미리 구해놓은 다음, 옮기는 수만 합에서 직접 빼고 더해주면 매번 큐의 합을 구하는 것보다 빠르게 동작할 수 있습니다.

from collections import deque


def solution(queue1, queue2):
    left = sum(queue1)
    lqueue = deque(queue1)
    right = sum(queue2)
    rqueue = deque(queue2)
    limit = 2 * (len(queue1) + len(queue2))
    count = 0

    if (left + right) % 2 == 1:
        return -1

    while count < limit:

        if left == right:
            return count

        if left < right:
            gap = rqueue.popleft()
            left += gap
            right -= gap
            lqueue.append(gap)
        else:
            gap = lqueue.popleft()
            right += gap
            left -= gap
            rqueue.append(gap)

        count += 1
    return -1


print(solution([3, 2, 7, 2], [4, 6, 5, 1]))

https://school.programmers.co.kr/learn/courses/30/lessons/118666 

오랜만에 자바도 좀 써보고 싶어서... python과 같은 방식으로 풀이했습니다.

python은 map 즉 dictionary를 빠르게 구현할 수 있어서 사용했지만 Java는 불러야 할 패키지도 많고 입력이 제한적인 만큼 그냥 아스키 코드를 이용한 배열로 처리해주었습니다.

main 함수가 따로 있기도 하지만... python보다 확실히 코드라인이 많아서 시간이 걸리네요.

효율성은 몰라도 코테를 후다닥 해치우기엔 python이 좋긴 한가봅니다.

public class q118666_Programmers_성격유형검사하기 {
	public static void main(String[] args) {
		
		String[] survey = {"AN", "CF", "MJ", "RT", "NA"};
		int[] choices = {5, 3, 2, 7, 5};
		
		Solution sol = new Solution();
		System.out.println(sol.solution(survey, choices));
		
	}
	
	public static class Solution {
	    public String solution(String[] survey, int[] choices) {
	        StringBuilder answer = new StringBuilder();
	        int[] point = new int[26];

			for (int i = 0; i < survey.length; i++) {
				int negative = survey[i].charAt(0) - 'A';
				int positive = survey[i].charAt(1) - 'A';

				if (choices[i] < 4) {
					point[negative] += 4 - choices[i];
				} else {
					point[positive] += choices[i] - 4;
				}
			}
			
		    if(point['R' - 'A'] < point[ 'T' - 'A']) {
		    	answer.append('T');
		    }
		    else {
		    	answer.append('R');
		    }

		    if(point['C' - 'A'] < point[ 'F' - 'A']) {
		    	answer.append('F');
		    }
		    else {
		    	answer.append('C');
		    }
		    
		    if(point['J' - 'A'] < point[ 'M' - 'A']) {
		    	answer.append('M');
		    }
		    else {
		    	answer.append('J');
		    }
		    
		    if(point['A' - 'A'] < point[ 'N' - 'A']) {
		    	answer.append('N');
		    }
		    else {
		    	answer.append('A');
		    }
			
	        return answer.toString();
	    }
	}
}

https://school.programmers.co.kr/learn/courses/30/lessons/118666 

2022 카카오 인턴 채용에 사용된 코딩테스트 문제였습니다.

간단하게 조건에 따라 점수를 더해주고 그 점수로 문자열만 만들어주면 끝나는 구현문제였습니다.

def solution(survey, choices):
    typedict = {'R': 0, 'T': 1, 'C': 2, 'F': 3, 'J': 4, 'M': 5, 'A': 6, 'N': 7}
    point = [0, 0, 0, 0, 0, 0, 0, 0]
    answer = ''

    for i in range(len(survey)):
        positive = typedict[survey[i][1]]
        negative = typedict[survey[i][0]]

        if choices[i] < 4:
            point[negative] += 4 - choices[i]
        elif choices[i] > 4:
            point[positive] += choices[i] - 4

    if point[0] < point[1]:
        answer += 'T'
    else:
        answer += 'R'
    if point[2] < point[3]:
        answer += 'F'
    else:
        answer += 'C'
    if point[4] < point[5]:
        answer += 'M'
    else:
        answer += 'J'
    if point[6] < point[7]:
        answer += 'N'
    else:
        answer += 'A'

    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42586

스택/큐를 어떻게 써야 하지? 문제2 입니다.

먼저 완료되는 작업들을 자료구조에 넣고 꺼내면서 비교하는 유형인 것도 같은데...

그냥 index를 밀어가면서 구현하는 게 더 쉬울 것 같아서 그렇게 풀이했습니다.

아이디어는 간단합니다. 우선순위가 현재 가장 높은 작업을 index로 가리키고, 그 작업의 남은 개발일 수만큼을 진행시켜 버립니다. (작업을 끝낸다는 얘기입니다.)

지금 index로 가리키는 작업이 끝나면 배포가 이루어지므로 현재 상황에서 배포가 가능한 작업들을 카운팅 해주고, 끝나지 않은 가장 우선순위가 높은 작업을 다음 index로 가리켜주면 됩니다.

/// 1차 개선

남은 시간을 매번 빼주면서 갱신하지 않고 현재 day를 갱신해주면서 개발에 필요한 일수가 day보다 작은 만큼 카운팅 해주는 식으로 구현을 바꿨습니다.

이전 코드가 `개발에 필요한 일수가 하나씩 차이나는 오름차순으로 정렬된` 최악의 경우 N번 순회(시간복잡도가 N^2)인데 개선 코드의 경우 무조건 1번 순회(시간복잡도 N)함으로서 작업을 완료합니다. 코드 라인이 줄어서 보기도 더 깔끔하네요.

개선 전 코드

def solution(progresses, speeds):
    answer = []

    for i in range(len(progresses)):
        remain = 100 - progresses[i]
        if remain % speeds[i] == 0:
            progresses[i] = remain // speeds[i]
        else:
            progresses[i] = (remain // speeds[i]) + 1

    index = 0
    while index < len(progresses):
        develop = progresses[index]
        count = 0
        flag = True

        for i in range(index, len(progresses)):
            progresses[i] -= develop
            if progresses[i] <= 0 and flag:
                count += 1
                index = i + 1
            else:
                flag = False

        answer.append(count)

    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/12899

될 것 같은데, 될 것 같은데 안 되는 이상한 문제입니다.

처음엔 간단히 0,1,2가 1,2,4로 치환된 삼진법 문제라고 생각했습니다.

그런데 생각해 보면 삼진법에서 0,1,2는 따지면 00, 01, 02라고 볼 수 있습니다.

이 문제에선 0,1,2가 직접적으로 대응되지 않을뿐더러 자릿수도 다릅니다.

풀이의 도움을 받아...  예외적으로 동작하는 3의 배수들을 봅시다.

3, 6, 9는 3진법에서 각각 10, 20, 100으로 나타납니다. 즉 3진법 변환에서 나눗셈의 나머지가 본래 순서대로는 [0,1] [0,2] [0,0,1]이라는 얘기인데, 문제의 변환을 보면 [4] [4, 1] [4, 2]로 나타납니다.

나머지가 0인 경우 0이 아니라 4가 들어가고 다음으로 넘겨주는 몫이 1 줄어든다는 사실을 알 수 있습니다.

(역순으로 수가 구해지기 때문에 윗 자릿수를 하나 줄이고 0이 아닌 3을 적는다고 생각하시면 됩니다.)

이 사실을 유념해서 3진법 변환을 진행해주면 됩니다.

124 나라가 아니라 123 나라였으면 좀 더 빨리 이해가 가능했을것 같은데 여러모로 잘 꼰 문제인 것 같습니다.

def solution(n):
    answer = []

    while n > 0:
        if n % 3 == 0:
            answer.append(4)
            n = (n // 3) - 1
        else:
            answer.append(n % 3)
            n = n // 3
    
    result = ""
    for i in range(len(answer)):
        addnum = answer[len(answer) - 1 - i]
        result += str(addnum)
    
    return result

https://school.programmers.co.kr/learn/courses/30/lessons/12906

스택/큐의 연습 문제인데 왜 스택/큐 인지 모르겠습니다.

쉽다는게 아니라 스택이랑 큐를 어디에 써서 구현할지 감이 안잡혀요... 

일단 입력을 n번 순회하면서 마지막에 넣은 값을 기억해주고, 같다면 패스 다르면 값을 넣어주고 갱신 하는 식으로 구현했습니다.

def solution(arr):
    answer = []
    before = -1
    
    for i in range(len(arr)):
        if arr[i] != before:
            before = arr[i]
            answer.append(before)
    
    return answer