출항사

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 약간의 테크닉이 필요한 다익스트라 응용 문제이다. 출발점 노드들이 주어지고, 산봉우리 노드들이 주어진다. 출발지 노드를 start라 하고, 산봉우리 노드를 end라고 하겠다. 우리가 구하고 싶은 값은 start -> end -> start로 탐색을 진행할때 지나온 간선의 가중치 최솟값이다. 여기서 약간만 생각하면 start -> end만 구해도 된다는 것을 눈치챌 수 있다. 굳이 end -> start를 탐색할 필요가 없기 때문이다. 그냥 start -> end에 도달하는 경로를 찾았다면 그 길을 따라서 그대..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 제한이 매우 널널해서 DFS로도 풀리는데 그냥 BFS가 더 간단해서 BFS로 풀었다. 구하고자 하는 것은 2차원 배열이 주어질때, 'P'의 거리가 2이하인 경우가 있는지 없는지이다. 따라서 'P'를 기준으로 탐색을 진행해서 거리 2 이내에 다른 'P'가 있는지 확인하면 된다. 주의해야 할것은 BFS를 돌릴때마다 방문 배열을 전부 밀어버려야 한다는 것이다. O(N^5)에 풀린다. import java.util.*; class Solution { private int[][] visited = new int[5][..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr numbers 배열이 주어진다. 우리가 구하고 싶은 값은 numbers[i]를 기준으로 [i+1 ... numbers.length] 사이에 있는 숫자중 가장 가까우면서 numbers[i]보다 큰 숫자이다. 제한이 100만이기 때문에 O(N), O(NlogN) 이내에 풀어야 할 것 같은데 logN은 이분탐색말고 떠오르지 않으니 그냥 O(N)으로 접근해보자. 뒤에 있는 숫자 중 하나를 채우는 것이기 때문에 딱봐도 뒤에서부터 무엇인가 하면 될것 같은 느낌이 든다. 그래서 뒤에서 부터 값을 채우도록 문제를 접근해보자..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 먼저 나이브하게 문제를 접근해보자. 존재하는 곡괭이의 개수는 최대 15개이다. 그리고 광물의 개수는 50개이다. 곡괭이 무조건 5개의 광물을 캐야한다는 조건이 있다. 50개의 광물을 캐기 위해서는 10개의 곡괭이가 필요한 것을 알 수 있다. 즉, 최대 10개의 곡괭이만 사용하게 된다. 그러면 15개의 곡괭이 중 10개를 뽑는데 15C10의 시간복잡도가 소요된다. 그리고 뽑은 곡괭이를 최소값이 되도록 나열해야 하는데, 10!의 시간복잡도가 소요된다. 이 둘을 곱하면 절대 문제를 해결할 수 없다는 것을 알 수 있..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 귀찮았던 구현 문제이다. 주어진 조건대로 구현을 하면 되는데 주의할 부분이 하나 있다. 문제에서 요구하는 시뮬레이션 순서는 아래와 같다. 시간이 되면 새로운 과제를 시작한다. 새로운 과제를 수행할때, 기존에 수행하던 과제가 있으면 대기열로 해당 과제를 보낸다. 현재 진행중인 과제가 끝이 나면, 대기중인 과제를 이어서 수행한다. 이렇게 케이스를 나눠볼 수 있다. 사실 케이스를 더 쪼갤 수 있지만, 새로운 과제가 있다면 무조건 시작해야 하기 때문에, 조건문 순서를 잘 걸어두면 간소화할 수 있다. 대기열에 들어간 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr N개의 몸무게가 주어지고, 시소가 주어진다. 시소에는 2, 3, 4 칸 중 하나에 앉을 수 있다. 이때 균형을 맞출 수 있도록 앉는 경우의 수를 구해야 한다. N은 10만 이하이므로 O(N^2)에는 안풀린다. 우리가 궁금한 것은 개수다. 그러니 각 몸무게별로 인원 수를 map에 저장하자. 그리고 이 key 값들을 이용해서 짝의 개수를 세면 된다. 앉을 수 있는 자리가 2, 3, 4이므로 2중 for문을 돌려주자. 현재 몸무게를 w라고 할때, 2, 3, 4 모두에 앉혀봐야 한다. 그리고 이때 반대편에 앉을 수 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간단하게 생각해보면, 매우 쉬운 문제이다. N까지 도달하고 싶은데, 2배씩 건너뛸 수 있다고 한다. 그리고 1칸씩 이동할 수 있는데, 1칸씩 이동하는 횟수를 최소로 만들고자 한다. 뒤에서부터 생각해보자. N = 1000일때, 가장 이득인 방법은 N = 500에서 2배로 뛰는 방법일 것이다. 그리고 N = 250 에서 500으로 뛰고 ... 이러다 보면 N = 125에서 막히는데, 홀수이기 때문이다. 그래서 1칸 이동했다 치고, N = 124부터 보자. 이런식으로 N = 0이 될때까지 확인하면 된다. 간단하게 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간단한 문자열 문제이다. 이전에 등장한 단어를 부르거나, 마지막 영단어와 끝말잇기가 되지 않는 순간을 찾아야 한다. 몫과 나머지 연산으로 몇번째 사람의 몇번째 순서인지 간단하게 구할 수 있고, 현재까지 언급된 단어는 set을 통해 간단히 관리할 수 있다. 따라서 시간복잡도 O(NlogN)내에 문제를 해결해낼 수 있다. import java.util.*; class Solution { private Set st = new HashSet(); private List list = new ArrayList(); pu..