본문 바로가기
  • 개발하는 곰돌이

Algorithm/Programmers3

[Kotlin] 프로그래머스 : 테이블 해시 함수 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해설 문제를 해결하기 위해 가장 먼저 배열을 조건에 맞게 정렬해야한다. 2번 조건에 col번째 컬럼의 값을 기준으로 오름차순 정렬하고, 값이 동일하면 첫 번째 컬럼의 값을 기준으로 내림차순 정렬하라는 언급이 있으므로 data를 해당 조건에 맞게 정렬한다(코드의 3번째 줄). 이후 row_begin번째 튜플부터 row_end번째 튜플까지의 \(S_i\)를 구하여 별도의 배열 또는 리스트에 저장한다(코드의 4~11번째 줄). 마지막으로 각 \(S_i\)에 대하여 XOR 연산을 수행하여 반환한다. .. 2022. 12. 28.
[Java] 프로그래머스 : 주식가격 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해설 문제 분류가 스택/큐라고는 하지만 배열만 이용해도 충분히 풀 수 있는 문제다. 문제의 조건에 따라 prices의 각 요소마다 그 이후의 요소들과 비교하여 값이 작아지는 경우가 있는지 확인하고, 값이 작아지는 경우가 있다면 값이 작아진 인덱스 까지의 거리를 구한 후 다음 요소로 넘어간다. Code class Solution { public int[] solution(int[] prices) { int[] answer = new int[prices.length]; for (int i = 0;.. 2022. 11. 29.
[Java] 프로그래머스 : 더 맵게 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 힙 트리(heap tree)를 사용하는 문제다. 입출력 예의 설명에 따르면 모든 음식의 스코빌 지수가 K이상이 되지 않았을 때는 문제의 조건에 따라 만들어진 새로운 음식도 섞이는 대상이 될 수 있다. 스코빌 지수가 가장 낮은 두 수를 지속적으로 뽑아내고 새로운 음식을 집어넣으면서 정렬을 해야하는데, 일반적인 배열이나 리스트를 사용하면 음식을 섞을 때마다 매번 정렬을 하게 되면 시간복잡도 상으로 굉장한 손해를 보게 된다. 따라서, 힙 트리를 사용하는 것이 바람직하다. 힙 트리 방식으로 동작하는 대표적.. 2022. 11. 24.