프로그래머스 - 등대 - c

프로그래머스 - 등대

 

후.. 해결까지 너무 오래 걸렸음...

며칠 만에 간신히 해결했.....

 

일단 세 번의 구현을 거침.

 

 

 

첫 번째 코드는 생각없이 막 썼는데, 테스트 케이스는 통과했으나,

제출 실패였고, print 찍으면서 되짚어 보니 너무 주먹구구식에 개판이라 일단 얘는 걍 버림.

 

 

 

두 번째 코드는 이제 나름 생각해 보면서 씀.

그러나 얘는 테스트 케이스는 통과했지만,

제출 시 실패 케이스 한 두 개 보이고 나머지 죄다 시간 초과...;

다시 보니 함수에서 함수를 들어가고를 반복하다 보니 결과적으로 최대 5중 반복이 ㅋㅋㅋ....

물론 5중첩이 원인이 아닐 가능성 매우 농후.

얘도 문제 많아 보여서 다시 보기는 싫음.

 

 

 

여기까지 이미 며칠이 지나버림;;

 

그리고

 

최종 세 번째 코드는 생각하면서 + 최대한 반복을 줄이려고 하면서 씀.

역시 테스트 케이스는 가볍게 통과.

그러나 제출 시 몇 개는 통과 + 나머지는 비허가 메모리 접근? 에러가 남.

걔가 얘임.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

void setUp(int n, int** list, int* count, int* onoff, int** lighthouse, size_t lighthouse_rows, size_t lighthouse_cols) {
	for (int i = 0; i < n; i++) {
		list[i] = NULL;
		count[i] = 0;
		// onoff 상태, onoff 결정 여부 판단 위해 -1로 초기화
		onoff[i] = -1;
	}
	
	for (int i = 0; i < (int)lighthouse_rows; i++) {
		for (int j = 0; j < (int)lighthouse_cols; j++) {
			// 각 노드의 길 개수 계산.
			count[lighthouse[i][j] - 1]++;
			// list에 테스트케이스 분리 저장. ex) {1,2}{1,3}{2,4}라면 0 - 1, 2 / 1 - 0, 3 / 2 - 0 / 3 - 1 /
			if (list[lighthouse[i][j] - 1] == NULL) {
				list[lighthouse[i][j] - 1] = (int*)malloc(sizeof(int) * count[lighthouse[i][j] - 1]);
			}
			else {
				list[lighthouse[i][j] - 1] = (int*)realloc(list[lighthouse[i][j] - 1], count[lighthouse[i][j] - 1] * sizeof(int));
			}
			list[lighthouse[i][j] - 1][count[lighthouse[i][j] - 1] - 1] = lighthouse[i][((j + 1) % 2)] - 1;
		}
	}
}

int checkOnoff(int n, int cur, int** list, int* count, int* onoff, int* answer) {
	int oncount = 0;

	// 길 개수가 1이면, 즉 내가 리프노드면 끄고 0 반환.
	if (count[cur] == 1 && cur != (n - 1)) {
		onoff[cur] = 0;
		return 0;
	}

	// 직접 연결된 하위 노드의 onoff 조사 및 내가 꺼져도 되는지 알기 위해 켜진 하위 노드 수 체크. 
	// onoff 초기값은 -1이었고 켜면서 지나감.
	for (int i = 0; i < count[cur]; i++) {
		onoff[cur] = 1;
		if (onoff[list[cur][i]] == -1) {
			oncount += checkOnoff(n, list[cur][i], list, count, onoff, answer);
		}
		// 지나온 길은 재귀 안 넣고 켜짐 처리.
		else if (onoff[list[cur][i]] == 1) {
			oncount++;
		}
	}

	// 전부 켜져 있다면 나를 끄고 0 반환.
	if (oncount == count[cur]) {
		*(onoff + cur) = 0;
		return 0;
	}

	// 지나오면서 이미 켜졌기 때문에 그냥 1 반환.
	return 1;
}

void numOfOn(int n, int* answer, int* onoff) {
	for (int i = 0; i < n; i++) {
		*answer += onoff[i];
	}
}

int solution(int n, int** lighthouse, size_t lighthouse_rows, size_t lighthouse_cols) {
	int answer = 0;
	int** list = (int**)malloc(sizeof(int)* n);
	int* count = (int*)malloc(sizeof(int)* n);
	int* onoff = (int*)malloc(sizeof(int)* n);

	// 기본 셋업
	setUp(n, list, count, onoff, lighthouse, lighthouse_rows, lighthouse_cols);

	// 메인 로직
	checkOnoff(n, n - 1, list, count, onoff, &answer);

	// answer 구하기
	numOfOn(n, &answer, onoff);
	
	return answer;
}

에러를 제외하고는 실패가 없는 걸로 미루어 봤을 때 당장 구조상으론 딱히 문제가 없어 보였음.

이제 잘못된 메모리 접근을 찾아야 했음.

 

여기서 또 며칠을 씀 ㅋㅋㅋㅋㅋㅋㅋㅋ....

아니 근데 진짜 아무리 봐도 모르겠는 거;;

분명 개인적인 생각으로는 딱히 문제도 없어 보이고, 인덱스가 넘어갈 가능성이 안 보이는데...

대체 어디서 잘못 접근 하는 건지...

 

동적할당에 대해서 찾아보다 보니 메모리 할당이 실패해서 NULL을 반환할 수도 있다 함.

malloc도 있고 realloc도 있는데 걔네가 NULL을 반환해서 꼬일 수도 있다는 의미로 받아들임.

(확률이 극히 희박하며, 만약 NULL을 반환할 정도로 개판이면 그 프로그램은 답이 없을 것이라는 글도 보긴 함.)

여튼 그래서 얘가 문젠가? 싶어서 while 포인터==NULL 이면 반복 할당  이러면서 별 짓을 다함.

근데 해결이 안돼...

 

...

 

여차저차 해서 list 할당 쪽에서 뭔가 문제가 있다는 거 까진 파악함.

그래서 그냥 list를 이중포인터로 그때그때 할당하려고 하지 말고,

그냥 n * n 사이즈 단일포인터로 박아놓자는 결론에 도달.

따라서 int** list = (int**)malloc(sizeof(int) * n) 얘를 int* list = ...n * n... 으로.. 고쳐야..하..는데... 어라..???  

sizeof(int)....???

ㅇ????

내가 얘를 왜 int 로 써놨어???

ㅎㅎㅎㅎ 설마 문제가 얘 하나 뿐일까 ㅎㅎㅎ

ㅎㅎ 분명 딴 데서도 잘못 한 게 있겠지 ㅎㅎㅎ 라는 마음으로 일단 고침.

int** list = (int**)malloc(sizeof(int*) * n)

 

...

 

ㅎㅎㅎ 너무 잘 되네 ㅎㅎㅎ

헤헤헤헿헤헿ㅎㅎ... 

나 왜 이걸 이제 알아차렸냐 ㅎㅎㅎㅎ

인생 ㅅㅂ....

내 며칠 어디갔어.....?

 

아래에 얘가 내 며칠을 날린 그 새키임..

바로 위 코드랑 ㄹㅇ 딱 한 문장 차이 남...;

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

void setUp(int n, int** list, int* count, int* onoff, int** lighthouse, size_t lighthouse_rows, size_t lighthouse_cols) {
	for (int i = 0; i < n; i++) {
		list[i] = NULL;
		count[i] = 0;
		// onoff 상태, onoff 결정 여부 판단 위해 -1로 초기화
		onoff[i] = -1;
	}
	
	for (int i = 0; i < (int)lighthouse_rows; i++) {
		for (int j = 0; j < (int)lighthouse_cols; j++) {
			// 각 노드의 길 개수 계산.
			count[lighthouse[i][j] - 1]++;
			// list에 테스트케이스 분리 저장. ex) {1,2}{1,3}{2,4}라면 0 - 1, 2 / 1 - 0, 3 / 2 - 0 / 3 - 1 /
			if (list[lighthouse[i][j] - 1] == NULL) {
				list[lighthouse[i][j] - 1] = (int*)malloc(sizeof(int) * count[lighthouse[i][j] - 1]);
			}
			else {
				list[lighthouse[i][j] - 1] = (int*)realloc(list[lighthouse[i][j] - 1], count[lighthouse[i][j] - 1] * sizeof(int));
			}
			list[lighthouse[i][j] - 1][count[lighthouse[i][j] - 1] - 1] = lighthouse[i][((j + 1) % 2)] - 1;
		}
	}
}

int checkOnoff(int n, int cur, int** list, int* count, int* onoff, int* answer) {
	int oncount = 0;

	// 길 개수가 1이면, 즉 내가 리프노드면 끄고 0 반환.
	if (count[cur] == 1 && cur != (n - 1)) {
		onoff[cur] = 0;
		return 0;
	}

	// 직접 연결된 하위 노드의 onoff 조사 및 내가 꺼져도 되는지 알기 위해 켜진 하위 노드 수 체크. 
	// onoff 초기값은 -1이었고 켜면서 지나감.
	for (int i = 0; i < count[cur]; i++) {
		onoff[cur] = 1;
		if (onoff[list[cur][i]] == -1) {
			oncount += checkOnoff(n, list[cur][i], list, count, onoff, answer);
		}
		// 지나온 길은 재귀 안 넣고 켜짐 처리.
		else if (onoff[list[cur][i]] == 1) {
			oncount++;
		}
	}

	// 전부 켜져 있다면 나를 끄고 0 반환.
	if (oncount == count[cur]) {
		*(onoff + cur) = 0;
		return 0;
	}

	// 지나오면서 이미 켜졌기 때문에 그냥 1 반환.
	return 1;
}

void numOfOn(int n, int* answer, int* onoff) {
	for (int i = 0; i < n; i++) {
		*answer += onoff[i];
	}
}

int solution(int n, int** lighthouse, size_t lighthouse_rows, size_t lighthouse_cols) {
	int answer = 0;
	int** list = (int**)malloc(sizeof(int*)* n);
	int* count = (int*)malloc(sizeof(int)* n);
	int* onoff = (int*)malloc(sizeof(int)* n);

	// 기본 셋업
	setUp(n, list, count, onoff, lighthouse, lighthouse_rows, lighthouse_cols);

	// 메인 로직
	checkOnoff(n, n - 1, list, count, onoff, &answer);

	// answer 구하기
	numOfOn(n, &answer, onoff);
	
	return answer;
}

 

씁... 쉽지 않네 증말