코딩테스트 연습 - 폰켓몬 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 import java.util.*; class Solution { public int solution(int[] nums) { HashSet set= new HashSet(); for(int i : nums){ //nums중복제거 set.add(i); } return set.size()>nums.length/2 ? nums.length/2 : set.size(); } } HashSet Set 인터페이스에서 지원하는 구현 ..
코딩테스트 연습 - 완주하지 못한 선수 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr HashMap을 이용한 풀이 import java.util.*; class Solution { public String solution(String[] participant, String[] completion) { String answer = ""; HashMap map = new HashMap(); //getOrDefault를 이용해 이름마다 value에 1 추가, 동명이인 구별 for(String key : ..
코딩테스트 연습 - 주식가격 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 1. 너무 더러운 내 코드 import java.util.*; class Solution { public int[] solution(int[] prices) { int[] answer = new int [prices.length]; Stack s =new Stack (); s.push(0); for(int i=1; i
힙정렬이란? 완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로 한 정렬방식 최댓값, 최솟값을 추출할 수 있는 자료구조 불안정 정렬 내림차순 정렬 => 최대 힙 / 오름차순 정렬 => 최소 힙 시간복잡도가 좋은편 가장 큰 값 몇개만 필요할 때 가장 효율적으로 사용 가능 완전 이진 트리란? [삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리] 힙 정렬 과정 최대 힙을 구성(내림차순 정렬 기준) 힙에서 한개씩 요소를 꺼내 배열 뒤에 저장 최대값부터 삭제하며 감소되는 순서로 정렬 시간 복잡도 최악 평균 최선 O(nlog₂n) O(nlog₂n) O(nlog₂n) [참고 자료] 링크
Insertion Sort란? 2번째 원소부터 시작하여 앞의 원소들과 크기 비교 후 삽입할 위치를 선정하고 원소를 뒤로 옮기면서 정렬하는 알고리즘 안전정렬이다 선택,버블 정렬보다 상대적으로 빠름 배열이 길어질수록 비효율 Insertion Sort 과정 2번째에 위치한 원소를 temp로 저장 temp와 이전 원소를 비교하여 삽입 1-2 반복 Insertion Sort Code public void insertionSort(int[]arr){ for(int i=1; i=0) && (arr[pre]>temp)){ //이전위치의 값이 더 클 경우 arr[pre+1]=arr[pre]; //값을 교환 pre--; } arr[pre+1]=temp; } } 시간 복잡도 최악의 경우(역으로 정렬되어 있을 경우) => O..
Selection Sort란? BubbleSort와 유사한 알고리즘으로 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘 원소 중 가장 작은 값을 선택하여 앞으로 이동 정렬하고자 하는 배열 안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬 BubbleSort에 비해 교환 횟수가 적기 때문에 많은 교환이 일어나는 자료상태에서는 비교적 효율적이다. 불안정 정렬이다. Selection Sort 과정 배열에서 최소값을 찾는다. 찾은 값을 맨 앞의 원소와 비교한 후 교체 맨 앞의 원소를 제외하고 1-2 반복 Selection Sort Code void selectionSort(int[] arr){ int min,temp; for(int i=0; i
🫧Bubble Sort란? 서로 인접한 두 원소의 크기를 비교하고, 조건에 맞도록 자리를 교환하며 정렬하는 알고리즘 코드가 직관적이고 간단하지만 매우 비효율적인 정렬 🫧Bubble Sort 과정 1회 차 : 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를... (N-1) 번째 원소와 N번째 원소를 비교하여 큰 수를 뒤로 이동 1회 차 후 가장 큰 수는 맨 뒤로 이동되므로 2회 차에서는 마지막 원소 제외(조건에 맞기 때문에) 다시 반복 회차를 반복 할 수록 제외되는 원소가 늘어나고 모든 원소가 조건에 맞게 정렬될 때까지 반복한다. 🫧Bubble Sort Code void bubbleSort(int[] arr){ int temp=0; for(int i=0;i n(n+1)/2 2개의 원소를 ..
