99클럽 코테 스터디 28일차 TIL

비기너

문제

506. Relative Ranks

#정렬 #맵

https://leetcode.com/problems/relative-ranks/description/

풀이

운동선수의 점수가 주어졌을 때 운동선수의 등수를 구하는 문제이다.

등수를 구하기 위해 점수를 정렬한다.

정렬을 하면 원본 배열이 변하므로 원본 배열은 복사해서 유지시켜 놓는다.

점수를 등수와 매핑시키기 위해 맵에 저장한다.

1, 2, 3등은 각각 등수 대신 Gold Medal, Silver Medal, Bronze Medal로 표현해야 한다.

원본 배열에서 주어진 점수대로 등수를 구하여 반환한다.

코드

import java.util.*;

class Solution {
    public String[] findRelativeRanks(int[] score) {
        int[] tmp = new int[score.length];
        for (int i = 0; i < score.length; i++)
            tmp[i] = score[i];
        Arrays.sort(score);

        HashMap<Integer, String> mp = new HashMap<>();
        for (int i = 0; i < score.length; i++) {
            if (i == score.length - 1) 
                mp.put(score[i], "Gold Medal");
            else if (i == score.length - 2)
                mp.put(score[i], "Silver Medal");
            else if (i == score.length - 3) 
                mp.put(score[i], "Bronze Medal");
            else
                mp.put(score[i], (score.length - i) + "");
        }

        String[] ans = new String[tmp.length];
        for (int i = 0; i < tmp.length; i++)
            ans[i] = mp.get(tmp[i]);

        return ans;
    }
}

미들러

문제

11055번: 가장 큰 증가하는 부분 수열

# 동적계획법

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

풀이

가장 큰 증가하는 부분 수열의 합을 구하는 문제이다.

동적계획법을 이용하여 n번째 수에서 끝나는 가장 큰 증가하는 부분 수열의 합을 구한다.

n번째 수에서 끝나는 증가하는 부분 수열 중 합이 최대인 것은 1 ~ n - 1의 증가하는 부분 수열 중 합이 최대인 것을 고르면 된다. 

(단 a[n] < a[i], 1 <= i <= n - 1)

따라서 1부터 시작해서 n까지 반복을 통해 만든 모든 증가하는 부분 수열의 합를 저장한 배열에서 최댓값을 찾아서 출력하면 된다.

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int[] a = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			a[i] = Integer.parseInt(st.nextToken());

		int[] d = new int[n];
		d[0] = a[0];
		int ans = d[0];
		for (int i = 1; i < n; i++) {
			d[i] = a[i];
			for (int j = 0; j < i; j++) {
				if (a[i] > a[j])
					d[i] = Math.max(d[i], d[j] + a[i]);
			}
			ans = Math.max(ans, d[i]);
		}

		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}