내일은 알고리즘

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

문제에서 시키는대로 구현하면 되는 시뮬레이션 문제입니다. 

몬스터의 마지막 공격이 있을때까지 데미지를 계산하며 체력을 회복합니다. 이때 붕대를 x초 감게 되면 추가적으로 체력을 회복하는것을 신경써야 합니다. 구현에는 다음 과정들이 필요합니다.

1. 시간을 늘려가며 체크해 공격이 들어왔다면 데미지 계산, 체력이 0 이하라면 -1을 return

2. 공격이 들어오지 않았다면 붕대를 1초 더 감고 체력을 회복

2-1. 붕대를 x초째 감았다면 체력을 추가 회복, 붕대를 감은 연속 횟수를 0으로 초기화

def solution(bandage, health, attacks):
    h, idx, b, e = health, 0, 0, attacks[-1][0]
    
    for i in range(e + 1):
        if i == attacks[idx][0]:
            h -= attacks[idx][1]
            b = 0
            idx += 1
        else:
            b += 1
            h = min(health, h + bandage[1])
        
            if b == bandage[0]:
                b = 0
                h = min(health, h + bandage[2])
        
        if h <= 0:
            return -1
    
    return h

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

간단한 구현문제입니다.

바탕화면의 모든 파일을 한 번에 선택하기 위해서는 좌상단, 우하단의 점들 안에 모든 파일의 좌표가 존재해야합니다. 최소값 좌표와 최댓값 좌표 두개를 미리 준비해놓고 #이 존재하는 좌표마다 각각의 x, y 혹은 r, c에 대해 최소 최대를 갱신해주면 됩니다.

변수를 선언할 때 초기값이 입력사이즈 안에 들어가지 않도록 주의해주세요.

def solution(wallpaper):
    lr, lc, rr, rc = 100, 100, -1, -1
    
    for i in range(len(wallpaper)):
        for j in range(len(wallpaper[0])):
            if wallpaper[i][j] == '#':
                lr = min(lr, i)
                lc = min(lc, j)
                rr = max(rr, i + 1)
                rc = max(rc, j + 1)
    
    return [lr, lc, rr, rc]

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

레벨 1 치고 구현 난이도가 약간 있는 시뮬레이션 문제입니다. 이 문제에서 우리가 구현할 기능들을 추려보자면 다음과 같습니다.

1. 산책을 시작하는 좌표를 찾기

2. 입력으로 주어진 방향과 이동 거리를 분석

3. 이동이 가능한지(공원 밖을 나가지 않는지, 이동 경로에 장애물이 있는지) 판단하기

4. 이동이 가능하다면 이동시키기

그대로 구현을 하고 주어진 입력대로 모두 이동한 후에 최종 좌표를 return 하면 됩니다.

def solution(park, routes):
    delta = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    dset = {"N":0, "S":1, "W":2, "E":3}
    r, c, n, m = 0, 0, len(park), len(park[0])
    
    def cango(r, c, d, w):
        nonlocal n, m
        
        for i in range(w):
            r += delta[d][0]
            c += delta[d][1]
            
            if r < 0 or r >= n or c < 0 or c >= m or park[r][c] == 'X':
                return [-1, -1]
            
        return [r, c]
    
    for i in range(n):
        for j in range(m):
            if park[i][j] == 'S':
                r = i
                c = j
    
    for route in routes:
        d, w = route.split(' ')
        d = dset[d]
        w = int(w)
        
        res = cango(r, c, d, w)
        if res[0] != -1:
            r, c = res[0], res[1]
                
    return [r, c]

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

18년 (시험은 17년에 이루어졌을 겁니다.) kakao 문제였다고 합니다.

입력을 적당히 잘 쪼개고 예외를 조심하면서 문제에 주어진 대로 구현하면 풀리는 문제입니다.

다트가 3개이기 때문에 저는 다트의 인덱스 idx와 입력의 인덱스 i를 다르게 관리해줬습니다. 또 점수가 10인 경우를 주의해야 합니다.

def solution(dartResult):
    answer = [0, 0, 0]

    idx = -1
    i = 0

    while i < len(dartResult):
        
        if dartResult[i] in ["S", "D", "T"]:
            if dartResult[i] == "D":
                answer[idx] *= answer[idx]
            elif dartResult[i] == "T":
                answer[idx] = answer[idx] * answer[idx] * answer[idx]
        
        elif dartResult[i] == "*":
            answer[idx] *= 2
            if idx - 1 >= 0:
                answer[idx - 1] *= 2
        
        elif dartResult[i] == "#":
            answer[idx] *= -1
        
        else:
            idx += 1
            if dartResult[i] == "1" and i < len(dartResult) - 1 and dartResult[i + 1] == "0":
                answer[idx] = 10
                i += 1
            else :
                answer[idx] = int(dartResult[i])
        
        i += 1

    return sum(answer)

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

counting sort의 개념이 살짝 녹아있는 문제입니다.

수 X와 Y에 대해 각 자릿수에 0~9 사이의 숫자가 몇개가 나오는지를 체크합니다.

어떤 숫자 i에 대해 X와 Y 중에 나온 수가 적은 값을 취합니다. (더 많은쪽은 짝을 이루지 못하고 남습니다.)

숫자 i를 짝이 이루어진 수 만큼 배열에 넣고 내림차순으로 정렬하면 정답이 됩니다.

단, 배열의 길이가 0이라면 "-1"을, 배열의 길이가 0의 갯수와 같다면 (즉 0 말고 다른 수가 배열 안에 없다면) "0"을 return하는 예외처리가 필요합니다.

def solution(X, Y):

    numx = [0 for i in range(10)]
    numy = [0 for i in range(10)]
    answer = []

    for n in X:
        numx[int(n)] += 1
    for n in Y:
        numy[int(n)] += 1

    pred = min(numx[0], numy[0])
    for i in range(10):
        n = min(numx[i], numy[i])
        for j in range(n):
            answer.append(str(i))

    answer.sort(reverse=True)

    if len(answer) == 0:
        return "-1"

    return ''.join(answer) if len(answer) > pred else "0"

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)

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

(문제가 무척 길어서 스크린샷은 생략..)

대학교 후배가 실버도장깨기를 하다가 막혔다며 SOS를 친 문제다.

자신만만하게 OK사인을 보내고 문제를 풀러갔다가, 100명도 되지 않는 적은 정답자 수에 놀라고 어마어마하게 긴 문제의 길이에 놀라고 불친절한 Input에 놀라고... 아무튼 생각보다 난이도 있는 문제였다.

처음에는 각 나무를 일종의 PriorityQueue처럼 보고 가능한 경우의 수를 모두 계산해서 최적해를 구하는 식으로 짜려고 했는데, 예외와 조건이 너무 많아서 불가능했다.

다른 후배도 같이 도전하던 와중에 그 친구가 먼저 정답을 통과했고, 전체적인 시간을 가지고 관리한다는 tip과 놓치고 있던 조건(최적해를 위해 기다리는것이 금지된다. 건널 수 있으면 바로 건넌다.)을 듣고 바로 구현을 마칠 수 있었다.

나무에 대기하고 있는 사람과

다리를 건너고 있는 사람

두개의 데이터를 가지고 가장 시간이 적게 걸리는 그룹이 다리를 건너는 시점마다를 트리거로 동작시켜서

빈 다리에 건널 사람이 있다면 채워 넣고, 다리를 건너는 그룹들은 남은 시간을 줄이는 식으로 구현했다.

코드는 이렇다.

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

public class Main {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();

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

		while (true) {
			st = new StringTokenizer(br.readLine());
			int B = Integer.parseInt(st.nextToken())*-1;
			int P = Integer.parseInt(st.nextToken());

			if (B == 0 && P == 0) {
				break;
			}
			int[] trees = new int[B + 1];
			trees[0] = P;
			trees[B] = -P;
			int[][] bridges = new int[B][2];
			int[][] groups = new int[B][2];
			int totalTime = 0;

			for (int b = 0; b < B; b++) {
				st = new StringTokenizer(br.readLine());
				bridges[b][0] = Integer.parseInt(st.nextToken());
				bridges[b][1] = Integer.parseInt(st.nextToken());
			}

			while (trees[B] < 0) {
				int time = Integer.MAX_VALUE;
				for (int b = 0; b < B; b++) {
					if (trees[b] > 0 && groups[b][0] == 0) {
						groups[b][0] = Math.min(trees[b], bridges[b][0]);
						groups[b][1] = bridges[b][1];
						trees[b] -= groups[b][0];
					}
					if (groups[b][1] > 0) {
						time = Math.min(groups[b][1], time);
					}
				}

				totalTime += time;

				for (int b = 0; b < B; b++) {
					if (groups[b][1] > 0) {
						groups[b][1] -= time;
						if (groups[b][1] == 0) {
							trees[b + 1] += groups[b][0];
							groups[b][0] = 0;
						}
					}
				}
			}
			sb.append(totalTime).append("\n");
		}

		System.out.println(sb);
	}
}