1225. [S/W 문제해결 기본] 7일차 - 암호생성기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14uWl6AF0CFAYD 

SW Expert Academy

 

문제 해석

8자리의 숫자를 입력받습니다.

첫 번째 숫자를 1 감소한 뒤, 맨 뒤로 보냅니다.

그다음 첫 번째 주는 +1을 더한 수를 감소한 뒤 맨 뒤로 보냅니다.

이 사이클은 5가 감소할 때까지만 반복합니다.

 

반복 수행 시 뒤로 이동한 후 해당 숫자가 0보다 작거나 0인 경우에 반복이 종료되며 해당 숫자 배열이 암호가 됩니다.

 

 

문제 풀이 전 설계

 

반복과 종료 시점이 문제에 적절하게 명시되어있기 때문에 바로 구현할 수 있습니다.

 

이때 어떤 자료구조를 사용하면 좋을까요?

해당 문제는 0번째 index를 N-1 번째 인덱스로 보내야 합니다.

 

만약 배열을 사용한다면 어떻게 될까요? 

0번째 index를 N-1번째로 보내는 건 O(1)을 시간 복잡도가 소요되지만

1번째 index부터 N-2번째 index까지 왼쪽으로 한 칸씩 당기는 것은 O(N)의 시간 복잡도가 소요됩니다.

 

연결 리스트를 사용하면 어떻게 될까요?

단순히 0번째 index와 N-1번째 index를 교환하면 됩니다. O(1)의 시간 복잡도가 소요됩니다.

 

 

package day0208;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Solution_1225_암호생성기 {
	static BufferedReader br;
	static List<Integer> passwordList = new LinkedList<Integer>();

	public static void main(String[] args) throws IOException {

		br = new BufferedReader(new InputStreamReader(System.in));
		
		for (int testCase = 1; testCase <= 10; testCase++) {
			
			input();
			// 입력 테스트
			// inputTest(passwordList);

			// 메인 로직실행
			int cnt =1;
			while (true) {				
				if (isZero()) {
					break;
				}				
				swapList();
				decrease(cnt++);
				// cycle 1~5반복
				if(cnt ==5) {
					cnt=1;
				}												
			}
			
			StringBuilder sb = new StringBuilder();
			sb.append("#" + testCase + " ");
			for (int value : passwordList) {
				sb.append(value + " ");
			}
			System.out.println(sb.toString());
			
			passwordList.clear();

			
		}
	}

	static void input() throws IOException {

		// testCase 입력 제외
		br.readLine();

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		// 암호는 8개 존재
		for (int i = 0; i < 8; i++) {
			passwordList.add(Integer.parseInt(st.nextToken()));
		}
	}

	static void inputTest(List<Integer> passwordList) {
		for (int value : passwordList) {
			System.out.print(value + " ");
		}
		System.out.println();
	}

	// 0번째 index를 마지막 index로 이동
	static void swapList() {
		int firstElement = passwordList.get(0);
		passwordList.add(firstElement);
		passwordList.remove(0);
		
	}

	// N-1번째 index를 i만큼 뺌
	// 0보다 작으면 0을 입력
	static void decrease(int i) {
		int index = passwordList.size() - 1;
		int element = passwordList.get(index) - i < 0 ? 0 : passwordList.get(index) - i;
		passwordList.set(index, element);
	}

	// N-1 번째 index가 0이라면 true
	static boolean isZero() {
		if (passwordList.get(passwordList.size() - 1) != 0) {
			return false;
		}

		return true;
	}
}

 

연결 리스트를 사용해서 구현하였습니다.

Queue를 사용하신다면 굳이 따로 메서드를 구현할 필요가 없을 것 같습니다.