알고리즘 풀어보기
과일장수
내가 생각한 풀이
- score를 내림차순으로 정렬한다. (비싼것들끼리 묶어서 먼저 판매)
- 임시로 저장할 List를 만들어서 score를 복사한다. (인덱스로 값을 지워주기 위해서)
- while문을 써서 newscore의 길이가 m보다 작지 않을 때까지 (newscore/m이 0보다 작아지면 포장 못함) answer에 m개째의 k에 갯수 m을 곱한 값을 더해준다. (제일 점수 낮은 사과*갯수)
- 방금 포장한 사과를 리스트에서 지워준다.
using System;
using System.Linq;
using System.Collections.Generic;
public class Solution {
public int solution(int k, int m, int[] score) {
int answer = 0;
score = score.OrderByDescending(x=>x).ToArray();
List<int> newscore = new List<int>(score);
while(newscore.Count/m>0){
answer+=newscore[m-1]*m;
newscore.RemoveRange(0,m);
}
return answer;
}
}문제 발생 : 시간초과
숫자가 엄청 커지면서 while에서 시간을 많이 쓰는 모양이다.
트러블 슈팅
while문을 돌리면서 RemoveRange()도 리소스를 많이 잡아먹을테니, 굳이 제거하지말고 인덱스를 바꿔가면서 더해보자.
using System;
using System.Linq;
using System.Collections.Generic;
public class Solution {
public int solution(int k, int m, int[] score) {
int answer = 0;
score = score.OrderByDescending(x=>x).ToArray();
for (int i =m-1;i<score.Length;i+=m){
answer+=score[i]*m;
}
return answer;
}
}- 내림차순으로 정렬한다.
- i가 m-1(m은 1부터 시작하고, 인덱스는 0부터 시작한다.)로 시작하고, 다음 i는 m만큼 증가한다.
- i번째 스코어(최저점)*갯수 한 값을 answer에 더해준다.
리소스를 많이 잡아먹는 부분을 제거하면 시간초과 오류는 발생하지 않는다.
주의할 점
기능적으로 편한 것들은 뒤에서 돌아가는게 많아서 리소스를 많이 잡아먹는다.
while을 돌린다거나 for문을 많이 돌린다고해서 무조건 시간이 오래 걸리는게 아니니
그런 부분을 고려하면서 작성해보자.
모의고사
풀이
간단하게 할 방법은 생각이 안나서,
1. 각 수포자별 int 배열과 맞은 정답수를 저장할 int 변수를 만든다.
2. 먼저 각 수포자별 제출할 문제들을 배열만큼 생성한다. 생성하면서 정답과 비교해서 동일하면 변수를 ++해준다.
3. 각 정답수를 한 배열로 뭉치고, 정렬을 해서 제일 큰 값을 저장한 후, 이를 기준으로 각 수포자의 정답수와 비교하여 answer에 더해준다. (문제에서는 int[]이지만 편의를 위해 List로 변경함)
using System;
using System.Linq;
using System.Collections.Generic;
public class Solution {
public List<int> solution(int[] answers) {
List<int> answer = new List<int>();
int[] _1correct=new int[answers.Length];
int[] _2correct=new int[answers.Length];
int[] _3correct=new int[answers.Length];
int _1cor=0;
int _2cor=0;
int _3cor=0;
int a=1;
for (int i=0;i<answers.Length;i++){
_1correct[i]= i%5 ==0 ? 1 : i%5+1;
if (_1correct[i]==answers[i])
_1cor++;
}
for (int i=0;i<answers.Length;i++){
int temp;
if (i%2==0)
_2correct[i]= 2;
else{
_2correct[i]= a;
if (a==1)
a=3;
else if (a==5)
a=1;
else
a++;
}
if (_2correct[i]==answers[i])
_2cor++;
}
for (int i=0;i<answers.Length;i++){
int[] temp = {3,3,1,1,2,2,4,4,5,5};
_3correct[i]=temp[i%10];
if (_3correct[i]==answers[i])
_3cor++;
}
int[] arr = new int[3]{_1cor,_2cor,_3cor};
arr = arr.OrderBy(x=>x).ToArray();
int high = arr[2];
if (_1cor==high)
answer.Add(1);
if (_2cor==high)
answer.Add(2);
if (_3cor==high)
answer.Add(3);
return answer;
}
}소수 만들기 
풀이
- 먼저 3개의 수를 뽑아야하기 때문에 for문을 3중으로 써서 nums에서 3개의 수를 뽑는 경우의 수를 구성했다.
- 맨 안쪽에 for문을 한 개 더 작성해서, 3개의 수를 더한 수가 l로 나눴을 때 나머지가 0이 되는 때가 몇번인지 구한다.
- 만약 나머지가 0이 되는 때가 2번이라면, answer++해준다.
using System;
class Solution
{
public int solution(int[] nums)
{
int answer = 0;
for (int i = 0; i < nums.Length; i++)
{
for (int j = i + 1; j < nums.Length; j++)
{
for (int k = j + 1; k < nums.Length; k++)
{
int temp = 0;
for (int l = 1; l <= nums[i] + nums[j] + nums[k]; l++)
{
if ((nums[i] + nums[j] + nums[k]) % l == 0)
temp++;
}
if (temp == 2)
answer++;
}
}
}
return answer;
}
}덧칠하기
문제 링크 : 내 깃허브
풀이
앞에서부터 해당하는 부분이 있으면 m만큼 칠하고, 그 범위 안에 있는 section의 수를 section 배열에서 제거하는 방식으로 진행했다. 밑에 나올 코드는 통과 못한 코드다.
1. for문을 벽의 길이만큼 돌리면서, 벽 i가 칠해야할 section에 있는 지 찾아본다.
2. 만약 벽 i가 칠해야할 섹션이라면, 다시 for문을 써서 시작 위치부터, 다음 칠해야할 위치까지 지워준다. (여기서는 n을 얘기하지만, n이 배열이 아니라 그냥 int다.)
3. answer++해주고 다시 반복한다.
using System;
using System.Linq;
public class Solution {
public int solution(int n, int m, int[] section) {
//n = 벽전체길이(칸당 1미터),m = 롤러 크기,section = 칠할 곳
int answer = 0;
for (int i = 0; i <= n; i++)
{
int newsection = 0;
int find = Array.IndexOf(section, i+1);
if (find != -1)
{
newsection = i + m - 1;
for (int j = i; j <= newsection; j++)
{
section = section.Where(num => num != j).ToArray();
}
answer++;
}
}
return answer;
}
}문제 발생 : 시간 초과 + 인지부조화
뭐가 뭔지도 모르고 for문과 Linq를 남발하다보니 오류는 안나는데 돌아가지도 않는 코드가 되버렸다.
트러블 슈팅
큰 틀은 바뀌지 않고, section에서 내가 칠해야 할 부분을 지워주는 방식만 바꾸었다.
using System;
using System.Linq;
public class Solution {
public int solution(int n, int m, int[] section) {
//n = 벽전체길이(칸당 1미터),m = 롤러 크기,section = 칠할 곳
int answer = 0;
int k=0;
for (int i = 0; i <= n; i+=k)
{
int newsection = 0;
int find = Array.IndexOf(section, i+1);
if (find != -1)
{
newsection = i + m - 1;
section = section.Where(num => num > newsection).ToArray();
answer++;
k=m;
}
else k=1;
}
return answer;
}
}여기서 k는 다음의 시작 인덱스를 결정한다. 만약 벽을 칠했을 경우, m만큼 증가하고, 아닐 경우 다음 인덱스를 찾는다.
그리고 where을 사용했는데, 이 안에 조건식은 조건에 맞는 내용만 남기고 나머지는 제거한다.
여기서 사용된 조건은 이미 칠해진 벽보다 다음에 있는 섹션만 남기는 것이다.
(람다식 참고 (좀 응용했음) : 삽질 없는 개발은 없다)
기사단원의 무기 
풀이
- number까지 숫자별로 약수의 개수를 구한다.
- 구한 약수의 개수를 비교해 limit을 넘으면 power만큼, 아니면 그 수만큼 answer에 더한다.
using System;
public class Solution {
public int solution(int number, int limit, int power) {
//number까지 차례대로 약수를 구해서 필요한 철의 무게를 계산해야됨.
int[] numbers= new int[number];
for (int i =0; i<number;i++){
for (int j=1;j<=i+1;j++){
if ((i+1)%j==0)
numbers[i]++;
}
}
int answer = 0;
foreach (int i in numbers){
if (i>limit)
answer+=power;
else answer+=i;
}
return answer;
}
}문제 발생 : 시간초과
수가 100,000까지라 조건으로 약수의 개수가 limit을 넘어가면 break 하도록 걸어도 시간초과가 발생했다. 몇시간 끙끙대다 시간초과라 너무 억울해서 다른 풀이를 참고했다.트러블 슈팅
(참고 : jyp의 게임 프로그래밍 가이드)
여기서는 약수의 갯수를 구하는 것이 아니라, i를 가지고 있는 약수의 카운트를 ++해주는 방식으로 약수의 개수를 산출해냈다.
using System;
public class Solution {
public int solution(int number, int limit, int power) {
int answer = 0;
int[] numCnt = new int[number+1] ;
//number까지 차례대로 약수를 구해서 필요한 철의 무게를 계산해야됨.
for (int i =1; i<=number;i++){
for (int j=i;j<=number;j+=i) //i의 배수들에게 카운트++
numCnt[j]++;
}
}
foreach (int i in numCnt){
if (i>limit)
answer+=power;
else answer +=i;
}
return answer;
}
}정리
내꺼도 나쁜 방법은 아니라고 생각했는데, 머리는 굴리기 나름인가보다. 근데 이 방법은 아예 생각이 안났다. 코딩 테스트 할 때는 안 하더라도 역시 구글링이 좋다.
로또의 최고 순위와 최저 순위
풀이
- 먼저 표시되어 있는 수 중에 맞는 수의 개수와, 0이 개수를 구했다.
int Cnt=0;
int zero=0;
for (int i =0;i <lottos.Length;i++){
if (lottos[i]==0)
zero++;
}
foreach(int i in lottos){
int isin = Array.IndexOf(win_nums,i); //당첨 번호에 존재하면 Cnt++;
if (isin != -1)
Cnt++;
}- 최고 등수는 Cnt+zero의 갯수이고, 최저 등수는 Cnt의 갯수이다. (최고 : zero도 다 맞는거 처리) 여기서는 switch문을 이용해 추가해주었다.
using System;
public class Solution {
public int[] solution(int[] lottos, int[] win_nums) {
int[] answer = new int[2];
int Cnt=0;
int zero=0;
for (int i =0;i <lottos.Length;i++){
if (lottos[i]==0)
zero++;
}
foreach(int i in lottos){
int isin = Array.IndexOf(win_nums,i);
if (isin != -1)
Cnt++;
}
switch (Cnt+zero){
case 2:
answer[0]=5;
break;
case 3:
answer[0]=4;
break;
case 4:
answer[0]=3;
break;
case 5:
answer[0]=2;
break;
case 6:
answer[0]=1;
break;
default :
answer[0]=6;
break;
}
switch (Cnt){
case 2:
answer[1]=5;
break;
case 3:
answer[1]=4;
break;
case 4:
answer[1]=3;
break;
case 5:
answer[1]=2;
break;
case 6:
answer[1]=1;
break;
default :
answer[1]=6;
break;
}
return answer;
}
}정리
좀 지저분해 보이긴 하지만, 나름 편하다. 해온게 깔끔하진 않지만, 알고리즘이라고 굳이 짧게 만들어야 된다는 법은 없으니까 리소스를 적게 먹는 편으로 작성해보자.
옹알이(2) - 5시간 걸림
처음 생각한 풀이
뭔가 더해서 babbling이랑 비교하기에는 경우의 수가 너무 많을 것 같아서 빼는 방식으로 만들어보았다.
for문으로 babbling 전체에서 말할 수 있는 단어가 나오면 그 단어 시작 지점에서 길이만큼 삭제하도록 작성해주었다.
using System;
public class Solution {
public int solution(string[] babbling) {
//"aya", "ye", "woo", "ma" 이거 네개밖에 못함.
int answer = 0;
string[] canSpeak = {"aya", "ye", "woo", "ma"};
for (int i =0; i<babbling.Length;i++){
int a = babbling[i].IndexOf(canSpeak[0]);
if (a!=-1)
babbling[i] = babbling[i].Remove(a,canSpeak[0].Length);
int b = babbling[i].IndexOf(canSpeak[1]);
if (b!=-1)
babbling[i] = babbling[i].Remove(b,canSpeak[1].Length);
int c = babbling[i].IndexOf(canSpeak[2]);
if (c!=-1)
babbling[i] = babbling[i].Remove(c,canSpeak[2].Length);
int d = babbling[i].IndexOf(canSpeak[3]);
if (d!=-1)
babbling[i] = babbling[i].Remove(d,canSpeak[3].Length);
}
foreach(string s in babbling){
if (s=="")
answer++;
}
return answer;
}
}문제 발생
중복 예외처리가 안된다. 이거 만들 때까지는 예외 처리 방법도 생각 안났다.
두 번째 풀이
- 여러 조건을 걸고, for문으로는 babbling 안의 문자열들을 차례로 불러오고, while문을 통해 문자열을 분해하는 동작을 수행했다.
- 조건을 풀어보자면, temp는 바로 전에 쓴 단어는 연속으로 못 쓰게 하기 위해서 작성되었고, IndexOf는 예시의 'maa' 같은 경우에 ma가 지워져도 a가 남기 때문에 case 'a'가 돌아갈 것을 예외처리 하기위해서 작성되었다.
- 만약 조건을 만족하지 못하거나, case 밖의 문자가 나오면 while을 탈출한다.
- 지워진 문자열이 공백일 때, answer++해준다.
using System;
public class Solution {
public int solution(string[] babbling) {
//"aya", "ye", "woo", "ma" 이거 네개밖에 못함.
int answer = 0;
string[] canSpeak = { "aya", "ye", "woo", "ma" };
for (int i = 0; i < babbling.Length; i++)
{
bool isgoing = false;
char temp='q';
while (!isgoing)
{
switch (babbling[i] == "" ? 'q' : babbling[i][0])
{
case 'a':
if (temp != 'a' && babbling[i].IndexOf(canSpeak[0])!=-1)
babbling[i] = babbling[i].Remove(0, canSpeak[0].Length < babbling[i].Length ? canSpeak[0].Length : babbling[i].Length);
else isgoing = true;
temp = 'a';
break;
case 'y':
if (temp!='y'&& babbling[i].IndexOf(canSpeak[1]) != -1)
babbling[i] = babbling[i].Remove(0, canSpeak[1].Length < babbling[i].Length ? canSpeak[1].Length : babbling[i].Length);
else isgoing = true;
temp = 'y';
break;
case 'w':
if (temp != 'w'&& babbling[i].IndexOf(canSpeak[2]) != -1)
babbling[i] = babbling[i].Remove(0, canSpeak[2].Length < babbling[i].Length ? canSpeak[2].Length : babbling[i].Length);
else isgoing = true;
temp = 'w';
break;
case 'm':
if (temp != 'm'&& babbling[i].IndexOf(canSpeak[3]) != -1)
babbling[i] = babbling[i].Remove(0, canSpeak[3].Length < babbling[i].Length ? canSpeak[3].Length : babbling[i].Length);
else isgoing = true;
temp = 'm';
break;
default:
isgoing = true;
break;
}
}
}
foreach (string s in babbling)
{
if (s == "")
answer++;
}
return answer;
}
}문제 발생
테스트에서 한 개가 불통임. 그래서 튜터님께 들고갔다.
튜터님이 말하길
자주 나오는 친구는 변수로 저장하고 사용
-> babbling 변수를 바꿔야되서 변수로 저장하니까 안되더라
바꾸기 할 때는 컨트롤 에프 -> ctrl+r+r이랑은 다른데 좋음
인덱스오브부터 좀 그럼. -> 좋은 기능은 아닌가봄
aaya 경우 조건도 다 만족하지만 이상한데서 짤림 -> 이게 중요했다.
aaya면 indexof도 만족하는데 1번~3번까지 지워져야되는데 0~2번까지 지워지기 때문에 오류가 발생했을 것이다.
그래서 이 부분을 수정해서 작성해보았다.
최종 수정
(참고 : Substring Devstory)
if (temp != 'a' && babbling[i].IndexOf(canSpeak[0])!=-1)
=> if (temp != 'a' && babbling[i].Substring(0, canSpeak[0].Length < talk.Length ? canSpeak[0].Length : talk.Length) == canSpeak[0])
조건이 더 추가되었는데, 기존에는 원래 있던 문자열 전체에서 찾지만, 최종에서는 문자열을 각 문자에 해당하는 문자열 크기만큼 분리해서 비교한다.
만약 남은 문자열의 길이가 충분치 않다면, 남은 부분만큼 가져와서 비교하게 되는데,
보통 이 경우에는 조건이 맞지 않기때문에 while문이 끝난다.
발표회 피드백 정리
- 클래스를 파일별로 분리
- goto 코드는 사용 안하는게 좋다.
- 파고드는 if문 있으면 디버깅할 때 좋지 않음.
- 스트링빌드 쓰는거 좋음. (글자 한 글자씩 출력 되는 거)
- 이거 한번쓸거같은데? 하는 애들도 메서드로 묶어주는게 좋다.
- 리스너 활용해 업적구현한 거 잘했다. 다른 조도 훔쳐쓰면 좋겠다. (4조)
- 우리조 피드백
컨벤션 맞췄는데 좀 들쭉날쭉함.
_는 보통 프라이빗에 붙이는게 컨벤션, 아무데나 붙이면 안된다.
region을 사용한 건 잘했지만 이름을 왜 안달았을까.
파일 이름 본인 이름으로 하지말기 - 내 이야기
나중에 해볼 것
- 키보드로 선택하는거 신기한데 나중에 알아보자
- 하드코딩이 뭘까
- 4조의 리스너 알아보기
특강 - 좋은 개발자의 비밀
개발자로서 동기부여 될 수 있는 시간
제목 : 좋은 개발자? 좋은 정체성!
개발자에 대한 정의
개발자 = 회사원 ? No
정체성
개발자이면서 다양한 모습으로 살아가는 것이 가능
직업이 아니라 나의 정체성이다.
지금 나의 모습 = 선택+환경
요약
개발자로 취업을 한다고해서 내가 직장인이라고 생각하는 것보다 여러 가능성을 열어두고 다음을 탐구하자. 사실 알고리즘 푼다고 잘 못 들었다.
내일 할 일
- 알고리즘 풀기
- 유니티 발제듣고 개인과제 시작하기
아마 두개하면 시간 안 남을 듯
