내일은 알고리즘

https://www.acmicpc.net/problem/1303

어... 정신을 차리니 마지막 PS로부터 3주 가량이 지났습니다.

추석연휴가 껴 있기도 했고, 개인적인 일로 지방을 오가느라 시간이 없기도 했고.... 무엇보다 근무도 바빴고... 여러 사정이 있었지만 결국엔 제가 게을렀던 거겠죠.

Java를 하도 안쓰다 보니 (현재 하고 있는 업무에서 90% 이상 Python을 씁니다.) 다 까먹어가고 있는 느낌이라 급하게 쉬운 문제를 하나 풀어봤습니다.

정말 기본적인 bfs 문제라 딱히 설명할건 없네요. visit 체크만 잘해주면 풀리는 문제였습니다. 주의 할 점은 N과 M이 거꾸로 주어진다는 정도입니다. 예제에서 티가 안나는 부분이라(예제 입력에선 N == M입니다.) 첫 제출에서 index 범위가 넘어가는 런타임 에러를 당했네요. 

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 q1303_BOJ_전쟁전투 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

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

		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int B = 0;
		int W = 0;

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

		for (int n = 0; n < N; n++) {
			char[] line = br.readLine().toCharArray();
			for (int m = 0; m < M; m++) {
				map[n][m] = (line[m] == 'W') ? 0 : 1;
			}
		}

		for (int n = 0; n < N; n++) {
			for (int m = 0; m < M; m++) {
				if (map[n][m] == 0 || map[n][m] == 1) {
					int target = map[n][m];
					int count = 0;
					queue.offer(new int[] { n, m });
					map[n][m] = -1;

					while (!queue.isEmpty()) {
						int[] now = queue.poll();
						count += 1;

						for (int i = 0; i < 4; i++) {
							int nx = now[0] + delta[i][0];
							int ny = now[1] + delta[i][1];

							if (isIn(nx, ny, N, M) && map[nx][ny] == target) {
								queue.offer(new int[] { nx, ny });
								map[nx][ny] = -1;
							}
						}

					}

					if (target == 0) {
						W += (count * count);
					} else {
						B += (count * count);
					}
				}
			}
		}

		sb.append(W).append(" ").append(B);

		System.out.println(sb);
	}

	private static boolean isIn(int x, int y, int n, int m) {
		return 0 <= x && x < n && 0 <= y && y < m;
	}
}

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

따로 적진 않았지만 사실 몇 달 전에 합격통보를 받고 8월부터 근무 중입니다.

아르바이트나 코딩(아두이노) 강사 등으로 월급도 받아봤고 작년엔 싸피 교육으로 9to6 생활을 1년간 했지만...

커리어라고 부를법한 무언가를 시작한 건 처음입니다.

명함도 받고

출근(재택근무)도 하고

업무도 배우고

팀원들끼리 meet up도 하고

지난 2주 동안 숨 쉬는 것 마저 새로울 정도로 모든 것이 다 처음이었습니다.

부족한 것도 많고 아직 적응도 안되지만 하나씩 배우고 익혀가며 발전해 나가고 있습니다.

알고리즘, 자료구조도 주말에 정리해야 되구요.

web 관련 지식도 잊어버리기 전에 복습해야 하는데 할게 너무 많습니다.

그런 의미에서 얼른 오늘 공부부터 해야겠습니다.

(화난게 아니라 열정으로 불타는 중입니다 ㅋㅋ)

이런 뻘 글을 쓰는 이유는... 먼 훗날에 시니어 개발자가 되고 나서 이 포스팅을 다시 보면서 오늘의 기분을 느껴보고 싶어서 일까요.

인터넷에 남기는 흑역사

https://school.programmers.co.kr/learn/courses/30/lessons/86491#qna

명함의 가로, 세로 크기의 최댓값을 포함하도록 지갑의 크기를 정해야 하는데, 명함을 돌릴 수 있으므로 명함의 긴 방향을 일치시키도록 돌리는 아이디어로 풀이할 수 있습니다.

극단적인 예를 들어, 1x10 10x1 두개의 명함을 이 상태대로 담으려면 10x10 사이즈의 지갑이 필요하지만, 하나의 명함을 돌리면 1x10 크기의 지갑에 담을 수 있습니다.

이런 상태를 만들기 위해서 w와 h값 중 한 방향을 정해 긴 쪽이 모두 일치하도록 돌려주고 최댓값을 찾으면 됩니다.

def solution(sizes):
    width = 0
    height = 0
    
    for size in sizes:
        w = size[0]
        h = size[1]
        
        if w < h:
            temp = h
            h = w
            w = temp
        
        if w > width:
            width = w
        if h > height:
            height = h   
    
    return width * height

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

2016년이 윤년이란 정보에 주의해서 입력의 일수에 월 별 지난 일 수를 저장해 줍니다.

예를 들어, 1월은 6일은 지난 월이 없어 그대로 6일 이지만 2월 6일은 1월이 지났기 때문에 31을 더해 37일이 됩니다.

또, 문제의 정보에서 생각해 보면 1월 1일(=1일)이 금요일이란 정보를 얻을 수 있습니다. 일주일은 7 단위로 반복되기 때문에, Index 1이 금요일인 길이 7의 배열을 만들어줍니다.

이제 입력된 날짜를 일수로 변환하고 7로 나눈 나머지의 Index 속 값을 취하면 쉽게 요일을 구할 수 있습니다.

def solution(a, b):
    month = [0,0,31,60,91,121,152,182,213,244,274,305,335]
    day = ['THU','FRI','SAT','SUN','MON','TUE','WED']

    daynum = month[a] + b
    answer = day[daynum % 7]
    return answer

solution(5,24)