지구정복

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net -문제해설 먼저 입력 좌표값들을 배열에 저장하고 이 배열을 복사한다. 복사된 배열을 오름차순으로 정렬한다. 그리고 정렬된 배열을 순회하면서 해시맵에 넣어준다. 이때 키는 정렬된 배열의 값이 들어가고 값으로는 좌표압축값인 idx가 들어간다. 또한 무작정 집어넣는 것이 아니라 해시맵에 똑같은 키가 있을 경우엔 건너뛰게 된다. -자바 package so..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net -문제해설 DP의 기본적인 문제인 것 같다. 단순히 피보나치 값을 구하는 것이 아니라 특정 피보나치 수의 1의 개수와 0의 개수를 구하는 문제이다. 2차원배열을 선언해서 0번 인덱스에는 0의 개수, 1번 인덱스에는 1의 개수를 집어넣고 dp[i][0] = dp[i-1][0] + dp[i-2][0] dp[i][1] = dp[i-1][1] + dp[i-2][1] 점화식을 통해 n행의 배열값을 출력하면 정답이다. -자바 package dp; import java.io.BufferedReader; i..

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net -문제해설 해시맵을 이용하면 간단하게 풀 수 있는 문제이다. 키에 사이트주소, 값에 비밀번호를 삽입하고 비밀번호를 알고 싶은 사이트 주소가 입력되면 StringBuffer에 키인 사이트 주소에 해당되는 비밀번호를 저장해주고 마지막에 StringBuffer를 출력하면 정답이다. 파이썬의 경우 딕셔너리 구조를 이용해서 키, 값을 삽입했다. -자바 package dataS..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net -문제해설 문제는 듣도못한 사람과 보도못한 사람이 겹치는 사람의 수와 이름을 출력하는 것이다. 듣도못한 사람이 3 홍길동 김길동 박길동 보도못한 사람이 4 홍길동 박길동 이길동 정길동 이라고하면 이름은 사전순으로 출력해야 하므로 2 박길동 홍길동 이 된다. 이를 위해 처음에 해시맵 hs1에 ( 키: 이름, 값: 1 ) 로 듣도못한 사람들을 삽입한다. 그리고 arr ArrayList를 만들고 보도..