문제 분석https://www.acmicpc.net/problem/15683n*m 배열이 주어진다. 각 배열의 원소는 값에 따라 아래의 역할을 한다. 0 : 빈 땅1~5 : CCTV6 : 벽 각 CCTV는 1~5의 값에 따라 감시할 수 있는 방향의 유형이 정해져있고, 특정 방향으로 바라보는 CCTV는 배열의 끝 혹은 벽을 만나기전까지 감시를 할 수 있다. CCTV의 방향은 아래와 같다. CCTV는 90도씩 회전할 수 있다. 이때, CCTV들을 특정 각도로 회전시키며 배열을 감시할 때 사각지대의 최솟값을 구하는게 문제다. 여기서 주의할 점은, 벽과 CCTV가 존재하는 곳은 사각지대로 세지 않는다. 문제를 객체지향적으로 접근한다면, 즉 조금 더 세분화해서 쪼개보면 각 CCTV를 조금 더 단순하게 표현할 ..
문제 분석https://www.acmicpc.net/problem/2531 회전 벨트 위에 초밥이 있고, 각 초밥은 종류가 존재한다.손님은 k개 연속으로 초밥을 먹는다.이때, 보너스로 c 종류 초밥을 하나 더 공짜로 먹는다. 그렇다면, 손님이 먹은 초밥의 종류의 최댓값은 얼마인가 ? 손님은 0~k, 1 + 1+k .. 의 초밥을 연속해서 먹는다.이때, n-1,0,1 .. 이런 순서로도 먹을 수 있다. 처음과 두번째 경우를 비교하면, 1~k까지의 초밥은 공통으로 먹게된다.따라서, 굳이 이걸 반복해서 다시 찾을 필요가 없다. 즉, 처음 먹은 0~k개의 초밥에 대해서 그 종류들과 각 종류 별 count를 저장하고두번째부턴 0번째 먹은 초밥을 빼고, k+1번째 초밥을 더하면 된다. 따라서, 매 반복에서 현재 초..
문제 분석https://www.acmicpc.net/problem/1522a와 b로 이루어진 문자열이 주어진다.주어진 문자열에서 원소들을 swap하여 a를 모두 이어붙이고자 한다.이때, 주어진 문자열의 맨 앞과 맨끝은 붙어있는 형태, 즉 원형이라고 할 때 a를 모두 이어붙이기 위한 최소 swap 수는 ? 문제를 어렵게 생각하면 미궁에 빠질 수 있지만,, 조금 더 간단하게 생각해보자 우선, 맨 앞과 맨 뒤는 이어져 있다. 그렇기에 배열에서 굳이 떨어트려놓을 필요가 없다.따라서 아래처럼 문자열을 바꿔서 생각을 해보자abababababababa => aababababababab 어떤게 가장 효율적으로 a,b를 스왑하게 되는걸까 ? 이미 맨뒤의 a들을 맨 앞으로 옮겨놨으니 사실 원형이라는 조건은 이제 잊어도된다..
문제 분석https://www.acmicpc.net/problem/1976N개의 도시와 각 도시와 연결된 도시들에 대한 정보가 주어진다.M개의 도시 방문 경로가 가능한 경로인 지 확인하여 가능하다면 YES 아니면 NO를 반환하면 되는 문제다, 여기서 경로에 대해 최적인지 판단할 필요가 없다.따라서, 두 도시 사이에 어떠한 길이의 경로로든 연결만 되어 있다면 갈 수 있게 된다. 그렇기에 union find로 각 도시의 부모를 하나 정하고 두 도시의 부모 idx가 동일하면 같은 집합임을 의미하고 이는 곧 서로의 도시로 갈 수 있다는 뜻이 된다. 주의할 점은, m개의 방문 도시를 0,1, .. 이렇게 주는게 아닌, 1,2,... 이렇게 주니 인덱스를 애초에 1부터하던가 아니면 M개의 도시의 인덱스를 1 빼고 ..
문제 분석https://www.acmicpc.net/problem/22866N개의 배열에 대해 i번째 원소의 왼쪽 (0~i-1)과 오른쪽 (i+1 ~ n-1) 에 대해서 각각i번째 원소의 값보다 큰 원소를 i번째 원소가 볼 수 있다.왼쪽을 쳐다보는 기준 a 0번째 빌딩부터 오른쪽으로그리고 마지막 빌딩부터 0쪽 방향, 즉 왼쪽으로 2번에 걸쳐서 탐색하며 문제를 해결했다. 스택에 순차적으로 빌딩을 삽입하고i번째 빌딩보다 높은 빌딩만 남겨둔다면결국 스택의 크기가 i번째 빌딩이 볼 수 있는 빌딩의 수가 되고스택의 peek의 값이 가장 최근에 삽입된, i와 가장 가까운 볼 수 있는 빌딩이 된다. 이를 왼쪽 -> 오른쪽, 오른쪽 -> 왼쪽으로 한 번씩 탐색하면 i의 입장에서 볼 수 있는 빌딩의 수와 가장 가까운 i..
문제 분석https://school.programmers.co.kr/learn/courses/30/lessons/152996# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr시소 중앙에서 2,3,4 미터 떨어져 있을 수 있고 왼쪽과 오른쪽의 무게는 거리*앉은 사람의 무게로 정해진다.각 사이드엔 한명만 시소를 탄다고 할 때, 시소가 균형을 이룬다면, 즉, 왼쪽과 오른쪽은 곱의 크기가 같다면 균형을 이룬다.이때, 균형을 이루는 쌍의 수를 구하라. 무게 자체가 1000밖에 되지 않는다. 따라서, *4를 해도 4000정도다.따라서, 각 무게의 곱을 배열의 인덱스로 해..
문제 분석https://school.programmers.co.kr/learn/courses/30/lessons/154538 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.krx를 y로 만들 수 있는 지 묻는 문제다.규칙은 x에 n을 더하거나, 2 또는 3을 곱해가며 y를 만들 수 있다면 그 최소 횟수를, 없다면 -1을 리턴하면 된다. x에 해당 규칙들을 가해가며 y를 찾는 방법도 있겠지만, 나는 y에서 n을 빼거나 2 또는 3으로 나누어가며 x를 찾는 방식으로 문제를 풀었다. NumInfo객체에 현재 수의 값과 현재까지의 연산 횟수를 저장하고해당 객체를 PQ에 ..
문제 분석https://school.programmers.co.kr/learn/courses/30/lessons/154539 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr배열이 주어지고 각 배열의 원소는 자신보다 뒤에 있는 원소 중 자신보다 크고 그 index가 가장 작은 원소를 자신의 뒷큰수로 여긴다. 각 원소에 대해 뒷큰수들을 찾아 배열에 저장하여 리턴하는 것이 목적인 문제다. 단, 뒷큰수가 없으면 -1을 배열에 저장하면 된다. 길이 자체가 10^6이기에 n^2의 풀이는 통과되기 힘들다.즉, 각 배열의 원소에 대해 자신의 뒤 원소들을 탐색하며 뒷큰수를 찾..
