전체 글
-
[BOJ-JAVA] 17298번: 오큰수Algorithm/Baekjoon Online Judge 2023. 4. 17. 16:57
문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 수열에 주어질 때 각 인덱스를 기준으로 가장 오른쪽에 있는 인덱스의 수보다 큰 수를 찾는 문제이다. 문제 풀이 2차원 배열을 사용해서 푸는게 가장 쉬운 방식이지만 시간초과가 날 것이기 때문에 자료구조를 적절히 활용해야한다. stack을 사용해 문제를 해결하는 것까지는 확인을 했지만 stack을 어떻게 활용해야하는지 고민했던 문제이다. 초반에는 수열의 뒤에서부터 확인하며 오큰수를 찾는 방법을 구하려 했지..
-
[BOJ-JAVA] 10799번: 쇠막대기Algorithm/Baekjoon Online Judge 2023. 4. 17. 15:07
문제 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 다음과 같이 괄호로 이루어진 문장이 주어질 때 막대기의 개수를 세는 문제이다. 괄호는 레이저를 나타낸다. 괄호 안에 포함된 가장 안쪽 괄호가 레이저가 된다. 모든 막대기는 괄호를 포함한다. 막대기에 대해 가장 안쪽 괄호 기준으로 나누었을 때 막대기 개수를 구해야한다. 문제 풀이 보통의 괄호를 이용한 문제는 stack을 이용해 해결할 수 있다. "("가 나올 경우 stack에 push ")"가 나올 경우..
-
[BOJ-JAVA] 1158번: 요세푸스 문제Algorithm/Baekjoon Online Judge 2023. 4. 12. 20:48
문제 해결 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 큐를 이용해 쉽게 구현할 수 있는 문제지만, 초기에는 연결리스트만을 사용하여 구현하였고, 이후에 다시 큐를 사용해 구현하였다. 연결리스트 사용 iterator를 사용하여 K번째 마다 remove iterator가 끝을 가르킬 때 다시 정의해줘야 하는 번거로움이 있음 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Iterator; ..
-
[BOJ-JAVA] 1406번: 에디터Algorithm/Baekjoon Online Judge 2023. 4. 7. 15:48
문제 해결 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 연결리스트 사용 커서를 사용하여 이동하며 삽입, 삭제 등의 행동을 하기 때문에 연결리스트로 초기 구현했다. 하지만 시간초과가 발생! System.out.print 부분을 StringBuilder로 변경해줬지만 역시나 시간초과 cursor라는 변수를 두어 삽입, 삭제를 진행하는데 연결리스트는 처음부터 노드를 하나씩 살피기 때문에 시간이 오래걸리는 것 같아, iterator를 사용해보기로함 ..
-
[BOJ-JAVA] 10828번: 스택Algorithm/Baekjoon Online Judge 2023. 4. 6. 14:21
문제풀이 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 스택 개념만 알고있다면 문제 자체는 어렵지 않지만 초기 작성한 코드와 이를 개선시키면서 어떻게 작성해야 효율적인지 고민했다. 초기 Java 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; class ..