프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 머리 아파서 좀 대충 풀었다 왜인지는 모르겠지만 게리맨더링이 생각나는 문제였다. 전선 개수가 최대 99개여서 하나하나 다 끊어보는 방법이 가장 먼저 떠올랐다. 1. 부모 배열과 부모를 찾는 함수 작성(분리집합) 2. 매 케이스마다 두 집합의 크기를 구해 차가 답보다 작은지 확인하자. 3. 전선 배열을 돌면서, 해당 전선을 제외하고 모든 전선을 확인해 집합을 둘로 나눈다. 4. 부모 배열을 초기화한다. 이렇게 작성했는데, 통과하고 다른 사람 풀이를 보니 dfs 한 번만으로 해결했더라... 전선을 모두 확인해 트..
programmers
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1시간 고민하고도 모르겠어서 질문 게시판에 있는 힌트를 봤지만, 문제를 애초에 잘못이해해서 힌트도 이해를 못 한 거였다;; 이 지문을 잘못이해해서, 내 양쪽 집이 둘 다 털리면 경보가 울리는 것으로 생각했었다. 그래서 첫 번째 집과 마지막 집에 포커스를 둘게 아니라, 첫 번째 집을 터느냐 마느냐만 생각하면 된다는 힌트도 이해를 못 했었다. 지문을 제대로 풀어보면 그냥 연속으로 집을 털지 말란 거다. (이 쉬운걸 왜 못 알아먹었을까) 2차원 배열로 DP 배열을 만들었고, DP[i][0]은 0번째 집을 털지 않았..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 백준에서 정렬, 스위핑 태그가 붙어있는 문제들의 풀이 유형이 떠올라 바로 적용했다. 우선 나가는 지점 오름차순으로 정렬한다. (나가는 지점이 같다면, 들어오는 지점이 작은 것이 앞으로 오도록 한다.) 최대한 많은 차량의 경로가 겹쳐야 단속카메라를 적게 달 수 있다. 나가는 지점을 기준으로 정렬했으니, 앞 차량의 나가는 지점(기준)이 뒷 차량의 들어가는 지점보다 크거나 같은 경우 차량들의 경로가 겹치므로 언제까지 겹치는지 확인하고 겹치지 않는 순간 단속카메라를 설치하고 기준을 바꿔준다. 첫 차량(i = 0)의 ..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 구명보트에 최대 2명만 탈 수 있다는 조건 덕분에 그리디를 잘 못 푸는 나도 빠르게 해결할 수 있었다. 구명보트 수를 줄이고 싶다면 최대한 2명씩 묶어서 탈출시켜야 한다. 무거운 사람을 최대한 가벼운 사람들과 매칭시키면 무거운 사람이 혼자 타서 탈출하는 경우를 줄일 수 있을 것이라 생각했다. 몸무게 오름차순으로 정렬한 후, 양 끝을 나타내는 인덱스(left, right)를 만들고 좁혀가며 보트의 수를 세자. 두 사람의 몸무게 합이 제한보다 크다면 무거운 사람이 혼자 타도록 하고 right만 감소시키자. 제한보..
