배열과 리스트 (문제 001)

자료구조는 데이터를 효율적으로 저장, 접근, 수정하기 위한 그릇이다. 코테에서는 각 문제에 주어진 입력 데이터의 형태와 사용해야 하는 알고리즘에 따라 적절한 자료구조를 선정해 사용하는 것이 매우 중요하다. 

 

배열과 리스트

기본 자료구조인 배열과 리스트는 비슷하지만 다르 점도 많다. 두 자료구조의 특징을 정확하게 이해하고 문제가 요구하는 조건에 따라 적절하게 선택해 사용하는 것이 중요하다. 

 

배열과 리스트의 핵심 이론

 

배열

배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조이다. 배열의 값은 인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있다. 아래 그림은 배열을 나타낸 것이다. 그림을 보면 배열에 값 1, 값 2, ... 값 6이 채워져 있고, 각 값은 0부터 5까지 인덱스가 지정되어 있다. 

 

배열의 특징

1. 인덱스를 사용하여 값에 바로 접근할 수 있다.
2. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.
3. 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.
4. 구조가 간단하므로 코테에서 많이 사용한다.

 

리스트

리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조이다.

> 노드는 컴퓨터 과학에서 값, 포인터를 쌍으로 갖는 기초 단위를 부르는 말이다. 

리스트의 특징

1. 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야한다. 다시 말해 값에 접근하는 속도가 느리다.
2. 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다. 
3. 선언할 때 크기를 별도로 지정하지 않아도 된다. 다시 말해 리스트의 크기는 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰 때 적절하다.
4. 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다. 

 

문제 001. 숫자의 합 구하기 

N개의 숫자가 공백 없이 써 있다. 이 숫자를 모두 합해 출력하는 프로그램을 작성하시오.

 

입력
1번째 줄에 숫자의 개수 N(1 <= n <= 100), 2번째 줄에 숫자 N개가 공백없이 주어진다. 

출력
입력으로 주어진 숫자 N개의 합을 출력한다.

 

이 문제는 유튜브 온라인 강의로 풀이법이 올라와있다. 

이 문제를 강의로 선택한 이유는 "코테에서 꼭 들여야하는 습관"을 알려주기 위해서라고 한다.

 

문제를 바로 풀려고 하지말고 꼼꼼하게 문제에 조건을 파악한 후에 방향을 설정해야한다.

초기 방향을 제대로 설정하지 않았을때, 이걸 다시 짜는 건 불가능하다.

처음부터 문제 내용을 꼼꼼히 분석하고 비로소 코딩을 해야한다.

 

손으로 문제를 어느정도 상상을 해봤다가 코드를 짜는게 좋다.

일단 여기서 첫번째 주의점.

<n이 100이다> 라는 것은 숫자의 자리수(개수)가 100이라는 건데, 이는 int나 long으로 받을 수 없다는 것을 알아차려야한다. > int나 long으로 받을 수 없다? 그러면 String 으로 받을 수 있다는 것을 떠올림. 

* 이걸 근거로 문제를 좀더 세부적으로 분석해나가면, 보다 좋은 로직이 나올 수 있다. 

 

1단계 문제 분석하기

N의 범위가 1부터 100까지이므로 값은 int형, long형과 같은 숫자형으로 담을 수 없을 정도로 크다. 이때 생각나와야 하는 게 String이다. 먼저 문자열 형태로 입력값을 받은 후 이를 한글자씩 문자 배열로 변환하고. 문자 배열값을 순서대로 읽으면서 숫자형으로 다시 변환해서 더해야한다. 가령, 입력값이 "1234"와 같은 문자열로 입력 받은 후에 이를 다시 '1', '2', '3', '4'와 같이 문자 배열로 변환하고, 다시 문자 배열을 1, 2, 3, 4로 변환한 다음 더해 10을 구하는 것이다. 

 

> 단, 문자열을 숫자형으로 변경하려면 아스키코드를 이해하고 있어야한다. 

아스키코드에서 같은 의미의 문자와 숫자의 코드 값 차이는 48이다. 예를 들어 문자 '1'은 아스키코드 값으로는 49이으모

문자 '1'을 숫자 1로 변환하려면 '1' - 48 또는 '1' - '0'으로 연산하면 된다. (실제 코드상에서도 '0'을 빼주거나 48을 빼주면 된다)

 

2단계 손으로 풀어 보기

1) 숫자의 개수만큼 입력받은 값을 String형으로 저장한다. 

 

String sNum = 10987654321

 

2) String형으로 입력받은 값을 char[]형으로 변환한다.

 

char 1 / 0 / 9 / 8 / 7 / 6 / 5 / 4 / 3 / 2 / 1

 

3) 인덱스 0부터 끝까지 배열을 탐색하며 각 값을 정수형으로 변환하고 결괏값에 더하여 누적한다.

 

index   0   1   2   3   4   5   6   7   8   9  10
char     1 / 0 / 9 / 8 / 7 / 6 / 5 / 4 / 3 / 2 / 1
------------------------------------------------------> 인덱스 0부터 10까지 정수형으로 변환, 결괏값 누적하여 더하기

 

3단계 슈도코드 작성하기

N값 입력받기
길이 N의 숫자 입력받아 String형 변수 sNum에 저장하기 
sNum을 다시 char []형 변수 cNum에 변환하여 저장하기
int형 변수 sum 선언하기
for(cNum 길이만큼 반복하기)
{
 배열의 각 자릿값을 정수형으로 변환하여 sum에 더하여 누적하기
}
sum 출력하기

 

4단계 코드 구현하기

해설지를 안보고 구현해본 코드

 

내가 틀린 지점은 String 변수를 스캐너로 입력 받아 저장할때 sc.nextInt(); 로 받은 것. 

처음엔 nextInt();로 코드를 치니까 에러가 떴다. 왜? 

String 변수를 스캐너로 입력받으려면 next(); 혹은 nextLine()으로 받아야 한다. 

 

 

※ next() 개행문자를 무시하고 입력을 받음, 즉 숫자를 치고 엔터를 누를경우 엔터 전까지만 입력을 받음.

※ nextLine() 한줄 단위로 입력 받기 때문에, 개행문자도 한 줄로 인식합니다.

 

아래는 강의를 들으면서 코드를 한줄 한줄 해설과 함께 따라 쓴 것. 

 

 

(익혀둘 것) 자바에서의 형 변환

문제 1번 해설과 답 드디어 끝..!