[JAVA] 백준 2089번

2089번 -2진수

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());

		Stack<Character> resultStack = new Stack<Character>();

		if (N == 0) { // N이 0 인경우
			resultStack.push('0');
		}

		while (N != 0) { // N이 0이 아닌경우

			int r = N % -2;

			if (r == -1) { // 나머지가 -1 인경우 스택에 1을 추가하고 나눈몫의 값에 1을 더한다
				resultStack.push('1');
				N = N / -2 + 1;

			} else if (r == 1) {
				resultStack.push('1');
				N = N / -2;
			} else {
				resultStack.push('0');
				N = N / -2;
			}

		}

		while (!resultStack.empty()) {
			bw.write(resultStack.pop());
		}

		bw.flush();
		bw.close();
	}

}

 

정답을 맞힌 풀이 방법

1 .  입력받은 수를 -2로 나누는 반복문을 만들어 나머지를 Stack에 넣어 준다.

2.  이때 나머지가 -1(음수)인 경우에는 나눈 몫에 1을 더해준다. 결과값이 양수인 0 과 1로만 표현되어야 하기 때문이다.

3. ex) -13의 경우 :

                               -13 =     -14 + 1     =  (-2 * 7) ... 1

                                  7 =                           (-2 * -3) ... 1

                                -3 =     -4 + 1     =     (-2 * 2) ... 1

                                 2 =                            (-2 * -1) ...0

                                -1 =     -2 +1     =       (-2 * 1)...1

                                  1 =                             (-2 * 0) ...1