글 읽기 - 메모리 초과 질문

ikth6001 4년 전 0

1023번 문제를 풀고 있는데, 알고리즘에 초보이다 보니 일단 효율 보다는 무식한 방법으로라도 구해보자는 생각으로 공부 중입니다.

문제를 풀었는데 시간초과가 아닌 메모리 초과가 나서... 이해가 안가서 질문 드립니다.

제가 구현한 알고리즘을 간략히 설명 드리자면

n으로 구할 수 있는 모든 문자열의 max 값을 구한다.
0부터 1에서 구한 max까지 for문을 돌면서 바이너리 문자열로 변경 하고, 옳바른 괄호 문자열인지 확인 합니다.
k 값 안에 괄호ㄴㄴ 문자열이 구해지면 그 문자열을 리턴하고 아니면 -1을 리턴 합니다.

재귀 호출을 사용한것도 아니고 딱히 맴버변수도 없어서.. 메모리 초과가 나는 이유를 모르겠네요... 조언 부탁 드립니다.

감사합니다.

import java.util.Scanner;

/**
 * https://www.acmicpc.net/problem/1023
 */
public class Main {
	
	private final char OPEN= '0';
	private final char CLSE= '1';

	public static void main(String[] args) {

		try(Scanner scanner= new Scanner(System.in)) {
			Main m= new Main();
			
			int n= scanner.nextInt();
			long k= scanner.nextLong();
			
			System.out.println(m.solution(n, k));
		}
		
	}
	
	/**
	 * @param n 50보다 작은 자연수
	 * @param k 2^(n-1)보다 작은 자연수
	 * @return
	 */
	private String solution(int n, long k) {
		
		long max= (long) Math.pow(2, n);
		long cnt= 0;
		
		for(long i=0; i<max; i++) {
			String binary= toFixedLengthBinary(n, i);
            
			if(isNoBracketNum(binary)) {
				
				if(cnt++ == k) {
					return toBracketString(binary);
				} else if(cnt > k) {
					break;
				}
			}
		}
		
		return "-1";
	}
	
	private boolean isNoBracketNum(String binary) {
		int openCnt= 0;
		int clseCnt= 0;
		
		for(char n : binary.toCharArray()) {
			
			if(n == OPEN) {
				openCnt++;
			} else if(n == CLSE) {
				clseCnt++;
			}
			
			if(openCnt > binary.length() / 2
					|| clseCnt > openCnt) {
				return true;
			}
		}
		
		return false;
	}
	
	private String toFixedLengthBinary(int leng, long num) {
		return String.format("%" + leng + "s", Long.toBinaryString(num)).replace(' ', '0');
	}
	
	private String toBracketString(String binary) {
		return binary.replace(OPEN, '(').replace(CLSE, ')');
	}
}

sait2000 4년 전 1

왜 메모리 초과인지는 모르겠지만, 어쨌든 통과하긴 힘든 코드입니다. 시간이 오래 걸릴 겁니다.

in:
50 1121037960441171

out:
))))))))))))))))))))))))))))))))))))))))))))))))))

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모리 초과 질문

ikth6001 4년 전 0

sait2000 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말