Algorithm Cinema

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을 활용하는게 편하겠다. 사실 아래 문제는 내가 바로 푼거라 지금 포스팅할때 봐..

1764번: 듣보잡 (acmicpc.net) 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 중복을 다루는 문제이다. 주어진 두번의 문자열들의 집합에서 , 중복되는걸 찾아서 사전순으로 return하라는 문제다. 중복을 다루니까 map을 활용하면 편하겠고 사전순으로 return.. > sort해야겠다는 생각 n.m의 max가 50만이니, 정렬할때 nlogn짜리 sort()메소드 활용. 이 정도의 아이디어만 있으면 쉽게 풀리겠다 ! 추가적인 tip이지만 Map.containsKey()의 시간복잡도는 평균적으로 ..

11478번: 서로 다른 부분 문자열의 개수 (acmicpc.net) 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 아주 직관적이며 쉬운 문제다. >> 부분 문자열 영어로 하면 substring.. 자바에 substring()이라는 메소드가 있다 허허.. 그걸 써서 어느 자료구조에다 넣느냐가 문제인데, 부분 문자열에 불가피하게 중복이 생기기 때문에 map 구조를 활용하여 중복을 다루는것이 가장 현명해보인다. map을 생성해서 값을 put했다면 entry로 한바퀴 돌며 중복된값있나 체크하고 있다면 그 값을 1로 replace()해준다면 바로 문제가 풀린다. 여기서 point는 s..

1620번: 나는야 포켓몬 마스터 이다솜 (acmicpc.net) 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 다솜이가 포켓몬을 참 좋아하는갑다. 문제를 상당히 정성스럽게 만드셨다. 일단 문제를 보자마자 map을 만들어야겠다는 생각을했고 문제의 조건은 input값이 String일때 (포켓몬이름) 포켓몬 번호를 출력하고 input값이 Integer일때 (포켓몬 번호)일때 포켓몬 이름을 출력하라고 했다. 일반적으로 map을 사용할때, key > value를 얻는건 매우쉽다. 그냥 ..