일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- 오브젝트 풀링
- 프리팹
- Animation State Machine
- Object Pooling
- Prefabs
- CSharp #자료구조
- rigidbody
- Hp바
- LayerMark
- Vector3
- 플레이어 이동
- 플레이어 방향전환
- apk
- Ainimation Blending
- Object Poling
- raycasting
- rotation
- 패럴렉스
- raycast
- 2D슈팅게임
- Blend Type
- 스크롤링
- Transform
- 유니티
- Hpbar
- Scrooling
- 일시정지
- Parallax
- joystick
- Unity
- Today
- Total
주녘공부일지
[프로그래머스 C#] Lv.4 지형 편집 본문
https://school.programmers.co.kr/learn/courses/30/lessons/12984
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
1. 정답코드 및 핵심 아이디어, 유의사항
주어진 2차원 영역의 층을 같은 높이로 맞추는 데에 드는 최소 비용을 구하는 문제
- 같은 높이로 맞추기 위해 가능한 건, 층을 추가하거나 삭제하는 것 뿐 (이동X)
-> 층을 추가하는 비용과 삭제하는 비용은 따로 주어짐
중복 연산 최적화 아이디어
- 주어진 2차원 배열을 리스트에 저장해 오름차순으로 정렬 ( 계단 형태가 됨 )
- 정렬된 리스트를 0번 인덱스부터 순회해 가장 낮은 층부터 높은 층의 방향으로 만들어나감
- 현재 만들려는 층에 대한 연산은 이전에 만들었던 층의 결과에 추가, 삭제해 중복 연산을 최소화
-> 이전 층보다 높아지면서 제거했던 블록을 복구해야 함 (제거한 비용을 돌려받기)
-> 이전 층보다 높아지면서 층을 맞추기 위해 블록을 추가해야 함
( 위 두개의 연산의 제거하거나 추가하는 영역은 무조건 직사각형 영역이 됨 )
+ 주어진 문제의 특성 상 만들려는 층에 따른 비용 그래프는 2차원 그래프 형태를 띄므로 가장 낮은 층에서부터 높은 층으로 탐색을 이어갈 때 최소 비용이 갱신이 되지 않는다면, 층에 따라 탐색되는 비용은 점점 높아지므로 탐색할 필요가 없음
+ 층의 높이의 최대 값은 10억으로 int 자료형의 범위를 벗어나기 쉬우므로 long 자료형으로 연산하게 되는데, 형 변환이 되지 않아 값이 잘못되는 경우를 유의해야 함
주석 참조
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public long solution(int[,] land, int p, int q)
{
long minCost, currCost; // 최소비용. 현재비용
var list = new List<int>(); // 각 칸의 블록 개수 (층 개수)
foreach (int i in land)
list.Add(i);
list.Sort(); // 오름차순 정렬
// 가장 낮은 층으로 만드는 비용 (가장 낮은 층을 기준으로 모든 층 제거)
long subNum = (long)list[0] * list.Count;
currCost = (list.Sum(x => (long)x) - subNum) * q;
minCost = currCost;
for (int i = 1; i < list.Count; i++)
{
// 같은 층에 대해 다루게 되므로 pass
if (list[i - 1] == list[i])
continue;
long addFloor = list[i] - list[i - 1]; ; // 층 증가 수
// 만들려는 층이 변경됨에 따라 제거했던 층을 취소
currCost -= addFloor * (list.Count - i) * q;
// 만들려는 층이 변경됨에 따라 추가되는 층을 추가
currCost += addFloor * i * p;
// 최소 비용이 갱신되지 않는다면
if (minCost < currCost)
break;
minCost = currCost;
}
return minCost;
}
}
'Programmers - C# > CodingTest Lv.4' 카테고리의 다른 글
[프로그래머스 C#] Lv.4 지형 이동 (0) | 2024.02.02 |
---|---|
[프로그래머스 C#] Lv.4 쿠키 구입 (0) | 2024.01.18 |
[프로그래머스 C#] Lv.4 올바른 괄호의 갯수 (1) | 2023.10.18 |