PS/BOJ
BOJ 10799 쇠막대기 [Java]
BOJ 10799 쇠막대기 - 문제 링크 https://www.acmicpc.net/problem/10799 - 문제 해설 '('가 입력으로 들어오면 쇠막대기나 레이저가 하나 추가된다는 의미이므로 스택에 '('를 쌓는다. ')'가 입력으로 들어오는 경우가 중요하다. ')'가 입력으로 왔을 경우는 2가지로 나눌 수 있다. 레이저이거나, 쇠막대기의 끝 점이다. 레이저인 경우 스택에 쌓인 쇠막대기의 수만큼 조각이 생긴다. 쇠막대기의 끝 점인 경우 조각이 1개가 추가된다. cnt는 조각의 수이고, 레이저를 판별하기 위해 입력을 배열에 담았다. - 코드 보기 import java.io.*; import java.util.Stack; public class ..
BOJ 9012 괄호 [Java]
BOJ 9012 괄호 - 문제 링크 https://www.acmicpc.net/problem/9012 - 문제 해설 VPS가 아닌 경우는 어떤 경우가 있을지를 생각해보자. 짝이 되는 ')'가 없어 '('이 남는 경우 짝이 되는 '(' 없이 ')'이 먼저 입력되는 경우 '('가 입력될 때마다 '('를 스택에 담아주고, ')'가 입력되면 스택의 최상단에 있는 '('를 pop해주는 방식으로 동작하게 한다. 그렇게 구현하였을 경우 과정이 끝났을 때, 스택이 비어있지 않으면 1의 경우이다. 스택이 비어있을 때, ')'가 들어오는 경우가 2의 경우이다. 위 내용을 바탕으로 코드를 구현하였..
BOJ 10828 스택 [Java]
BOJ 10828 스택 - 문제 링크 https://www.acmicpc.net/problem/10828 - 문제 해설 자바의 util.Stack을 이용하여 풀면 쉽게 풀 수 있지만, 직접 스택을 구현하여 풀었다. tail은 스택 제일 상단 원소의 인덱스 값이다. 구현하는 데 있어 딱히 어려운 점은 없고 자료형의 변환에만 신경써주면서 구현하면 된다. 한 가지 시행착오를 겪은 것이 있다면, 처음에 코드를 짤 때는 st.nextToken()을 받아줄 변수를 만들지 않았다. 예를 들자면, 아래의 67번째 줄의 코드를 if(st.nextToken().equals("push"))와 같이 짰다. 나머지 else if문들도 똑같이 작성하였다. 이렇게 구현을 하니 내가 얻고자 하는 값이 나오지 않았다. StringTo..
BOJ 11004 K번째 수 [Java]
BOJ 11004 K번째 수 - 문제 링크 https://www.acmicpc.net/problem/11004 - 문제 해설 메모리와 시간 제한이 여유로워서 sort 메소드를 이용하여 쉽게 풀 수 있는 문제이다. sort 메소드말고 다른 방식으로 풀 경우 quick sort를 이용해서 풀 수도 있을 것 같다. 이 문제를 풀면서 처음에 한 가지 간과한게 있다면, BufferedReader와 StringTokenizer를 이용하여 한 줄씩 입력 받아 토큰으로 만들었기때문에, 18줄의 코드처럼 StringTokenizer를 한 줄마다 다시 만들어줄 필요가 있다. - 코드 보기 import java.io.*; import java.util.*; public class Main { static int n; sta..
BOJ 10989 수 정렬하기 3 [Java]
BOJ 10989 수 정렬하기 3 - 문제 링크 https://www.acmicpc.net/problem/10989 - 문제 해설 N이 10,000,000 이하의 자연수이기 때문에 sort를 쓰면 메모리 초과가 난다는 사실을 인지해야한다. 정렬해야하는 숫자들이 10,000 이하라는 사실에서 counting sort를 쓰면 되겠다는 힌트를 얻었다. cnt[i]를 1-10000 범위의 자연수 i가 입력된 횟수라고 설정하고 구현해주면 된다. 출력할 때는 cnt[i] > 0 이 아닌 경우에는 i가 입력되지 않은 경우이니 제외한다. - 코드 보기 import java.io.*; public class Main { static int n; public static void main(String[] args) thr..