Algorithm Cinema

17299번: 오등큰수 (acmicpc.net) 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미. 1. 카운팅 배열 일단 빈도수체크를 해야하는 점. 여기서 카운팅 배열을 하나 만들어 아이디어를 떠오르는 게 좋겠다. (수의 max range가 100만이니 100만+1짜를 만든다.) 그래서 input을 받고나면 정수 값마다의 인덱스에 자신들의 빈도수가 체크가 되겠다. 2. 스택 스택을 쓰는 근거는 최신 업데이트를 필..

17298번: 오큰수 (acmicpc.net) 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4,..

10799번: 쇠막대기 (acmicpc.net) 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 닫는 괄호와 여는 괄호를 중심으로 문제를 해결해야하는 문제. - 이 괄호 꺾쇠를 보면 이젠 습관적으로 스택을 떠올리게 된다. 이 문제 역시 스택으로 풀었어야했다. 난 처음에 어느 괄호를 기준으로 잡아야할지 감이 안와서 잘 못 풀었었다. 뭐 크게 경우는 두가지 이지만, 연속될 경우를 잘봐야 한다. 접근. 1. (( / () / )) / )( / 총 4가지의 연속경우가 있으니 이를 잘 참고해야겠다. ()인 경우 레이저를 표시하기에..

17413번: 단어 뒤집기 2 (acmicpc.net) 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 있다. 문자열의 시작과 끝은 공백이 아니다. ''가 문자열에 있는 경우 번갈아가면서 등장하며, ''일때 닫는 꺾쇠이기에, tag type > false & >도 ..

1158번: 요세푸스 문제 (acmicpc.net) 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)- 요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램. 1. 원을 이루면서 앉..

1406번: 에디터 (acmicpc.net) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 명령어 4가지를 통해 문자열을 control해보는 문제. 커서를 활용하는 특이한 문제다. 특이한 점은 시간제한이 빡세다 0.3초.. 첫번째 접근. 그냥 stringBuilder와 인덱싱 활용해서 풀기, - 답은 맞게나오나, 성능이 o(n)으로 낫배드나, 0.3초라 시간제한에 걸렸다 두번째 접근 커서 활용 >> LinkedList의 ListIterator로 문제 해결하기. 얘는 시간제한에 안걸리고 풀었다 iterator의..

1874번: 스택 수열 (acmicpc.net) 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net input되는 숫자의 갯수와 그 숫자들로 순서대로 수열을 하나 만들고, 그 숫자 오름차순으로 스택에다가 push를 하며 중간중간 pop을 하며 이 수열을 만들 수 있는가? 를 묻는 문제이다. 문제가 약간 어렵게 느껴질수도 있는데, 예제 1을 보면, 8 > 4 3 6 8 7 5 2 1 순으로 수열이 나열되어있다. 하지만 오름차순으로 p..

2346번: 풍선 터뜨리기 (acmicpc.net) 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다. 예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 ..

11478번: 서로 다른 부분 문자열의 개수 (acmicpc.net) 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 부분 문자열의 갯수를 출력하는 문제이다. 예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다. 즉 어떠한 문자열의 부분문자열들은 서로 겹치는게 분명히 존재하겠다. 겹치지 않는 부분문자열의 가짓수. 일단 겹치지 않는 조건중에 가장 잘 보이는건 글자의 갯수겠다. 사실 부분문자열을 영어로 해석하면 substring이다. 하지만 ..

1269번: 대칭 차집합 (acmicpc.net) 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 차집합에 관한 문제. 두가지 포인트를 보면 된다. 1. a-b 이땐 a의 집합에서 b의 집합이 겹칠경우 그 부분만 제외한다. 즉 a집합이 point이며, a-b집합은 a집합보다 클수없다. 2. b-a 위와 똑같지만 point가 b 즉 각각 중복된 요소를 찾아서 a집합, b집합에 겹친 부분집합을 뺴준다. 중복된 요소를 다루니 map을 활용하는게 편하겠다. 사실 아래 문제는 내가 바로 푼거라 지금 포스팅할때 봐..