[synergy 요청] codeup 1411번 빠진 카드 문제 풀이
CodeUp 1411번 (1차원 배열 문제)
01. 문제 정의 ☝️
문제 설명
우리는 1부터 N까지의 숫자가 차례대로 적힌 N장의 카드 묶음을 가지고 있다.
그런데 이 카드 묶음을 옮기는 중 실수로 땅에 떨어뜨려 그 중 한 장을 잃어버렸다.
여러 분은 땅에 떨어진 카드 묶음을 읽어서 빠진 하나의 카드 번호를 찾아 출력해야 한다.
입력
첫 줄에는 한 장을 잃어버리기 전 카드의 전체 장수 N이 주어져 있다. 단 . 3 <= N <= 50 이다.
이어지는 N-1개의 각 줄에는 한 장이 빠진 카드 묶음의 카드 숫자가 하나씩 순서 없이 나열되어 있다.
출력
여러분은 주어진 카드 묶음에서 빠진 하나의 카드를 찾아서 그 번호를 출력해야 한다.
입력 예시
10 3 4 1 10 2 6 7 5 9
출력 예시
8
첫 줄에 입력되는 숫자는 1부터 N까지의 범위이며, 이 후로부터 입력되는 숫자들은 N-1개로 입력된 숫자들 중에 빠진 숫자 하나를 찾는 문제입니다. 쉽게 생각하면 어렵지 않은 내용이지만 처음 문제를 해결하는 분들을 위해 어떻게 문제를 풀어가야 하는지 쉽게 설명해드리도록 하겠습니다.
02. 문제를 해결하는 코드를 구현하기 위한 방법
문제가 간단하면 간단할수록 그 문제를 풀 수 있는 방법은 다양한 방법이 있습니다. 그 중에 제가 설명 드렸던 한 가지 방법과 코드 설명을 요청해주셨던 방법 두 가지 코드를 설명해드리겠습니다. 문제를 푸는 순서나 방법에 대해서는 주관적인 부분이 많지만 저는 이런 식으로 문제를 풀고 있으니 분명 배울 점이 있을 거라 생각합니다.
먼저 저는 문제를 해결하기 위한 코드를 짤 때, 입력 / 처리 / 출력 부분을 나누어서 작성합니다.
입력에서는 필요한 변수를 선언하거나 입력받은 data를 저장할 변수나 배열을 정리합니다.
처리하는 부분에서는 문제에서 요구하는 답을 찾기 위한 코드를 구현합니다.
출력하는 부분은 물론 화면 상에 출력하는 의미도 포함되지만 함수를 구현할 때는 return 값을 정리하는 것을 의미하기도 합니다.
02.1. 입력 👇
이렇게 입력 / 처리 / 출력 세 부분만 나눠서 생각하시면 어렵지 않게 푸실 수 있습니다. 먼저 문제에서 입력받는 숫자들을 어떻게 저장할 것인지와 몇 개를 저장받아야하는지를 정합니다. 위의 예시에서는 입력되는 숫자가 두 종류입니다. 하나는 첫번째 줄의 숫자 (범위를 나타내는 숫자) 와 두번째부터는 카드 숫자로 이어서 N-1개가 입력됩니다. 이렇게 연관되어 있는 수들과 그렇지 않은 수들이 있는 것을 알 수 있겠죠? 보통 연관이 되는 숫자들, 특히 이렇게 순차적으로 범위 안에 있는 숫자들의 경우는 배열로 저장하는 것이 좋습니다.
그 이유를 설명드리자면 10 이후의 3 4 1 10 2 6 7 5 9 의 숫자는 첫번째 숫자에 의해 개수가 달라집니다. 이런 입력을 변수로 받게 하려면 서로 다른 이름의 50개의 변수를 가져야하며 나중에 조건을 확인하려할 때 50개의 변수들을 각각 모든 수와 비교해서 알아내야 합니다. 하지만 배열에 저장하면 배열 안에 필요한 크기만큼 선언해서 입력을 받을 수 있고 이후에 반복문을 통해 조건을 검색하거나 출력을 할 때 쉽게 구현할 수 있습니다.
그럼 이제 첫번째 줄은 임의의 변수로 두번째 줄의 입력부터는 배열에 저장해야한다는 점 아시겠죠?
입력받는 코드를 구현해보면 아래와 같습니다.
#include <stdio.h>
int main(void) {
int num; // 첫번째 줄의 수를 임의의 변수로 저장
scanf("%d", &num); // num 입력 받음
int nums[num-1]; // 2번째 수부터 저장받을 배열 선언
for (int i = 0 ; i < num ; ++i)
scanf("%d", &nums[i]); // 반복문을 통해 배열 입력 받음
입력에 대한 코드는 구현되었습니다. 현재 선언된 변수와 저장된 배열의 모습을 그려보면 아래와 같습니다.
.PNG)
02.2. 처리 (Idea) / 출력 👇
이제 저렇게 저장된 배열들 중에 1부터 10까지의 숫자 중 빠진 숫자를 찾아내는 처리 부분의 코드를 작성하면 됩니다. 위에서 설명한 것처럼 이 부분의 방법은 아주 다양합니다. 저는 그 중에서 가장 쉽게 생각할 수 있는 방법을 구현해보겠습니다.
누구나 생각할 수 있는 아이디어 중 하나가 바로 배열 안에 먼저 1이 있는지 보고 있으면 하나 증가해서 2가 있나 보고 또 3도 찾고 10까지 찾다보면 없는 수 하나를 찾을 수 있다 일겁니다. 말로는 너무 간단하죠?
처음 코드를 구현하시는 분들은 이런 아이디어를 말로 써보는 것이 굉장히 중요합니다. 이런 말들을 코드로 변환시켜보면 구현할 수 있기 때문입니다. 이런 식으로 연습하다 보면 나중에는 글로 쓰지 않아도 머리 속에 그려지실 겁니다. 우리는 처음 구현하시는 분들을 위해서 아주 기초적으로 코드를 구현해보겠습니다.
아이디어를 정리해보면 1부터 10까지 숫자를 하나씩 배열 안에 모든 수와 비교해보고 배열 안에 없는 수를 찾아낸다 입니다. 배열 안에 모든 수를 비교하기 위해서는 반복문으로 비교하면 되겠다는 생각이 드실까요? 또 1부터 10까지 숫자를 비교하기 위해선 배열 안에 숫자 외에 다른 기준이 되는 변수가 필요하겠구나라는 생각도 하셔야합니다. 이렇게 글로 써보니 어떤 변수가 필요하며 어떻게 비교를 해야할지 조금은 쉽게 정리할 수 있었습니다.
그럼 코드로는 먼저 임의의 변수를 하나 선택하고 1로 설정할 것입니다. 그리고 nums의 0번째 배열부터 8번째 배열까지 비교를 해볼 겁니다. 만약 1이 중간에 있다면 이번엔 2로 nums의 0번째 배열부터 8번째 배열까지 비교합니다. 또 중간에 2도 있다면 하나 증가시켜 3을 비교하고 이렇게 비교하는 코드를 만들어 보겠습니다.
int count = 1; // 임의의 변수를 1로 초기화
for (int j = 0; j < num-1; ++j) { // 반복문을 돌려서 0번째 배열부터 8번째 배열까지 비교
if (nums[j] == count) // nums[j] 와 count가 맞는 숫자가 있는지 확인
// ??
}
이 작업을 2도 3도 쭉 비교할 겁니다.
int count = 1; // 임의의 변수를 1로 초기화
for (int j = 0; j < num-1; ++j) { // 반복문을 돌려서 0번째 배열부터 8번째 배열까지 비교
if (nums[j] == count) // nums[j] 와 count가 맞는 숫자가 있는지 확인
break;
}
++count; // count = 2;
for (int j = 0; j < num-1; ++j) {
if (nums[j] == count)
break;
}
++count; // count = 3;
for (int j = 0; j < num-1; ++j) {
if (nums[j] == count)
break;
}
-------------------------생략-------------------------
++count; // count = 9;
for (int j = 0; j < num-1; ++j) {
if (nums[j] == count)
break;
}
++count; // count = 10;
for (int j = 0; j < num-1; ++j) {
if (nums[j] == count)
break;
}
이렇게 비교해서 숫자를 찾으려 합니다. 여기서 생각을 좀 더 해봅시다. 10번의 반복을 했는데 없는 수가 있는 반복문은 어떤 차이가 있을까요?
반복문이 끝난 직후에 아마도 int j 의 값이 혼자 num-1 일 것입니다. 반복문을 끝까지 검색했는데도 불구하고 맞는 숫자가 없어서 if 문에서 break로 빠져나오지 못한 것이죠. 그럼 int j의 값이 num-1인 반복문을 찾아보겠습니다.
int count = 1; // 임의의 변수를 1로 초기화
int j; // j 가 num-1인지 확인하기 위해 변수를 반복문 밖으로 빼냈습니다.
for (j = 0; j < num-1; ++j) { // 반복문을 돌려서 0번째 배열부터 8번째 배열까지 비교
if (nums[j] == count) // nums[j] 와 count가 맞는 숫자가 있는지 확인
break;
}
if (j == num-1) {
printf("%d", count);
return 0;
}
++count; // count = 2;
for (j = 0; j < num-1; ++j) {
if (nums[j] == count)
break;
}
if (j == num-1) {
printf("%d", count);
return 0;
}
++count; // count = 3;
for (j = 0; j < num-1; ++j) {
if (nums[j] == count)
break;
}
if (j == num-1) {
printf("%d", count);
return 0;
}
-------------------------생략-------------------------
++count; // count = 9;
for (j = 0; j < num-1; ++j) {
if (nums[j] == count)
break;
}
if (j == num-1) {
printf("%d", count);
return 0;
}
++count; // count = 10;
for (j = 0; j < num-1; ++j) {
if (nums[j] == count)
break;
}
if (j == num-1) {
printf("%d", count);
return 0;
}
자 이렇게 if문을 통해서 j가 num-1인 경우를 찾고, 찾으면 바로 printf로 출력을 하고 return 0;으로 프로그램을 종료하도록 했습니다. 사실 처리 이후에 출력 부분도 따로 정리를 하려 했는데 너무 간단하고 어렵지 않아서 이 후에 조금 더 어려운 문제를 정리하게 될 때 다시 설명드리도록 하겠습니다.
코드를 구현했습니다. 그런데 이렇게 끝내기는 뭔가 찝찝하지 않은가요? 물론 원하는 결과를 얻었다면 코드가 틀렸다고 말할 수는 없지만 위의 코드를 보고 있자면 뭔가 비효율적으로 작성된 것 같다는 생각이 들지 않나요? 🙄
다들 저와 같은 마음이실 거라 생각해서 찝찝한 이유를 한 번 찾아보겠습니다. 아마도 다들 눈치 채셨겠지만 특정 코드가 계속해서 반복하고 있습니다.
++count;
for (j = 0; j < num-1; ++j) {
if (nums[j] == count)
break;
}
if (j == num-1) {
printf("%d", count);
return 0;
}
바로 이 코드가 무려 10번이 똑같이 반복되고 있습니다. 차이는 count의 숫자가 점점 늘어났다는 것 외에는 차이가 없습니다. 코드가 이렇게 반복될 때 반복을 줄이기 위해서 사용하는 반복문에 대해서 생각이 나셨다면 아주 훌륭합니다. 반복문이 생각 안나셨다면 기초 반복문을 꼭 읽고 오세요. 반복문의 기본 구조 중에 증감이 있다는 거 기억하실 겁니다. 달라지는 저 count라는 변수를 i로 바꾸게 되면 뭔가 보이실까요?
int i = 0;
for (j = 0; j < num-1; ++j) {
if (nums[j] == count)
break;
}
if (j == num-1) {
printf("%d", count);
return 0;
}
++i;
for (j = 0; j < num-1; ++j) {
if (nums[j] == count)
break;
}
if (j == num-1) {
printf("%d", count);
return 0;
}
++i;
for (j = 0; j < num-1; ++j) {
if (nums[j] == count)
break;
}
if (j == num-1) {
printf("%d", count);
return 0;
}
---------------생략------------------
자 어떤 형태인가요 우리가 어렵게 생각했던 중첩 반복문을 쓰면 될 것 같지 않나요? 그렇습니다. 중첩 반복문은 사실 이렇게 하나씩 코드를 짜면서 바꿔가면서 구현하면 되는 겁니다. 그럼 한 번 우리가 바라는대로 바꿔보겠습니다. for문의 시작은 1부터 num까지 1씩 증가하면서 반복시키면 됩니다.
for (int i = 1; i <= num; ++i) {
int j;
for (j = 0; j < num-1; ++j) {
if (nums[j] == i)
break;
}
if (j == num-1) {
printf("%d", i);
return 0;
}
}
이렇게 보니 또 어렵게 보이시나요 😂 그렇지만 위에까지 이해하신 여러분은 충분히 이해할 수 있습니다.
처음부터 코드를 작성하는 순서와 방법, 아이디어까지, 또 반복되는 코드를 반복문으로 바꾸면서 간단하게 구현해보았습니다. 완성된 코드는 아래와 같습니다.
#include <stdio.h>
int main(void) {
int num;
scanf("%d", &num);
int nums[num-1];
for (int i = 0 ; i < num ; ++i)
scanf("%d", &nums[i]);
int i, j;
for (i = 1; i <= num; ++i) {
for (j = 0; j < num-1; ++j) {
if (nums[j] == i)
break;
}
if (j == num-1) {
printf("%d", i);
return 0;
}
}
return 1; // 빠진 코드가 없을 시 오류 코드 반환 // 생략 가능
}
끝!!!! 🤟이면 좋았겠지만 해욱씨의 요청에 따라 새로운 코드에 대한 해석도 해보겠습니다.
[번외] 요청 코드 해석! 👏
자 올려주신 코드를 해석해보겠습니다. 코드는 아래와 같습니다.
#include <stdio.h>
int main(void) {
int lose;
int num;
scanf("%d", &num);
int nums[50] = {};
for (int i = 0; i < num; ++i) {
nums[i] = i + 1;
}
for (int j = 0; j < num - 1; ++j) {
scanf("%d", &lose);
nums[lose - 1] = 0;
}
for (int k = 0; k < num; ++k) {
if (nums[k] != 0) {
printf("%d", nums[k]);
}
}
return 0;
}
여기서 요청받은 질문은 nums[lose-1] = 0 의 의미와 nums[k] != 0 의 의미입니다.
일단 코드를 나눠서 이해해보겠습니다.
#include <stdio.h>
int main(void) {
int lose;
int num;
scanf("%d", &num);
int nums[50] = {};
for (int i = 0; i < num; ++i) {
nums[i] = i + 1;
}
여기까지 살펴보면 변수는 lose, num이라는 정수타입을 선언했고, nums라는 배열을 선언했습니다. 저는 사실 여기서 조금 비효율적이라고 생각이 들었는데요. 이미 num의 숫자를 입력받아서 알고 있는데 50이라는 크기의 배열을 할당해놓는 것은 메모리 관리가 안되는 것이기 때문입니다. 우선은 코드를 해석하는 것이 우선이기에 넘어가도록 하겠습니다. 그리고 이어서 반복문으로 nums 배열에 1부터 num까지의 숫자를 넣습니다. 해당 코드까지 진행한 data 모습을 보여드리겠습니다.
.PNG)
여러분의 이해를 돕기 위해 C/C++ debugging 하는 방법을 열심히 찾아서 세팅해놓았습니다. 🤛
살펴보면 lose 변수에는 초기화가 안되어 있음을 알 수 있고 num는 10, nums에는 1부터 10까지 숫자가 차례대로 입력된 것을 볼 수 있습니다. 이제 다음 코드들을 살펴보겠습니다.
for (int j = 0; j < num - 1; ++j) {
scanf("%d", &lose);
nums[lose - 1] = 0;
}
j 는 0부터 num-1까지 반복됩니다. 여기서 scanf를 통해 입력을 받는데 입력받는 data는 lose 변수에 저장이 됩니다. 아마도 그럼 위의 예제에서 3 4 1 10 2 6 7 5 9 가 lose에 연속해서 입력이 되겠네요. 그리고 여기서 중요한 점! nums 배열에서 lose -1 번째 값을 0으로 치환합니다. 여기서 왜??라고 생각하시는 분들이 있으실 수도 있는데요.
위의 캡처 사진을 다시 한 번 살펴보겠습니다. 지금 nums의 인덱스에는 0번째에는 1, 1번째에는 2, 2번째에는 3… 이렇게 인덱스와 값이 1차이로 입력되어 있습니다. 그럼 정상적이라면 nums[lose-1] 값은 어떤 값이 들어가 있을까요? 바로 lose 값이 들어가 있을 것으로 예상할 수 있게 됩니다.
요약하자면 이미 차례대로 배열에 입력된 수 배열에서 입력되는 lose의 수에 해당되는 값이 0으로 치환된다라고 말할 수 있습니다. 진행되는 사진을 한 번 보겠습니다. 먼저 3을 입력했을 때 결과입니다.
.PNG)
3이 입력되면 lose-1은 2, nums의 2번째 배열 값 3이 0으로 치환되었습니다. 다음 4를 입력했을 때 결과입니다.
.PNG)
다음은 입력을 모두 받았을 때의 결과입니다.
.PNG)
이렇게 입력되지 않은 8을 제외한 모든 배열의 값들이 0으로 치환되었습니다. 이후의 코드는 어렵지 않겠죠? 바로 0이 아닌 수를 찾아서 반환하면 빠진 수를 찾을 수 있게 될 겁니다.
최대한 어렵지 않게 이해시켜드리려고 노력했는데 잘 이해되셨나요? 어려운 부분이 있었다면 댓글 남겨주시고 제가 혹시 설명 중 잘못된 부분이나 실수한 부분이 있으면 댓글 남겨주시면 바로 수정하거나 답변드리겠습니다! 다들 컨디션 조절 잘하시고 끝까지 열심히 공부해서 좋은 결과 있기를 바랍니다! 😄👏
댓글