PS(Java)/백준

[PS] 백준 1158번 요세푸스

문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이 큐를 이용하여 풀었음 코드 import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); Strin..

[PS] 백준 1406번 에디터 (다시 풀기)

문제 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 L : B :커서 왼쪽 문자 삭제 P : 커서 왼쪽에 문자 추가 입력: 길이 N인 영어 소문자로 이루어진 문자열 명령어개수 명령어 출력: 편집된 문자열 처음 풀었던 방법: |ㅇ|ㅇ|ㅇ|ㅇ| 길이가 4면 5 가지 경우 0 1 2 3 4 (커서가 맨 마지막오른쪽, 값은 길이와 같음) |ㅇ 이상태를 기본으로 둔다. StringBuilder를 사용하여 풀었는데, StringBuilder 사용시 원래 문자열 String은 변하지 않는 것을 유의하여야 한다. 이 ..

[PS] 백준 1388번 바닥 장식

문제 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net 풀이 세로길이 n, 가로길이 m 인 방에 다음 두 가지 판자를 깐다. (n,m

[PS] 백준 11655번 ROT13

문제 11655번: ROT13 첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다. www.acmicpc.net 풀이 알파벳을 13글자씩 밀어서 출력하면 되는데, 알파벳은 26글자 이므로 14번째 글자 부터는 A(a)부터 다시 돌아가서 출력하면 된다. x+13

[PS] 백준 10799번 쇠막대기

문제 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 풀이 스택을 사용하여 풀었다. 기본적으로 )는 무조건 push하고, )일 때 스택을 pop한다. stack.size로 잘린 막대 개수를 카운트한다. 1. (가 들어옴 → stack.push 2. )가 들어옴 → 일단 stack.pop을 하고 charAt(i-1) 확인 ( )이면 레이저로 잘린 것이므로 piece += stack.size ) )이면 막대하나의 끝이므로 앞에 (를 하나 없앰 piece++; 코드 import java.io.BufferedReader; imp..

[PS] 백준 10828번 스택

문제 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 참고한 풀이 참고글: 자바 컬렉션 프레임워크 참고글: stack interface 스택 문제 풀려다가 자바 컬렉션 인터페이스를 공부하게 생긴... 문제 자체는 쉬우나 이번에는 위 글들을 읽으며 자바 컬렉션에 대해 다시 공부했다. Stack 라이브러리는 'Vector' 클래스를 상속받아 구현하고 있다. Vector 클래스는 기본적으로 'ArrayList'와 그 구조가 거의 같다. Stack 클래스는 내부에서 최상위 타입 배열인 Objec..

[PS] 백준 11004번 K번째 수

문제 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 퀵소트 참고글 참고한 풀이1 참고한 풀이2 Quick Sort 퀵소트는 partition 메서드를 중심으로 재귀호출하는 방식으로 구현된다. pivot의 자리가 선택(partition 메서드 한 번 실행)된 후 부분집합으로 계속 쪼개져 정렬하는 분할 정복 방식 정렬 알고리즘 pivot을 기준으로 작은 수들은 pivot의 왼쪽, 큰 수들은 오른쪽에 배치 이 과정을 재귀적으로 반복하면 모든 수가 정렬이 된다 pivot을 선택하는 방법에 따라 처리속도가 달라진다 첫번째 요소 / 중간 요소 / 마지막 요소 / 랜덤..