프로그래머스 문제
https://school.programmers.co.kr/learn/courses/30/lessons/131701
풀이 후기
0. 잡담
카카오 문제는 길이부터가 차이가 난다. 내용이 어려운 건 그렇다 쳐도, 요구사항이 너무 많아서 틀리게 구현하는 경우가 좀 많은 느낌. 그리고 AI 추천 문제에서 나오는 옛날 카카오 코테 문제는 c#을 지원 안 하는 경우가 너무 많아서 제대로 풀 수가 없다. 추천 문제에 선호하는 언어 넣을 수 있게 고쳐주세요.
1. 분석
너무 길어서 질문하기부터 봤는데 글도 6개라서 별 소득은 없을 줄 알았지만 전현서님 글이 있어서 다행이었다. 항상 감사합니다... 암튼 이해한 부분은 다음과 같다.
- 완전탐색 -> 그냥 순수 요구사항 구현
- 배송 문제 (https://velog.io/@soseuleaf/택배-배달과-수거하기)처럼 숫자 카드의 값은 모르겠지만, 아무튼 최적의 카드를 넣었다고 계산.
글은 더 길었는데 이해한 건 저거 2개다. 추가로 내가 생각한 것은 일종의 카드를 놓는 사이클이다. 모든 분기 노드의 엣지를 곱하면 나오는 값에 따라 카드가 반복되어 들어가고, 해당 사이클에 따라서 카드를 놓으면 되지 않을까? 해당 방법은 사이클 구하다가 시간초과로 폐기되었다.
간선 바꾸는 건 그냥 큐 구현하듯이 엣지를 한 바퀴 돌리는 느낌이라 특별한 건 없고, 나머지는 그냥 하라는 대로 해봤다.
- 카드를 한 개씩 넣어본다.
- 원하는 값이 카드를 1만 넣었을 때 이상이면 조건1 충족
- 원하는 값이 카드를 3만 넣었을 때 이하면 조건2 충족
- 카드 넣은 개수가 타겟보다 크면 망한 조건이므로 즉시 -1 반환
- 넣은 순서는 리스트에 저장해서 다시 계산하는 용도로 써야 한다.
- 그렇게 돌리다가 모든 리프 노드가 조건1,2가 충족되면 그게 가장 적합한 카드를 배치하는 방법.
- 넣은 순서를 따라가면서 다시 계산한다. 계산은 글로 쓰기 어려우니 코드 확인.
2. 실행 결과
3. 코드
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public Node[] nodes;
public class Node
{
public int index;
public int target;
public int direction = 0;
public int cards = 0;
public List<int> edges = new List<int>();
public bool IsLeaf => edges.Count == 0;
public bool IsBomb => target < cards;
public bool IsCountInRange => target <= cards * 3 && target >= cards;
public Node(int i, int t)
{
index = i;
target = t;
}
public void AddEdge(int n)
{
edges.Add(n);
}
public void AddCard()
{
cards++;
}
public void SortedEdges()
{
edges.Sort();
}
public int GetNextNodeNum()
{
var temp = edges[direction];
direction = (direction + 1) % edges.Count;
return temp;
}
public int CalculateCardValue()
{
// 이번 루프를 제외 하고 계산
cards--;
// 남은 루프를 3으로만 돌렸다고 가정하고, 1과 비교해서 큰 값 넣기
var leftNum = Math.Max(1, target - (cards * 3));
target -= leftNum;
// 뭐가 적합한지 리턴
return leftNum;
}
}
public int[] solution(int[,] edges, int[] target)
{
// 노드 생성
nodes = new Node[target.Length + 1];
for (int i = 0; i < edges.GetLength(0); i++)
{
var a = edges[i, 0];
var b = edges[i, 1];
if (nodes[a] == null)
{
nodes[a] = new Node(a, target[a - 1]);
}
if (nodes[b] == null)
{
nodes[b] = new Node(b, target[b - 1]);
}
nodes[a].AddEdge(b);
}
// 엣지 정리 및 리프 찾기
var leafs = new List<Node>();
foreach (var node in nodes)
{
if (node == null) continue;
if (node.IsLeaf) leafs.Add(node);
node.SortedEdges();
}
// 1카드만 계속 넣어보기
var inputOrder = new List<int>();
while (true)
{
var node = nodes[1];
while (node.IsLeaf == false)
{
node = nodes[node.GetNextNodeNum()];
}
node.AddCard();
inputOrder.Add(node.index);
// 불가능한 케이스인지 확인
if (node.IsBomb)
{
return new[] { -1 };
}
// 전부 조건 안에 있으면 탈출
if (leafs.All(leaf => leaf.IsCountInRange))
{
break;
}
}
// 순서대로 넣어 보면서 최적의 카드 값을 찾음
var answer = new List<int>();
foreach (var index in inputOrder)
{
var node = nodes[index];
answer.Add(node.CalculateCardValue());
}
return answer.ToArray();
}
}개인적으로 코드가 예쁘게 작성돼서 마음에 든다. 클래스를 최대한 자제하면서 빨리 구현하려고도 해봤는데 그냥 마음 편한 대로 하는 게 맞는 것 같다.
그냥 바보