Java 코딩테스트 공부/Java 알고리즘 공부

Java 정렬, 이분검색과 결정알고리즘 1

2022. 9. 2. 15:54

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard

 

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

자바(Java)로 코딩테스트를 준비하시는 분을 위한 강좌입니다. 코딩테스트에서 가장 많이 출제되는 Top 10 Topic을 다루고 있습니다. 주제와 연동하여 기초문제부터 중급문제까지 단계적으로 구성

www.inflearn.com

 

문제 1 :

숫자 n과 해당 n의 갯수만큼 숫자가 주어진다.

해당 숫자들을 오름차순으로 정렬해서 출력하는 프로그램을 작성하여라.

단, 선택 정렬을 이용

ex)

5

2 6 13 5 9

->

2 5 6 9 13

 

선택 정렬이란?

gif 출처 : https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/resources/selection-sort-001.gif

 

소스코드 (빠른 입출력과 StringBuilder 사용) :

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
class Main {
	public String solution(int n, int[] arr) {
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<n-1; i++) {
		    int idxMin = i;
			for(int j=i+1; j<n; j++) {
				if (arr[j] < arr[idxMin]) idxMin = j;
			}
			// swap(arr[i], arr[idxMin])
			int temp = arr[i];
			arr[i] = arr[idxMin];
			arr[idxMin] = temp;
			sb.append(Integer.toString(arr[i])).append(" ");
		}
		sb.append(Integer.toString(arr[n-1]));
		String answer = sb.toString();
		return answer;
	}

	public static void main(String[] args) throws IOException {
		Main T = new Main();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		String k = br.readLine();
		StringTokenizer st = new StringTokenizer(k);
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		} 
		bw.write(T.solution(n, arr));
		bw.flush();
		bw.close();
	}
}

 

음.. 빨라서 좋긴 하지만 당분간은 평범하게 코드 작성해야겠다.

 

 

소스코드 :

import java.util.*;
class Main {
	public int[] solution(int n, int[] arr) {
		for(int i=0; i<n; i++) {
			int minIdx = i;
			for(int j=i+1; j<n; j++) {
				if (arr[minIdx] > arr[j]) minIdx = j;
			}
			// swap
			int tmp = arr[i];
			arr[i] = arr[minIdx];
			arr[minIdx] = tmp;
		}
		return arr;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = sc.nextInt();
		}
		for(int x : T.solution(n, arr)) {
			System.out.print(x+" ");
		}
	}
}

 

 

 

문제 2 :

숫자 n과 해당 n의 갯수만큼 숫자가 주어진다.

해당 숫자들을 오름차순으로 정렬해서 출력하는 프로그램을 작성하여라.

단, 버블 정렬을 이용

ex)

5

2 6 13 5 9

->

2 5 6 9 13

 

버블 정렬이란?

gif 출처 : https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/resources/bubble-sort-001.gif

 

소스코드 :

import java.util.*;
class Main {
	public int[] solution(int n, int[] arr) {
		// n-1만큼 반복
		for(int i=0; i<n-1; i++) {
			// 반복할 때 마다 마지막 자리가 결정되므로 j<n-1-i
			for(int j=0; j<n-1-i; j++) {
				if (arr[j] > arr[j+1]) {
					// swap
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
		return arr;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) arr[i] = sc.nextInt();
		for(int x : T.solution(n, arr)) System.out.print(x+" ");
	}
}

 

 

문제 3 :

숫자 n과 해당 n의 갯수만큼 숫자가 주어진다.

해당 숫자들을 오름차순으로 정렬해서 출력하는 프로그램을 작성하여라.

단, 삽입 정렬을 이용

ex)

5

2 6 13 5 9

->

2 5 6 9 13

 

삽입 정렬이란?

gif 출처 : https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/resources/insertion-sort-001.gif

 

소스코드 :

import java.util.*;
class Main {
	public int[] solution(int n, int[] arr) {
		// i=1 부터 시작
		for(int i=1; i<n; i++) {
			int select = arr[i], j;
			// i-1부터 0까지 역방향으로 진행됨
			for(j=i-1; j>=0; j--) {
				if (arr[j] > select) arr[j+1] = arr[j];
				else break;
			}
			// 끝까지 돌렸거나(j=-1), arr[j]가 select보다 크지 않을 경우 j+1에 select 삽입
			arr[j+1] = select;
		}
		return arr;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) arr[i] = sc.nextInt();
		for(int x : T.solution(n, arr)) System.out.print(x+" ");
	}
}

'Java 코딩테스트 공부 > Java 알고리즘 공부' 카테고리의 다른 글

Java 정렬, 이분검색과 결정알고리즘 3  (0) 2022.11.04
Java 정렬, 이분검색과 결정알고리즘 2  (0) 2022.09.03
Java 스택, 큐 알고리즘5 + deque  (0) 2022.08.20
Java 스택, 큐 알고리즘4 + 빠른 입출력  (0) 2022.08.17
Java 스택, 큐 알고리즘3  (0) 2022.08.16
'Java 코딩테스트 공부/Java 알고리즘 공부' 카테고리의 다른 글
  • Java 정렬, 이분검색과 결정알고리즘 3
  • Java 정렬, 이분검색과 결정알고리즘 2
  • Java 스택, 큐 알고리즘5 + deque
  • Java 스택, 큐 알고리즘4 + 빠른 입출력
daramG
daramG
dotori Java
daramG
다람쥐의 개발 블로그
daramG
전체
오늘
어제
  • 분류 전체보기 (193)
    • Java 코딩테스트 공부 (67)
      • Java 알고리즘 공부 (37)
      • Java 백준 문제풀이 (27)
      • Java 코테 나만의 팁 (3)
    • SQL Study (0)
      • Programmers SQL 문제풀이 (0)
      • SQLP 준비 (0)
    • 웹 개발 지식 정리 (0)
      • Servlet (0)
      • Java 정리 (0)
    • 자바 스프링 (45)
      • 스프링 공부 (4)
      • 스프링 게시판 프로젝트 (6)
      • 부트 블로그 JPA 프로젝트 (30)
      • react & springboot (5)
      • 스프링 오류창고 (0)
      • 리액트 + 스프링 프로젝트 (0)
      • pf (0)
      • pfError (0)
    • React (6)
      • React 정리 (3)
      • React 오류 창고 (3)
    • C++ 코딩테스트 공부 (중단) (20)
      • c++ 백준 문제풀이 (15)
      • c++ 알고리즘 공부 (5)
    • Unity (3)
      • Unity 공부 (3)
    • WebRTC (2)
      • WebRTC 강의학습 정리 (0)
      • WebRTC 프로젝트 (1)
    • 김영한님의 스프링 강의 학습 (10)
      • 스프링 강의 목차 (1)
      • 인텔리제이 & 스프링 기초 (1)
      • 스프링 핵심 원리 (8)
    • 전공 지식 정리 (40)
      • interview (0)
      • Java (0)
      • 운영체제 (4)
      • 데이터베이스 설계 (10)
      • 소프트웨어 공학 (3)
      • 유닉스 (14)
      • 디지털 논리회로 (0)
      • 인공지능 (7)
      • js (0)
      • etc (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Java 백준 문제풀이
  • 스프링 프로젝트
  • java 알고리즘
  • React&Spring 강의수강
  • 운영체제
  • Unity 공부
  • 김영한 스프링 입문
  • 부트 jpa 게시판 프로젝트
  • 김영한 스프링 강의
  • 코테 알고리즘
  • 데이터베이스 설계
  • 스프링부트 블로그 프로젝트
  • java
  • Java 코테 나만의 팁
  • 무서운 이야기
  • 스프링부트 프로젝트
  • 인공지능
  • 김영한의 스프링 핵심 원리
  • 디지털 논리회로
  • 스프링 공부
  • 백준 c++
  • 노마드코더의 zoom클론코딩
  • 유닉스
  • C++ 알고리즘

최근 댓글

최근 글

hELLO · Designed By 정상우.
daramG
Java 정렬, 이분검색과 결정알고리즘 1
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.