백준 15663 N과 M (9) JAVA

sundays·2024년 6월 27일
0

문제

N과 M (9)

풀이

백트래킹에 대한 내용은 이전이랑 너무 비슷해서 생략하고,
중복된 순서대로 나오면 안되서 뭘쓸까하다가..그냥만만한 hashset을 사용했다
근데 생각해보니 적재순서를 보장해줘야 해서 LinkedHashSet을 사용해서 풀었다.

메모리 공간이 너무 많이 차지하려나? 했는데 맞았다.
그리고 지금보니까 vistied 배열도 공간을 줄이면 메모리도 더줄일수 있을거같고

자료 구조를 이용한 것도 괜찮긴한데...

이런풀이말고 다른게 더 괜찮을거 같아서
다른 분들 풀이 보니까 visited 체크와 동시에 backtracking 안에서 변수를 선언해서 이전에 들어간 값이랑 겹치지 않는 값을 선택하기 위해 이전값을 저장하고 있다가 비교를 하고있었다. 자바코드는 아니지만 너무 좋자나

void func(int cnt) {
	if (cnt == m) {
		for (int i = 0; i < m; i++)
			printf("%d ", res[i]);
		printf("\n");
		return;
	}
	int xx = 0;
	for (int i = 0; i < n; i++) {
		if (!chk[i] && arr[i] != xx) {
			res[cnt] = arr[i];
			xx = res[cnt];
			chk[i] = true;
			func(cnt + 1);
			chk[i] = false;
		}
	}
}

출처
나중에 보고 배껴야지~

이제보니까 hash사용한 풀이들도 많구나 휴 다행이다,

전체 코드

전체 코드

profile
develop life

0개의 댓글