전체 글
BOJ 18808 스티커 붙이기 [Java]
BOJ 18808 스티커 붙이기 1. 문제 링크 https://www.acmicpc.net/problem/18808 2. 문제 해설 구현 문제이다. 문제를 해결하기위해 구현해야하는 기능은 2개이다. 1. 스티커를 붙일 수 있으면 스티커를 붙이기 2. 스티커를 회전한다. 1번 기능을 구현하기 위해 2가지 메서드를 만들었다. 스티커를 노트북에 붙일 수 있는지 확인하는 isPossible 메서드와 스티커를 노트북에 붙이는 attach 메서드이다. isPossible 메서드는 매개변수로 스티커를 붙이는 노트북의 맨 왼쪽 상단 위치를 받는다. 노트북의 격자에 스티커가 이미 붙어있는 상황에서 스티커를 붙여야 할 때만 스티커를 붙이지 못하므로 false를 리턴해주고 나머지 상황에서는 true를 리턴해준다. attac..
BOJ 2623 음악프로그램 [Java]
BOJ 2623 음악프로그램 1. 문제 링크 https://www.acmicpc.net/problem/2623 2. 문제 해설 pd들이 정한 조건에 따라 가수 순서가 정해지고 그에 맞춰 정렬을 해줘야하는 문제이다. 위상정렬이 떠올랐다. 위상정렬에 대해 알고 싶다면 아래의 글을 참고해보자. 위상 정렬(Topological sorting) [Java] 문제에서 주어진 예시를 아래 그림으로 한번 나타내보았다. 사이클이 있으면 위상정렬을 할 수가 없는데, 문제에서 세번째 pd가 정해준 순서 2->3이 3->2로 바뀐다고 했을 때 불가능하다고 한 이유가 사이클이 생기기 때문이다. 코드에 대한 설명을 해보자면, indeg 배열은 각 정점들에 들어오는 간선의 수를 담은 배열이고, arr에 인접리스트 방식으로 그래프를..
BOJ 1182 부분수열의 합 [Java]
BOJ 1182 부분수열의 합 1. 문제 링크 https://www.acmicpc.net/problem/1182 2. 문제 해설 재귀를 이용해서 풀었다. 각 원소마다 더할 것인지 더하지 않을 것인지를 선택할 수 있고 그에 따라 재귀 함수가 계속 호출된다. 그러므로 시간복잡도는 O(2^n)이다. 최악의 경우에 n이 20이기에 주어진 시간 안에 충분히 해결할 수 있다. 재귀 함수의 매개 변수로 idx와 sum을 주어 현재 몇번째 idx에 위치해있고, 더한 값이 얼마인지를 담았다. 재귀 함수의 탈출 조건은 idx가 n과 같아지면 탈출하고, 만약 sum이 s와 일치하면 경우의 수 값 cnt를 +1 해준다. 문제 조건에서 부분수열의 크기가 양수여야하는 조건이 있으므로 만약 s가 0이라면 아무 것도 더해주지 않은 ..
BOJ 11659 구간 합 구하기 4 [Java]
BOJ 11659 구간 합 구하기 4 1. 문제 링크 https://www.acmicpc.net/problem/11659 2. 문제 해설 가장 쉽게 생각할 수 있는 방법은 그냥 더해주는 것이다. 근데 이 방법은 시간복잡도가 O(nxm)으로 굉장히 느리기 때문에 다른 방식을 생각해보자. 다른 방법으로는 구간합을 이용한 방법을 떠올릴 수 있다. 특정 구간까지의 합을 저장해둔 배열을 이용하는 방식이다. sum[i]는 처음부터 i개의 원소를 합한 값이다. 즉, 0 ~ i-1 인덱스의 원소의 합을 뜻한다. 그러므로, sum[0]=0 이고, 수들을 입력 받으면서 나머지 sum 배열의 원소들도 채워준다. 구하고자 하는 값이 i번째 수부터 j번째 수의 합이라면 sum[j]-sum[i-1]의 값을 구해주면 O(1)으로 ..
2021 카카오 채용연계형 인턴십 Lv1 숫자 문자열과 영단어 [Java]
2021 카카오 채용연계형 인턴십 Lv1 숫자 문자열과 영단어 1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/81301 2. 문제 해설 카카오 2021 채용연계형 인턴십 코딩테스트의 1번 문제이다. 입력 받은 문자열에서 영어로 들어오는 값을 대응하는 숫자로 바꾸어서 반환해주면 된다. String 배열을 만들어서 zero부터 nine까지 넣어주면 배열의 인덱스랑 딱 대응하기에 쉽게 처리할 수 있다. replaceAll() 메서드를 이용하여 입력 받은 문자열에 있는 영어 값을 전부 숫자로 바꿔준다. 3. 코드 보기 class Solution { public int solution(String s) { String[] numbers = {"zero"..