Junior-Developer

1일 1커밋! 1일 1 백준!

문제풀이/프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/43165?language=java 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 풀이 DFS를 이용해서 문제를 해결했다. 첫번째 원소부터 마지막 원소까지 탐색을 하면서, 해당 원소를 덧셈했을때와 뺄셈했을때의 경우를 모두 구해준 뒤, 마지막 원소까지 탐색을 했고 그 경우에 target과 같다면 answer를 +1 해준다. 시간복잡도 숫자의 개수는 2~20개 이고, ..

2021. 11. 19.

문제풀이/백준oj

https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 풀이 말을 살짝 바꿔서 잘라야되는 전깃줄을 구하는것이아닌, 자르지 않아도되는 전깃줄의 최대값을 구해준다고 생각을 하면 쉽게된다. 그럼 여기서 자르지않아도 되는 전깃줄의 최대값은 어떻게 구해줄까? 방법은 바로 증가하는 수열의 최대길이를 구해주면된다. 이를 위해 Lower_bound함수를 구현해준 뒤, 자르지않아도 되는 전깃줄의 최대값을 구해주어 N에서 빼주면 답이 나온다. 시간복잡도 ..

2021. 11. 7.

문제풀이/백준oj

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 2번째줄에 사자를 놓는 경우를 생각해보자 왼쪽에 놓기 위해서는, 1번째줄에 사자가 오른쪽에 있거나 1번째줄에 사자가 없어야한다. 오른쪽에 놓기 위해서는, 1번째줄에 사자가 왼쪽에 있거나 1번째줄에 사자가 없어야한다. 놓지 않기위해서는, 1번째줄에 사자가 왼쪽,오른쪽,없는 3가지 경우 모두 가능하게된다. 위를 일반화 하면 다음과 같다. i번째줄의 왼쪽에 놓기위해서는 i-1번째 줄의 오른쪽에 사자가 있거나, i-1번째 줄에 사자가 없다. i번째줄의 오른쪽에 놓기위해서는 i-1번째 줄의 왼쪽에 사자가 있거나, i-1번째 줄에 사자..

2021. 11. 7.

문제풀이/백준oj

https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 풀이 먼저 N명의 정보를 입력받은다음에, 모두를 조건에 맞게 비교를 했다. 이때 compareTo메소드를 오버라이딩해서 height와 weight값 모두가 자신보다 큰 경우를 추가시켜주어서 문제를 해결했다. 시간복잡도 이중for문으로 해결이 가능하기때문에 O(N2)이 된다. 코드 import java.util.*; public class Main { static Vector v=new..

2021. 11. 5.

문제풀이/백준oj

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 현재까지 나온 문자열인지 확인을하는 Map을 이용해서 나온적이 없는 문자열이면 벡터에 add한 뒤, 정렬기준을 문자열의 길이가 작은순, 같다면 사전적으로 먼저오는순으로 정렬을 한다. 코드 import java.util.*; public class Main { static Vector v=new Vector(); static Map check=new HashMap(); static ..

2021. 11. 4.

문제풀이/백준oj

https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 풀이 A문자열을 B문자열과 겹쳐가면서 문제를 해결하면된다. 예를들어서 A=adaabc , B=aababbc라고 해보자. 먼저 A의 첫번째 문자를 B의 첫번째 문자와 겹쳐본다. A a d a a b c B a a b a b b c 그럼 A의 맨 마지막에는 빈칸이 되는데, 길이를 맞추기위해 아무 알파벳이나 추가해도 된다했으므로, A와B의 길이를 최소로 하기위해서..

2021. 11. 2.

문제풀이/백준oj

https://www.acmicpc.net/problem/2920 2920번: 음계 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8 www.acmicpc.net 풀이 먼저 해당음계들을 인덱스에 맞춰서 저장을 해준뒤, 입력받는 숫자에 맞는 음계를 String에 추가해준다. 모두 추가해준뒤, asc에 맞는 "cdefgabC"와 일치한다면 ascending을, desc에 맞는 "Cbagfedc"와 일치한다면 descending을 출력해준다. 만약 맞는게 없다면 mixed를 출력해준다. 시간복잡도 8번의 입력과 길이가 8..

2021. 11. 1.

문제풀이/프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 풀이 1. 자동차가 나가는 지점을 기준으로 오름차순으로 정렬을 한다. 2. 정렬후 첫번째 자동차가 나간 지점을 checkPoint(카메라 지점)로 설정을 한다. 3. 다음 자동차를 탐색하면서, 이 자동차가 checkPoint에 포함이 되어있으면 만난다는 뜻이므로 넘겨준다 4. 만약 checkPoint에 포함이 되지않는다면, 즉 이전에 설치한 카메라에 걸리지 않는다면 새로운 카메라를 나가는 지점에 설치해준 뒤, 카메라의 개수를 갱신해준다. 시간복잡도 routes의 개..

2021. 11. 1.