PS/BOJ
BOJ 2003 수들의 합 2 [Java]
BOJ 2003 수들의 합2 - 문제 링크 https://www.acmicpc.net/problem/2003 - 문제 해설 전형적인 투포인터 알고리즘을 이용할 수 있는 문제이다. 2중 for문을 이용하면 시간 복잡도가 O(N^2)으로 제한 시간을 맞출 수 없지만, 투 포인터를 이용하면 O(N)으로 시간이 충분하다. 시작점을 가리키는 포인터를 start, 끝 점을 가리키는 포인터를 end, 포인터가 가리키는 두 원소의 합을 sum, 찾고자 하는 경우의 갯수를 cnt라고 하자. 1) 두 원소의 합이 M이면 구하고자 하는 경우를 찾았으니 cnt를 1 더해준다. start가 가리키는 원소의 값을 sum에서 빼주고 start를 1 더해준다. end를 1 더해주고 더해진 end가 가리키는 원소의 값을 sum에 더해..
BOJ 1158 요세푸스 문제 [Java]
BOJ 1158 요세푸스 문제 - 문제 링크 https://www.acmicpc.net/problem/1158 - 문제 해설 ArrayList를 이용하여 풀었다. 제거할 사람의 인덱스가 k만큼 계속 더해진다. 인덱스의 시작이 0이고 처음 제거할 사람의 인덱스는 k-1이므로 인덱스 초기값을 -1로 설정했다. k씩 더하다가 인덱스가 리스트의 마지막 인덱스를 넘어가면 다시 처음 인덱스 값으로 돌아가서 작동해야한다. 이 과정 처리를 나머지(mod) 연산을 이용하여 해결하였다. - 코드 보기 package 큐; import java.io.*; import java.util.*; public class BOJ_1158 { static int n, k; public static void main(String[] ar..
BOJ 1406 에디터 [Java]
BOJ 1406 에디터 - 문제 링크 https://www.acmicpc.net/problem/1406 - 문제 해설 java 내의 LinkedList를 이용하여 풀었다. ListIterator는 Iterator와는 다르게 양방향으로 원소에 접근이 가능하기에 ListIterator를 이용하였다. 18-19줄에서 커서를 맨 뒤로 보내는 작업을 먼저 해주고, 그 후 각 명령이 들어오면 그에 맞게 동작하도록 구현하였다. ListIterator 내부에 현재 보고 있는 위치를 가리키는 cursor가 있어서 메소드를 활용하면 쉽게 해결할 수 있는 문제였다. 문제에서 사용한 메소드들만 정리해보겠다. - hasNext() : iterator가 리스트를 순방향으로 순회할 때 다음 원소가 있으면 true를 없으면 fals..
BOJ 11656 접미사 배열 [Java]
BOJ 11656 접미사 배열 - 문제 링크 https://www.acmicpc.net/problem/11656 - 문제 해설 문자열과 정렬을 이용한 간단한 구현 문제이다. 입력 받을 String을 만들어주고, 앞에서부터 접미사를 한글자씩 뗀 문자열을 담을 String 배열로 ans를 만들어준다. String 클래스의 메소드 substring을 이용하여 글자를 떼어냈다. - 코드 보기 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sy..
BOJ 11655 ROT13 [Java]
BOJ 11655 ROT13 - 문제 링크 https://www.acmicpc.net/problem/11655 - 문제 해설 입력 받은 문자열에서 알파벳 대문자, 소문자의 경우만 13글자씩 밀어서 표현하면 된다. 신경써야하는 부분은 14번째 알파벳 n부터는 13글자를 밀면 z를 지나 다시 a로 돌아가서 밀린다는 것이다. char형 배열 ans을 만들어 입력 받은 문자열을 담았다. 그 후, 문자열을 문자 하나씩 검사하면서 위 내용들을 구현하였다. - 코드 보기 import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(ne..