[알고리즘] 암호생성기
2024. 2. 2. 16:30ㆍ알고리즘 풀이/Java
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14uWl6AF0CFAYD
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
package daily05.swea.no1225;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Solution1 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
long s = System.currentTimeMillis();
for(int tc = 1 ; tc <= 1; tc++) {
br.readLine();
StringTokenizer st = new StringTokenizer(br.readLine());
Deque<Integer> deq = new ArrayDeque<>();
for(int i = 0; i< 8; i++) {
deq.add(Integer.parseInt(st.nextToken()));
deq.add(Integer.MAX_VALUE);
}
int totalCount = 0 ;
int count = 0;
while (true) {
int first = deq.pollFirst();
if(first - (count +1) <=0) {
deq.addLast(0);
break;
}
if(totalCount++ % 100 == 0) System.out.println(totalCount);
deq.addLast(first - ++count);
count %= 5;
}
sb.append("#").append(tc).append(" ");
while(!deq.isEmpty()) {
sb.append(deq.pollFirst()).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
System.out.println(System.currentTimeMillis() - s);
}
}첫번째 접근
앞에서 빼고 뒤로 추가해주는 행위를 반복해야 하기 때문에 여기에 적합한 deque을 활용한다.
다음을 반복해서 진행한다.
ㄱ. deque의 첫번째 값을 뺀다.
ㄴ. 현재 줄여야 하는 값만큼 줄인다.
ㄷ. 값이 만약 0보다 작다면 deque에 넣어주고 반복을 종료한다.
ㄹ. 그렇지 않다면 deque에 넣어준다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Solution {
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for (int testCase = 1; testCase <= 1; testCase++) {
st = new StringTokenizer(br.readLine());
int N = 8;
int[] tempArray = new int[N];
st = new StringTokenizer(br.readLine());
int minValue = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
tempArray[i] = Integer.parseInt(st.nextToken());
minValue = Math.min(minValue, tempArray[i]);
}
int fiveCycleNum = minValue / 15 - 1; // 15로 나누어 떨어지는게 있을때 예외 처리
tempArray = subtractFiveCycle(tempArray, fiveCycleNum);
Deque<Integer> deque = changeToDeque(tempArray);
findCode(deque);
sb.append("#").append(testCase).append(" ");
for (Integer integer : deque) {
sb.append(integer).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
}
private static int[] subtractFiveCycle(int[] tempArray, int fiveCycleNum) {
return Arrays.stream(tempArray)
.map((e) -> e - fiveCycleNum * 15).toArray();
}
private static int[] sortArray(int[] tempArray, int moveNum) {
int[] result = new int[8];
for (int i = 0; i < 8; i++) {
int index = i - moveNum % 8;
if (index < 0) {
result[(8 + index)] = tempArray[i];
}
else {
result[index] = tempArray[i];
}
}
return result;
}
private static Deque<Integer> changeToDeque(int[] tempArray) {
Deque<Integer> deque = new LinkedList<>();
for (int ele : tempArray) {
deque.addLast(ele);
}
return deque;
}
private static void findCode(Deque<Integer> deque) {
int j = 0;
while (true) {
int element = deque.pollFirst();
element -= (j+1);
if (element <= 0) {
element = 0;
deque.addLast(element);
return;
}
j = (j + 1) % 5;
deque.addLast(element);
}
}
}두번째 접근
integer의 값이 20억 정도라는 것을 감안하면 이를 계속 반복하는건 시간 측면에서 비효율적이라는 생각이 든다.
왜냐하면 총 8번의 사이클을 진행하게 되면 모든 원소는 무조건 15만큼 감소하게 되고 다시 원래의 첫번째 원소가 다시 감소 순서가 된다.
그렇다면 원소값 중 최솟값을 먼저 15로 나눠준 몫은 8번의 사이클의 개수가 된다.
모든 원소에 대해 몫 * 15만큼으로 빼주게 되면 모든 원소는 15 미만이 된다.
그리고 (5 * 8) * 몫만큼 감소가 진행된 것이기 때문에 이를 활용해 각각의 원소의 현재 위치를 구할 수 있다.
이를 이용하여 위치를 다시 설정해주면 모든 원소가 15미만인 상태에서 넣고 빼는 작업을 진행해주면 되기 때문에 넣고 빼는 연산의 횟수가 크게 줄어들게 된다.
이러한 방법을 활용하여 두번째 접근을 진행하였다.
세번째 접근
그런데 원소의 현재 위치는 그대로다. 왜냐하면 40 움직임을 하나의 단위로 받기 때문에 8로 나누어 떨어져기 때문이다.
따라서 sort하는 함수를 빼줄 수 있다. 그러면 최종 코드는 다음과 같이 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Solution {
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for (int testCase = 1; testCase <= 1; testCase++) {
st = new StringTokenizer(br.readLine());
int N = 8;
int[] tempArray = new int[N];
st = new StringTokenizer(br.readLine());
int minValue = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
tempArray[i] = Integer.parseInt(st.nextToken());
minValue = Math.min(minValue, tempArray[i]);
}
int fiveCycleNum = minValue / 15 - 1; // 15로 나누어 떨어지는게 있을때 예외 처리
tempArray = subtractFiveCycle(tempArray, fiveCycleNum);
Deque<Integer> deque = changeToDeque(tempArray);
findCode(deque);
sb.append("#").append(testCase).append(" ");
for (Integer integer : deque) {
sb.append(integer).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
}
private static int[] subtractFiveCycle(int[] tempArray, int fiveCycleNum) {
return Arrays.stream(tempArray)
.map((e) -> e - fiveCycleNum * 15).toArray();
}
private static Deque<Integer> changeToDeque(int[] tempArray) {
Deque<Integer> deque = new LinkedList<>();
for (int ele : tempArray) {
deque.addLast(ele);
}
return deque;
}
private static void findCode(Deque<Integer> deque) {
int j = 0;
while (true) {
int element = deque.pollFirst();
element -= (j+1);
if (element <= 0) {
element = 0;
deque.addLast(element);
return;
}
j = (j + 1) % 5;
deque.addLast(element);
}
}
}'알고리즘 풀이 > Java' 카테고리의 다른 글
| [알고리즘] 수열 편집 (1) | 2024.02.05 |
|---|---|
| [알고리즘] 암호문3 (0) | 2024.02.02 |
| [알고리즘][X] LCS 2 (0) | 2024.01.31 |
| [알고리즘][X] 스위치 켜고 끄기 (0) | 2024.01.30 |
| [알고리즘] 재귀를 통한 순열 (0) | 2024.01.30 |