[Boj] 2464. 비밀번호 - java

⬛ 2464. 비밀번호

https://www.acmicpc.net/problem/2464

2464번: 비밀번호

⬛ 풀이 방법

• 1의 개수가 같으면서 가장 가까운 작은 수와 가장 가까운 큰 수를 찾기
• 입력받은 수를 이진수 리스트로 저장 (43 = 101011(2), list = [1, 1, 0, 1, 0, 1, 0])
• 해당 수보다 더 작은 수를 찾기 위해서는 리스트를 인덱스 0부터 돌며 01이 되는 부분 찾아서 10로 swap ( [1, 1, 0, 1, 0, 1, 0] -> [1, 1, 1, 0, 0, 1, 0] )
• 해당 수보다 더 큰 수를 찾기 위해서는 리스트를 인덱스 0부터 돌며 10이 되는 부분 찾기 01로 swap( [1, 1, 0, 1, 0, 1, 0] -> [1, 0, 1, 1, 0, 1, 0] )
• 01 또는 10인 부분을 단지 swap하는 과정만 하면 (1100000111 보다 작은 수 중 가장 큰 수는1011110000) 같은 경우를 해결하지 못한다.

⬛ 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class 비밀번호_2464 {

	static int cnt;
	static List <Integer> smallList = new ArrayList<>();
	static List <Integer> bigList = new ArrayList<>();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long A = Long.parseLong(br.readLine());
		long X = A;
	
		while(A > 0L) {
			smallList.add((int)(A%2));
			bigList.add((int)(A%2));
			if((int)(A%2)==1)
				cnt++;
			A = A/2;
		}
		smallList.add(0);
		bigList.add(0);
		System.out.println(small() + " " +big());
	}
	public static long small() {
		int i;
		for(i = 1; i < smallList.size();i++) {
			if(smallList.get(i) == 1 && smallList.get(i-1) == 0) {
				smallList.set(i, 0);
				smallList.set(i-1, 1);
				break;
			}
		}
		if(i == smallList.size())
			return 0;
		for(int j = 0; j < i;j++) {
			smallList.set(j, 0);
		}
		int count = 0;
		for(int j = 0; j <smallList.size();j++) {
			if(smallList.get(j) == 1)
				count++;
		}
		for(int j = 0; j < cnt - count; j++) {
			smallList.set(i-1-j, 1);
		}
		return toDecimal(smallList);
	}
	public static long big() {
		int i;
		for(i = 1; i < bigList.size();i++) {
			if(bigList.get(i) == 0 && bigList.get(i-1) == 1) {
				bigList.set(i, 1);
				bigList.set(i-1, 0);
				break;
			}
		}
		if(i == bigList.size())
			return 0;
		for(int j = 0; j < i;j++) {
			bigList.set(j, 0);
		}
		int count = 0;
		for(int j = 0; j <bigList.size();j++) {
			if(bigList.get(j) == 1)
				count++;
		}
		for(int j = 0; j < cnt - count; j++) {
			bigList.set(j, 1);
		}
		return toDecimal(bigList);
		
	}
	public static Long toDecimal(List<Integer> list) {
		Long result = 0L;
		Long bin = 1L;
		for(int i = 0; i < list.size(); i++) {
			result += bin * (long)list.get(i);
			bin *= 2L;
		}
		
		return result;
	}
}