PS(Java)/백준
[PS] 백준 11652번 카드
문제 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 풀이 다뤄야 할 데이터, N의 최대 개수는 십만개이지만, 카드에 입력될 수 있는 수의 범위는 -2의 62승~ 2의 62승이므로 long타입 배열을 선언한다. 카드배열에 수를 입력받은 뒤 가장 많은 개수의 카드의 값을 출력하는 문제이다. 주의할 점은 가장 많은 개수의 카드가 여러종류일 경우 카드의 숫자가 더 작은 것을 출력한다는 점이다. 생각해보면 두 가지 방법이 있다. 방법1) Arrays.sort로 오름차순 정렬을 한 뒤 카드 개수를 카운트하기 방법2..
[PS] 백준 10989번 수 정렬하기 3
문제 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 ※ 주의 1
[PS] 백준 10825번 국영수
문제 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 풀이 compare 함수에서 내림차순 정렬하고 싶을 때는 로직을 반대로 짜면 될 것 같았는데 내 예상이 맞았다. String을 사전 순으로 정렬해야하는데 방법이 여러가지 일 것 같아서 찾아봤다. String을 사전 순 정렬 하는 방법(참고한 글) stringArraySort() compareTo() Arrays.sort() -> 기본적으로 사전순 정렬된다. String 두 개를 비교 해야하기 때문에 compareTo 메서드를 사용했다. ..
[PS] 백준 10814번 나이 순 정렬
문제 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 풀이 방법이 다양할 것 같아서 고민을 하다가 클래스를 사용하기로 했다. 참고한 풀이 방법 1. String[][] 사용해서 Arrays.sort , Comarator 사용 2. Calss에 변수 2개 넣어서 Arrays.sort 확장하여 정렬 3. StringBuilder를 배열처럼 사용하여 Counting sort 형태로 사용 코드 import java.util.Arrays; import java.util.Comparator; import java.util.Sc..
[PS] 백준 11650번 좌표 정렬하기(Comparable과 Comparator)
문제 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 풀이 참고한 풀이 Arrays.sort()는 2차원 배열의 정렬을 할 수 X →람다식을 사용하여 Arrays.sort() 확장 일회성으로 함수를 써야할 경우 람다식으로 구현하는 것이 좋음 Comparator 의 경우 람다식으로 표현 할 수 있다 우선순위를 사용자화 compare 메소드를 오버라이딩하여 비교 방법(우선순위 판단)을 구현 https://st-lab.tistory.com/243 Arrays.so..
[PS] 백준 2751번 수 정렬하기 2
문제 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 참고한 풀이 N(1 ≤ N ≤ 1,000,000) 라는 점 주의. 최악의 경우에도 O(nlogn) 을 보장하거나 혹은, O(n) 에 가까운 정렬 알고리즘을 사용해야 한다(Arrays.sort 로 쓰면 시간초과됨) 1. Collections.sort() 사용 : 병합(최악) + 삽입(최선) hybrid sorting algorithm. O(n) ~ O(nlogn) 을 보장 2. Counting sort 사용 1번 방법을 사용해보았다.정처기 준..
[PS] 백준 2579번 계단 오르기
문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 참고한 풀이 앞으로는 PS 문제 푸는 방식을 바꿔보려한다. 문제풀이법이나 다양한 알고리즘에 익숙하지 않은 상태에서 문제를 풀려다 보니 시간이 오래걸리고, 해답을 보더라도 이해하는데 시간이 걸린다. 학창시절 수학을 잘 못하고, 싫어했던 이유 중에 하나가 안풀리는 문제가 있으면 몇시간이고 끙끙 대면서 붙잡고 있기 때문이었는데 지금 똑같은 상황을 겪고 있다 ㅎㅎ... 앞으로는 우선 문제에 대해서 10분간만 생각해보고 바로 해답을 보면서 풀어야겠다. 코드 import j..