1. A (Favorite Sequence)
1-1. 링크
1-2. 문제 해석
1-3. 코드 및 해설
2. B (Last Year's Substring)
1-1. 링크
1-2. 문제 해석
1-3. 코드 및 해설
3. C (Unique Number)
1-1. 링크
1-2. 문제 해석
1-3. 코드 및 해설
4. 반성의 시간
1. A (Favorite Sequence)
1-1. 링크
Problem - A - Codeforces
codeforces.com
1-2. 문제 해석
숫자들이 담긴 배열이 주어진다.
예를 들어서 a = [1, 2, 3, 4, 5, 6]이라고 해보자.
이걸 앞에서부터 차례대로 옮겨적을건데 앞서 적은 숫자와 가장 멀리 배치되도록 적을 것이다.
1예를 들어서 1을 옮겨 적었다고 치자
1 2그다음 순서인 2를 옮겨 적을 때는 1과 최대한 멀리 떨어지게 옮겨 적는다.
1 3 2그다음 순서인 3을 옮겨 적을 때는 앞서 적은 2와 최대한 멀리 떨어지게 옮겨 적는다.
단, 이때 3은 1의 우측에 위치해야 한다.
1 3 4 2그다음 순서인 4를 옮겨 적을 때는 앞서 적은 3과 최대한 멀리 떨어지게 옮겨 적는다.
단, 이때 4는 2의 좌측에 위치해야 한다.
1 3 5 4 2그다음 순서인 5를 옮겨 적을 때는 앞서 적은 4와 최대한 멀리 떨어지게 옮겨 적는다.
단, 이때 5는 3의 우측에 위치해야 한다.
1 3 5 6 4 2마지막으로 6을 최대한 5와 멀리... 떨어지게 적어야 하지만 공간이 없으니 어쩔 수 없이 붙어있게 되긴 했지만
어쨌든 이렇게 해서 끝!
규칙을 말로 설명하려니 좀 복잡해지긴 하는데 사실 되게 간단한 규칙이다.
앞의 숫자부터 좌측, 우측으로 번갈아가며 옮겨 적으면 되는 규칙이다.
근데... 누가 그랬더라? 한국말은 끝까지 들어봐야 한다고?
한국말뿐만 아니라 영어도 마찬가지더라
A번 문제가 요구하는 것은 배열을 줄 테니 이러한 규칙에 따라 만들어진 배열을 출력하시오가 아니라
이러한 규칙에 따라 만들어진 배열이 있으니 처음 배열을 출력하시오였다.
이걸 놓쳐서 삽질함... ^^...
즉, 배열이 주어지면 맨 왼쪽, 맨 오른쪽에 있는 값들을 순서대로 가져와서 출력하면 되는 문제였다.
1-3. 코드 및 해설
public class A_김주환 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int testCase = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= testCase; tc++) {
int n = Integer.parseInt(br.readLine());
String[] arr = new String[n];
String[] input = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
if (i % 2 == 0) arr[i] = input[i / 2]; // 짝수번째에는 맨 왼쪽 값을 가져오고
else arr[i] = input[n - (i / 2) - 1]; // 홀수번째에는 맨 오른쪽 값을 가져온다.
}
for (int i = 0; i < n; i++) {
sb.append(arr[i]).append(" ");
}
sb.append("\n");
}
System.out.println(sb.toString());
}
}짝수번째 홀수번째에 맞게 왼쪽 혹은 오른쪽 값을 가져오면 되는 간단한 문제였다.
Deque로 풀까 배열로 풀까 고민하다가 그래도 배열이 더 빠르지 않을까 싶어 배열로 풀었다.
2. B (Last Year's Substring)
2-1. 링크
Problem - B - Codeforces
codeforces.com
2-2. 문제 해석
언제나 느끼는 거지만 코드 포스는 문제는 문제 푸는 시간보다 해석하는 시간이 더 걸리는 것 같다... ㅠ
한글로 된 알고리즘 문제도 맨날 제대로 못 읽고 틀리는데 영어는 오죽해...
아무튼!
이 문제는 23048293492 이런 숫자를 줄 건데 너 여기서 substring을 한번 써서 2020이라는 숫자를 만들 수 있어?
를 묻는 문제이다.
예를 들어 20192020이라는 숫자는 앞에 2019를 지우면 2020을 만들 수 있고
22019020이라는 숫자는 가운데에 2019를 지우면 2020을 만들 수 있다.
| prefix | suffix |
| 2020 | |
| 2 | 020 |
| 20 | 20 |
| 202 | 0 |
| 2020 |
나올 수 있는 경우의 수가 5가지밖에 안되므로 약간 무지성 코딩...?으로 푸니 쉽게 풀렸다.
2-3. 코드 및 해설
public class B_김주환 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testCase = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= testCase; tc++) {
int n = Integer.parseInt(br.readLine());
String input = br.readLine();
System.out.println(has2020(input) ? "YES" : "NO");
}
}
public static boolean has2020(String input) {
if (input.startsWith("2020") || input.endsWith("2020")) {
return true;
}
if (input.startsWith("2") && input.endsWith("020")) {
return true;
}
if (input.startsWith("20") && input.endsWith("20")) {
return true;
}
if (input.startsWith("202") && input.endsWith("0")) {
return true;
}
return false;
}
}나는 startsWith랑 endsWith를 활용해서 검사를 해주었다.
이런 함수가 없는 C언어 같은 경우는 인덱스 하나하나 비교 검사를 해주면 되고
파이썬은... 스터디원 보니까 엄청 코드가 간결하던데 파이썬을 잘 몰라서... 매번 파이썬 답안을 보면서 깜짝깜짝 놀란다.
3. C (Unique Number)
3-1. 링크
Problem - C - Codeforces
codeforces.com
3-2. 문제 해석
어떤 숫자의 각 자릿수를 더해서 숫자 x를 만들 수 있다고 할 때
이 어떤 숫자가 될 수 있는 최솟값은 얼마인가?라는 문제이다.
(단, 각 자릿수는 중복될 수 없다. 예를 들어 11은 불가능!)
- 49 (4 + 9 = 13)
- 58 (5 + 8 = 13)
- 67 (6 + 7 = 13)
예를 들어서 x가 13이라고 했을 때 13을 만들 수 있는 숫자는 위와 같다.
그중에서 최솟값은 49 임을 알 수 있다.
이 문제는 잘 생각해보면 2가지 사실을 알 수 있다.
우선 첫 번째로 최대한 큰 숫자를 일의 자리에 가깝게 배치해야 한다는 것이다.
그래야 가장 높은 자릿수에 작은 숫자를 배치할 수 있을 테니까.
즉, 9부터 차례대로 일의 자리부터 넣어보면서 반복문을 돌면
반복문을 많이 돌아봤자 9번 만에 정답을 찾을 수 있다.
두 번째는 각 자릿수는 중복될 수 없다는 규칙 때문에 사실상 만들 수 있는 숫자 x의 값이 그리 크지 않다는 것이다.
1부터 9까지 모든 숫자를 다 사용한다고 해도 x의 최댓값은 45밖에 되지 않는다.
이 점을 이용해서 DFS로 풀이한 스터디원도 있었다.
하지만 아무래도 첫 번째 방법이 더 효율적이다.
3-3. 코드 및 해설
public class C_김주환 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testCase = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= testCase; tc++) {
StringBuilder sb = new StringBuilder();
int x = Integer.parseInt(br.readLine());
int n = 9; // 9부터 1까지 검사
while (x != 0) {
if (n == 0) { // x가 0이 안됐는데 n이 0이 됐다? 즉, x를 만들 수 없다는 뜻임
sb.setLength(0); // sb를 초기화하고
sb.append("1-"); // -1을 넣고 (reverse 할거라서 1-)
break; // 탈출
}
if (x >= n) { // x가 n보다 같거나 크면
x -= n; // x에서 n을 빼고
sb.append(n); // n을 sb에 저장
}
n--; // 그 다음 n값 검사 (내림차순)
}
System.out.println(sb.reverse().toString()); // sb에 저장된 값을 역으로 출력
}
}
}해설은 주석으로 다 달아두었다.
4. 반성의 시간
D번을 풀다가 시간이 끝났는데 솔직히 시간이 있었어도 D번은 못 풀었을 것 같다.
그럴듯한 방법이 떠오르지 않았다.
매번 3솔만 하는데 실력이 어째 느는것 같지가 않네...
그래서 오늘부터는 문제 푼 내용을 포스팅으로 적어두려고 한다. 이러면 도움이 되겠지!
💡 느낀 점
- Codeforces는 알고리즘 고수분들이 주로 애용하는 사이트 같던데... 3솔 따리가 포스팅을... 죄송합니다... 😓
- 그 고수분들이 우리 스터디원들... 다들 어떻게 그렇게 잘하는 거지?
- 얼른 4솔 하고 싶다.
댓글