Algorithm Cinema

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를 얻는건 매우쉽다. 그냥 ..

18870번: 좌표 압축 (acmicpc.net) 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 주어진 정수들의 Ranking을 매기는 문제이다. 적절한 자료구조를 활용해야겠다는 생각을 처음에 못하고 일단 정렬된 배열과 원본 배열을 만들어놓고, 이진탐색을 해보자.라는 생각을 했다. (시간제한이 빡세서) 일단 첫번째 정렬된 배열을 만들자. > 이건 좋은 아이디어. 애사당초에 ranking을 할때 정렬된 배열 하나는 꼭 있어야한다. 시간제한이 있으니 nlogn짜..

11650번: 좌표 정렬하기 (acmicpc.net) 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 이 문제는 2차원 좌표평면의 좌표들의 순서를 정렬하는 문제이다. 첫번째 최우선의 정렬 기준은 x좌표 증가 순, 그리고 x좌표가 같다면 y좌표가 증가하는 순서로 정렬을 하는 것이다. 일단 나의 첫번째 시도는 x좌표 따로, y좌표 따로 , 그 다음 이 두 x,y를 합친 배열 따로 총 3가지 배열을 다뤄보자하였다. 고민을 계속하다 보니 xy 좌표 를 따로 배열로 ..

두 정렬 모두 시간복잡도가 o(n^2)라 느리긴 하지만, 배워두면 쓸데가 있지 않을까 하고 포스팅해본다. 배열은 9 2 4 5 3 . 크기 5짜리라고 가정하자 1. 선택정렬 선택정렬의 컨셉은 간단히 말하면 최솟값을 0번째 인덱스에 집어 넣는다 생각해야한다. 첫번째 loop부터 살펴보자. i=0 & j = 1,2,3,4 i=0일때, minindex=0이겠다. 여기서 j=1,2,3,4로 움직이면서 첫번째 인덱스보다 다음인덱스가 작다면 minindex를 초기화하고 이를 j = 1,2,3,4 다 돌면 최종적으로 최소값을 지닌 인덱스가 나올 것이다. minindex = 1이라는 결론이 나오고. temp > arr[1] , arr[1] > arr[0] , arr[0] > temp( 즉 temp는 여기서 최솟값이겠다..