내일은 알고리즘

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

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)