연습문제/JAVA (66) 썸네일형 리스트형 [백준 java] 10845 - 큐 바로 전 문제 스택과 거의 같은 문제이다. 스택에서는 그냥 스택을 사용하여 풀었는데 이번에는 직접 큐 처럼 동작하는 배열을 만들어서 구현했다. 큐는 선입선출이므로 먼저 들어온 값을 삭제한다. 여기서는 직접 삭제하지 않고 보여줄 부분을 변경 우선 배열의 보여줄 부분 시작점 start , 끝점 last 으로 두고 push 시 배열의 last 인덱스에 추가후 last를 ++ pop 에는 직접 삭제를 하지말고 큐의 last인덱스를 보여주고 보여줄 start를 ++한다. size 해당 큐의 크기는 last- start 이다 (배열을 직접 삭제하지않고 보여주는 부분만 바꿨기때문) empty start back 은 사이즈에 따라, 즉 last-start 이 0인지 아닌지에 출력을 바꿔준다. import java.io.. [백준 java] 10828 - 스택 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 블로그 - 전체 글 여러가지 언어와 입력 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다. 방법: 첫째 줄에 정수의 개수 N (= 10,000,000), 둘째 줄부터 N개의 줄에 한 개의 자연수(10,000 이하)가 적힌 파일 www.acmicpc.net 위 블로그에서 입력속도 비교글을 한눈에 볼 수 있다. BufferReader로 입력을받고 "push 정수" 를 스페이스바로 구분하기위해 StringTokenizer를 사용하였다 출력은 .. [백준 java] 9935 - 문자열 폭발 진짜 폭발시키고 싶은 문제 String replace를 사용하면 O(N^2) 번의 시간복잡도가 발생하므로 Stack을 사용하는 방법으로 풀어야한다. (문자열 탐색후 지우고 다시 처음부터 탐색하기 때문) 폭발 문자열 = B 1. 입력값을 char[]로 받은 후 스택에 처음부터 하나씩 넣는다 2. 만약 스택 사이즈가 B보다 크다면 3. 스택에 넣은 값에 B의 길이만큼 뺀 값과 B를 한글자씩 for문으로 비교한다 4. 만약 explosion = true 라면 B의 길이만큼 스택에서 버린다. (선입선출) 계산 후 for문을 사용하여 값을 출력했는데 여기서 또 시간초과가 발생했다 for문을 사용하여 출력할때도 O(N^2) 번의 시간복잡도가 발생해서 그렇다 시간 복잡도, 입출력 시간복잡도, 입출력 velog.io .. [백준 java] 1717 - 집합의 표현 (Union-find) 집합의 수는 0을 포함한 N+1 개의 집합을 가진다. Union-find 알고리즘을 사용하여 문제를 해결했다. 합집합 찾기라는 의미를 가진 알고리즘으로, 두 개의 노드를 집어 두 노드가 같은 그래프에 속하는지 판별한다. Find 는 입력한 수가 어떤 집합에 포함되어있는지 부모를 찾아준다 (재귀함수를 사용하여 부모를 찾을때까지 타고 올라간다) Union 은 두 수 a와 b가 포함되어 있는 집합을 합쳐준다. 두 값을 비교하여 더 작은 값의 부모노드로 합쳐준다 부모가 p[1] = 1 과 p[2] = 2인 노드를 합치면 p[2] = 1로 연결되며 더 작은 1번노드를 가리키게 된다 for문으로 M개의 입력(m,a,b)을 받으며 첫번째 숫자의 m이 0이면 a,b를 union 첫번째 숫자m이 1이면 a,b를 각각 f.. 1717-집합의 표현 (오답) 1. M(연산의 수)이 10만개이므로 2중 for문을 사용하여 리스트를 합쳐주는것은 O(N^2)시간이 걸린다. 2. 집합의 수가 1~100만개지 집합 수의 범위가 1~100만이 아니기때문에 0도 포함되어야한다 (0을 포함안시키고 수행) 시간복잡도를 다시한번 생각해보고 다른 방법을 찾아봐야겠다 import java.util.*; public class B1717 { static int N,M,p,a,b; static ArrayList Board; public static void main(String[] args) { Scanner sc= new Scanner(System.in); N = sc.nextInt(); M = sc.nextInt(); Board = new ArrayList(); for(int i.. [백준 java] 5430 - AC 실제로 문자열을 뒤집으면 시간초과가 난다. 따라서 boolean형 변수 Reverse를 선언하고 만약 R이 들어오면 reverse != reverse 로 변경해주자 밑 코드는 for문마다 결과값을 ArrayList에 저장해야해서 마지막에 배열을 뒤집어서 저장했다 import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class B5430 { static ArrayList intArr = new ArrayList(); static ArrayList resArr = new ArrayList(); static boolean reverse; static char[] charArr; public static.. [백준 java] 3190-뱀 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 사과는 : 1, 그냥길은 :0 * 주의할점 * 1. 뱀이 사과를 먹으면 Board의 1(사과) 을 0으로 바꿔줘야한다. 2. X초가 끝난 뒤에 (뱀이 움직이고 난 후) 방향을 움직여아한다 3. for문을 통해 자기자신과 만났는지 확인하고 break로 전체 while문을 빠져나와야 한다 뱀의 길이와 위치를 알기위해 snake 큐를 만들었다 q에 이동할 곳을 넣어주고 만약 사과를 먹었다면 Board의 사과만 0으로 없애주고 만약 사과를 먹지 않았다면 큐를 삭제하여 제일 이.. [백준 java] 9012-괄호 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net (괄호는 1 )괄호는 -1로 바꾸고 순서대로 더한다(int sum). 만약 sum이 음수가 된다면 바로 실패처리 후 NO 최종으로 더한 값이 0이 나온다면 YES를 출력한다 import java.util.Scanner; public class B9012 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt();.. 이전 1 2 3 4 5 6 7 ··· 9 다음
