출항사

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

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 자체는 매우 쉽지만, java comparator를 연습하기 좋아 보여서 풀었다. 문제에서 하라는대로 하면 바로 뚫리는 문제다. 요구사항은 아래와 같다. 1. 수록곡이 많은 장르를 우선순위로 내림차순 정렬한다. 2. 수록곡을 기준으로 내림차순 정렬한다. 3. 초기 index 위치를 기준으로 오름차순 정렬한다. 이를 관리하기 위해 map 두개를 활용했다. 하나는 장르별로 수록곡이 총 몇개인지? 다른 하나는 장르별 초기 인덱스를 저장하는 map이다. 그다음, 구현만 하면 끝이다. 단 주의할점이 하나 있는데,..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr {1, 1}에서 출발한 뒤 {N, M}에 도달할 수 있는 최소 비용을 구하라고 한다. 간선의 가중치는 1이므로 BFS나 DFS로 풀린다. Queue 문법에 좀 익숙해지려고 BFS로 풀었는데, 크게 고려할 점이 없어서 단순 구현만으로도 풀리는 문제이다. import java.util.*; class Solution { private int[] dx = {0, 0, -1, 1}; private int[] dy = {1, -1, 0, 0}; private Queue q = new LinkedList(); priva..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr A, E, I, O, U 순서로 길이가 5이하인 문자열을 만들 수 있다고 한다. 이때 특정 문자열이 몇번째 문자열인지 구해야한다. 제한이 매우 작기에 별도의 규칙을 찾을 필요는 없고, 직접 다 구하는 브루트포스를 돌려주는게 가장 간단해 보인다. 그리고 브루트포스를 돌렸을때 시간복잡도는 O(5^5) 정도 소요된다. import java.util.*; class Solution { private List words = List.of("A", "E", "I", "O", "U"); private Integer cou..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간단한 문제이지만, ArrayList를 정렬하는 문법이 익숙치 않아 조금 걸렸다. 구하고자 하는 것은 최대한 작은 종류의 귤을 사용해 k를 맞출 수 있는가? 이다. 탐욕법으로 접근해보면, 가장 개수가 많은 귤의 종류부터 선택하면 될것이다. 이 방법으로 구한 귤의 종류보다 절대 적게 k를 맞출 수 없기 때문이다. 그래서 귤의 종류별로 개수를 관리하는 Map을 하나 만들고, Map에 들어있는 value를 기준으로 내림차순 정렬을 해준다. 그다음 배열의 앞에서부터 귤을 제공하고, k가 넘어가는 순간 종료하면 된다...

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간단하게 해결할 수 있는 문제지만, java로 알고리즘 문제를 많이 안풀어봐서 조금 버벅였다. 문제를 쉽게 풀어내기 위해 어떤 순서로 해결할지 생각해봤다. 1. 우선 set으로 주어진 skill 트리에 있는 문자열들을 전부 관리한다. 그다음 skill_trees에 있는 문자열을 하나씩 꺼내 skill에 들어있는 문자열만 포함하는 문자열을 만들어줬다. 2. 올바른 skill_tree 가 되기 위해서는 순서가 무조건 정해진대로 되어야 한다. 그래서 주어진 스킬의 순서가 [1, 2, 3, 4, 5]라고 할때, [1..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 꽤나 재밌는 문제이다. N개의 풍선이 주어지고, 2개씩 풍선을 비교한다. 이때 큰 값을 가지고 있는 풍선은 사라지는데, 딱 한번 작은 풍선이 먼저 사라지는 경우를 넣을 수 있다고 한다. 제한이 매우 크기 때문에 브루트 포스는 절대 불가능 하고, DP도 아니고... 먼저 양끝 풍선에 대해 관찰 해보면, 이들은 무조건적으로 정답의 후보가 될 수 있다는 것을 알 수 있다. 그래서 '각 풍선을 기준으로 우승자가 될 수 있는지?'로 관점을 바꿔 문제를 접근했다. 하나의 풍선을 마지막 까지 남겨놓고 나머지 풍선들을 우선..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 전형적인 DP 문제이다. 제일 위에 있는 꼭짓점부터 가장 밑변까지 이동할때 얻을 수 있는 최댓값을 구해야 한다. 이를 삼각형 모습 그대로 본다면 굉장히 구현하기가 귀찮아진다. 그래서 어떻게 하면 쉽게 해결할 수 있을지 고민을 해보자. 이 그림에서 7을 잡고 쭉 잡아 왼쪽에 붙힌다고 생각해보자. 그러면 값은 아래와 같이 변한다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 이제 우리가 알고싶은 갚은 매우 간단하게 계산할 수 있다. 각 위치에 도달하기 위해서는 바로 자신의 위 혹은 왼쪽 대각선에서 내려올..