2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각SUN,MON,TUE,WED,THU,FRI,SAT
입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열TUE를 반환하세요.
제한 조건
2016년은 윤년입니다.
2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다)
입출력 예
abresult
5
24
TUE
풀이 .
class Solution {
public String solution(int a, int b) {
String answer = "";
int[] months = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
String[] days = {"THU", "FRI", "SAT", "SUN", "MON", "TUE", "WED"};
int total = 0;
for(int i = 0; i < a; i++) {
total += months[i];
}
total += b;
answer = days[total % 7];
return answer;
}
}
public class Main {
public static void main(String[] args) {
Solution sol = new Solution();
}
}
가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다. 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.
제한사항
W, H : 1억 이하의 자연수
입출력 예
WHresult
8
12
80
입출력 예 설명
입출력 예 #1 가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.
풀이 .
->
예제를 바탕으로 조건을 찾아보고자 했다.
예제의 경우 w : h = 8 : 12 이고, 이걸 최대공약수 4로 나누면 2 : 3이 된다.
즉, 전체 map에서 선분이 지나가는 2 x 3 크기의 덩어리가 gcd개 존재하게 된다.
하지만 이 6칸의 사각형이 모두 선분에 걸치는 것은 아니다. 살릴 수 있는 부분도 존재한다. 이걸 계산하는 게 관건인 듯 하다.
라고 여기까지 생각했는데.. 자세히 생각해보니 굳이 w : h가 1이 아닌 최대공약수를 갖도록 맞아떨어지는 수가 주어진다는 보장이 없다. (이걸 굳이 여러 블럭으로 나누려고 할 필요가 없었다)
결국 다시 원점이다.
나누어 떨어지지 않는 경우에 대한 조건을 떠올리기 위해 w : h = 8 : 5 로 직접 그려보았다.
끝 열이 겹치는 형태로 2 x 1, 3 x 1의 3, 2개씩 반복되었다.
여기에서 규칙을 찾을 수 없을까?
(틀린 접근법이었다)
여기에서 더 나아가지 못하고 답을 확인했다.
우선 딱 나누어 떨어지지 않는 경우(gcd = 1인 경우)는 그냥 w x h사이즈의 블록이 gcd개 만큼 반복된다고 보면 된다.
즉, (w / gcd) * (h / gcd) 사이즈가 gcd번 반복되는 일반식을 세우면 되는 것이다.
위에서 관건이라고 언급했던 이 gcd개의 덩어리에서 선분을 지나는 칸을 구하는 것도 일반식을 세울 수 있었다.
이 w/gcd = w', h/gcd = h' 으로 두어 이 덩어리의 사이즈가 w' x h' 라고 두었을 때, 선분이 지나는 칸의 개수는 w' + h' - 1개가 된다.
일반식이기 때문에 gcd가 몇이든 항상 동일하게 적용된다.
어떻게 이런 식이 도출되는가?
->
(w' x h')블록 안에서 선분은 항상 행, 열 중 하나에 대해서만 이동한다. 행과 열을 동시에 이동하는 경우, 즉, 대각선 방향으로 한 번에 이동하는 경우는 없다는 것이다.
(전체를 놓고 봤을 때 대각선 방향으로 이동하는 경우가 있긴 하지만 이건 다음 (w' x h')블록으로 이동하는 것이다. 즉, 위의 빨간 글씨의 문장은 항상 성립하게 된다.)
그럼 결국 선분은 (w' x h')블록 안에서 행을 h'번, 열을 w'번 이동하게 된다. 하지만 블록의 맨 왼쪽위 칸은 첫번째 행과 첫번째 행을 동시에 표현하기 때문에 이 중복에 대한 처리로 -1을 해줘야 한다.
이렇게 w' + h' - 1 이란 식을 도출할 수 있게 된다.
결국 전체 맵에서 손상되지 않은 사각형의 개수는
(w * h) - (w' + h' - 1) * gcd 이라는 식을 통해 구할 수 있게 된다. (단, w' = w / gcd, h' = h / gcd)
class Solution {
public int gcd(int a, int b) {
if(b == 0) return a;
else return gcd(b, a % b);
}
public long solution(int w, int h) {
long answer = 0;
int gcd = gcd(w, h);
answer = ((long)w * (long)h) - (((long)w / gcd) + ((long)h / gcd) - 1) * gcd;
return answer;
}
}
public class Main {
public static void main(String[] args) {
Solution sol = new Solution();
}
}
풀이를 찾아보며 BigInteger 클래스를 사용해서 gcd를 좀 더 편하게 구할 수 있는 방법이 있단 걸 알았다.
사실 원래 방식도 별 거 없어서 그게 그거이긴 하다.
(속도는 원래 방식이 아주 조금 더 빠른 듯 하다)
import java.math.BigInteger;
public int gcd(int a, int b) {
BigInteger bi1 = BigInteger.valueOf(a);
BigInteger bi2 = BigInteger.valueOf(b);
BigInteger gcd = bi1.gcd(bi2);
return gcd.intValue();
}
124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.
124 나라에는 자연수만 존재합니다.
124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.
예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.
10진법124 나라10진법124 나라
1
1
6
14
2
2
7
21
3
4
8
22
4
11
9
24
5
12
10
41
자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.
제한사항
n은 500,000,000이하의 자연수 입니다.
입출력 예
nresult
1
1
2
2
3
4
4
11
풀이 .
class Solution {
public String solution(int n) {
StringBuilder sb = new StringBuilder();
while(n > 0) {
int mod = n % 3;
if(mod == 0) {
mod = 4;
n = n / 3 - 1;
} else
n /= 3;
sb.insert(0, String.valueOf(mod));
}
return sb.toString();
}
}
public class Main {
Solution sol = new Solution();
}
문제를 보자마자 3진법을 사용하면 되겠다는 생각까지는 도달했다.
처음에는 단순히 3진법으로 나온 0, 1, 2를 각각 크기 순서대로 1, 2, 4로 치환하면 될 것이라고 생각했지만 잘못된 풀이였다.
n을 나눈 나머지가 1, 2일 때는 그걸 그대로 쓰면 되지만 0이 나올 떄는 몫을 -1 하고 나머지를 4로 바꿔줘야 한다.
게임개발자인죠르디는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. 죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.
게임 화면은1 x 1크기의 칸들로 이루어진N x N크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은5 x 5크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은1 x 1크기의 격자 한 칸을 차지하며격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다.게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.
만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형두 개가 없어집니다.
크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)
게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.
[제한사항]
board 배열은 2차원 배열로 크기는5 x 5이상30 x 30이하입니다.
board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
0은 빈 칸을 나타냅니다.
1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
moves 배열의 크기는 1 이상 1,000 이하입니다.
moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.
한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.
예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.
첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.
출력
첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.
예제 입력 1
5
4
1312
3
132
예제 출력 1
7
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static ArrayList<Integer> subA, subB;
static int[] A, B;
static int T, N, M;
public static int upperBound(ArrayList<Integer> list, int target) {
int min = 0;
int max = list.size();
while(min < max) {
int mid = (min + max) / 2;
if(list.get(mid) <= target) {
min = mid + 1;
}else {
max = mid;
}
}
return max;
}
public static int lowerBound(ArrayList<Integer> list, int target) {
int min = 0;
int max = list.size();
while(min < max) {
int mid = (min + max) / 2;
if(list.get(mid) >= target) {
max = mid;
}else {
min = mid + 1;
}
}
return max;
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
// A[] 전처리
N = Integer.parseInt(br.readLine());
A = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
// B[] 전처리
M = Integer.parseInt(br.readLine());
B = new int[M];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < M; i++) {
B[i] = Integer.parseInt(st.nextToken());
}
// 각 배열에 대한 부분배열의 합
subA = new ArrayList<>();
for(int i = 0; i < N; i++) {
int sum = A[i];
subA.add(sum);
for(int j = i + 1; j < N; j++) {
sum += A[j];
subA.add(sum);
}
sum = 0;
}
Collections.sort(subA);
subB = new ArrayList<>();
for(int i = 0; i < M; i++) {
int sum = B[i];
subB.add(sum);
for(int j = i + 1; j < M; j++) {
sum += B[j];
subB.add(sum);
}
sum = 0;
}
Collections.sort(subB);
// 이분탐색으로 정답 찾기
long ans = 0;
for(int i = 0; i < subA.size(); i++) {
ans += upperBound(subB, T - subA.get(i)) - lowerBound(subB, T - subA.get(i));
}
System.out.println(ans);
}
}
처음에는 부분배열의 합을 담는 배열 subA, subB를 구하기 위해 DFS를 짰었다.
근데 굳이 그럴 필요 없이 이중 for문을 사용해서 모든 부분배열의 합을 구할 수 있었다.
