프로그래머스 - 알고리즘 공부

문제 설명

모든 문제를 풀수 있도록 알고력과 코딩력을 얻는데 걸리는 최소 시간을 구하는 문제이다.

주의사항

• 배열의 인덱스 범위 설정
  • 최고 가질 수 있는 알고력과 코딩력은 최대 150이다.
  • 그런데 내가 문제를 풀 때 150이상의 알고력 또는 코딩력을 얻을 수 있음을 유의해야 한다.
  • 배열을 더 크게 잡거나 혹은 배열 범위를 넘어갈때 안쪽으로 다시 조절해줘야 한다.
• 다익스트라 풀이 주의사항
  • 아마 효율성 부분을 통과할 수 없을 수 있다.
  • 이부분은 우선순위 큐에 있는 쓸데없는 데이터들이 많아서 그런것일 수 있다.
  • 하지만 또다른 에외도 존재한다.
    • 정제를 안해줘서 가 아니라 코드가 좀 길어서 시간초과가 난다..
    • 스타일 차이인데 왜 시간초과가 나는지 모르겠다..

TRY

1. 다이나믹 2022 테크 여름인턴십 코딩테스트 해설- 다이나믹을 생각했지만 어떻게 점화식을 이뤄야 할지 몰랐다.
2. 다익스트라

풀이

다이나믹

public int solution_dp(int alp, int cop, int[][] problems) {
		int[][] dp = new int[152][152];
		int targetAlp = 0;
		int targetCop = 0;
		for (int[] problem : problems) {
			targetAlp = Math.max(targetAlp, problem[0]);
			targetCop = Math.max(targetCop, problem[1]);
		}

		// alp가 더 많거나 혹은 cop가 목표치보다 높을 때 예외처리
		if (targetAlp < alp) {
			alp = targetAlp;
		}

		if (targetCop < cop) {
			cop = targetCop;
		}

		for (int i = alp; i < 152; i++) {
			Arrays.fill(dp[i], 999_999);
		}

		dp[alp][cop] = 0;

		for (int i = alp; i <= targetAlp; i++) {
			for (int j = cop; j <= targetCop; j++) {
				dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + 1);
				dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i][j] + 1);
				for (int k = 0; k < problems.length; k++) {
					int reqAlp = problems[k][0];
					int reqCop = problems[k][1];
					int rewAlp = problems[k][2];
					int rewClp = problems[k][3];
					int time = problems[k][4];
					/**
					 * 예외의 핵심
					 * 만약 범위를 넘어가서 알고력과 코딩력을 달성했다면
					 * 그래도 목표 알고리즘의 최솟값이 들 수 있는 경우가 있다.
					 */
					if (i >= reqAlp && j >= reqCop) {
						int ny = i + rewAlp;
						int nx = j + rewClp;

						if (ny > targetAlp) {
							ny = targetAlp;
						}

						if (nx > targetCop) {
							nx = targetCop;
						}

						dp[ny][nx] = Math.min(dp[ny][nx], dp[i][j] + time);
					}
				}
			}
		}

		return dp[targetAlp][targetCop];
	}

다익스트라

public int solution(int alp, int cop, int[][] problems) {
		List<Problem> problemList = new ArrayList<>();
		int targetAlp = 0;
		int targetCop = 0;
		for (int[] problem : problems) {
			targetAlp = Math.max(targetAlp, problem[0]);
			targetCop = Math.max(targetCop, problem[1]);
			problemList.add(new Problem(problem[0], problem[1], problem[2], problem[3], problem[4]));
		}

		// 시간 채우면 알고력 코딩력이 올라가는 것이 필요함.
		problemList.add(new Problem(0, 0, 1, 0, 1));
		problemList.add(new Problem(0, 0, 0, 1, 1));

		PriorityQueue<MyAbility> pq = new PriorityQueue<>();
		pq.offer(new MyAbility(alp, cop, 0));
		int times[][] = new int[151][151];
		for (int i = 0; i < 151; i++) {
			Arrays.fill(times[i], 9999);
		}
		times[alp][cop] = 0;

		while (!pq.isEmpty()) {
			MyAbility ability = pq.poll();

			if (times[ability.alp][ability.cop] < ability.time)
				continue;

			if (ability.alp == targetAlp && ability.cop == targetCop) {
				return ability.time;
			}

			for (Problem problem : problemList) {
				int nextAlg = ability.alp + problem.rewardAlg;
				int nextCop = ability.cop + problem.rewardCop;
				int nextTime = ability.time + problem.time;

				if (nextAlg > targetAlp) {
					nextAlg = targetAlp;
				}
				if (nextCop > targetCop) {
					nextCop = targetCop;
				}

				if (problem.canSolve(ability.alp, ability.cop) && times[nextAlg][nextCop] > nextTime){
					times[nextAlg][nextCop] = nextTime;
					pq.offer(new MyAbility(nextAlg, nextCop, nextTime));
				}
			}
		}

		return 0;
	}

	class MyAbility implements Comparable<MyAbility> {
		int alp, cop, time;

		public MyAbility(int alp, int cop, int time) {
			this.alp = alp;
			this.cop = cop;
			this.time = time;
		}

		@Override
		public int compareTo(MyAbility o) {
			return time - o.time;
		}
	}

	class Problem {
		int conditionAlg, conditionCop;
		int rewardAlg, rewardCop;
		int time;

		public Problem(int conditionAlg, int conditionCop, int rewardAlg, int rewardCop, int time) {
			this.conditionAlg = conditionAlg;
			this.conditionCop = conditionCop;
			this.rewardAlg = rewardAlg;
			this.rewardCop = rewardCop;
			this.time = time;
		}

		public boolean canSolve(int myAlp, int myCop) {
			return this.conditionAlg <= myAlp && this.conditionCop <= myCop;
		}

	}

다익스트라 시간 초과 예외

정제를 안해줘서 가 아니라 코드가 좀 길어서 시간초과가 난다..

위 다익스트라 풀이에 problem을 순회하는 코드를 보면 if문이 하나만 들어가 있다.

다시말해서 타이트한 조건에만 수용하도록 구현했다.

그런데 나는 예외를 쳐내는 식으로 구현했었다. 그런데 시간초과가 났다.

for (Problem problem : problemList) {
				if (!problem.canSolve(ability.alp, ability.cop)) // 못풀면 
					continue;
				int nextAlg = ability.alp + problem.rewardAlg;
				int nextCop = ability.cop + problem.rewardCop;
				int nextTime = ability.time + problem.time;

				if (nextAlg > targetAlp) {
					nextAlg = targetAlp;
				}
				if (nextCop > targetCop) {
					nextCop = targetCop;
				}

				if (times[nextAlg][nextCop] < nextTime) { // 이미 빠른시간에 풀었던 경험이 있다면
					continue;
				}

				times[nextAlg][nextCop] = nextTime;
				pq.offer(new MyAbility(nextAlg, nextCop, nextTime));
			}