* 유진호님 감사합니다. =)
출처 :
http://www.csharpstar.com/top-20-googl ··· tions%2F알고리즘 문제 Top20개인데, 풀이 결과는 별거 없는데... 용어가.. 좌절스럽습니다.
일단 문제 옮겨 놓고 용어부터 풀어야 겠네요.
1. Given an unsorted array which has a number in the
majority (a number appears more than 50% in the array), find that number?
2. How to detect a
cycle in singly linked list?
3. How to merge two sorted linked list, write a program in your favorite programming language i.e. Java,C#
4. Write a Program which checks if two Strings are
Anagram or not?
5. How to swap two numbers without using a temp variable, write code which is free from Integer overflow?
6. How to find all pairs of elements in an integer array, whose sum is equal to a given number?
7. Write a function to print nth number in
Fibonacci series?
8. Write a function to count a total number of set bits in a 32 bit Integer?
9. Write a function to remove duplicate characters from String?
10. How to find the 3rd element from end, in a singly linked, in a single pass?
11. How to calculate
factorial using recursion in C#?
12. C# program to check if a number is
Armstrong number or not?
13. Algorithm to check if a number is
Prime or not?
14. Algorithm to check if a number is
Palindrome?
15. Algorithm to find if Array contains duplicates?
16. Write code to reverse a linked list, if you able to do it using loops, try to solve with recursion?
17. How to rotate an array by a given pivot ?
18. How to remove duplicates from a sorted linked list?
19. How to find sum of digits of a number using Recursion?
20. Sorting an Array using
Selection Sort 흐미... -_-;; 용어 몰라서 문제 못풀뻔 했네요.
(물론 불러줘야 인터뷰를 볼 수 있겠지만....)
용어정의부터
* a number in the Majority : 50%이상을 차지하는 수입니다.
예를 들면, {1,2,3,4,5,2,2,2,2} 에서 2가 Majority 수가 되겠군요. 간단히 Linq로 해결할 수 있을거 같네요.
* cycle in singly linked list 는 순환 연결리스트 같네요.
* Anagram은 이전에서 다뤘던 앞으로 읽어도 뒤로 읽어도 같은 문자입니다.
* Fabonacci 수열이 있네요.
파보나치 수열은 간단히 예로 들면 0, 1, 1, 2, 3, 5, 8, 13... 과 같이 바로 앞의 숫자와 현재 숫자를 더한 결과입니다.
* Factorial 을 계산하라네요. 팩토리얼은 예를 들어 3i = 3*2*1 = 6 (고딩때 수학이... 으으으)
* 암스트롱 넘버는 의외인데, 찾아보니 153 = 1^3 + 5^3 + 3^3 = 153 처럼 abc = a^n + b^n + c^n = x 로 n은 자릿수입니다.
* Prime number 는 영원한 수학계의 숙제인 자신외에는 나눌 수 있는 수가 없는 소수입니다.
* Palindrome number는 anagram하고 똑같이 숫자 131, 121, 22, 11 같은 수로 꺼꾸로 읽어도 같은 수가 됩니다.
만드는 공식은 "처음수+꺼꾸로한수"로 72 + 27 = 99 가 되는 수입니다.
* Selection Sort는 지난 포스팅에서 했던 배열 정렬 방법중 하나인데, 선택정렬이군요.
1. {1,2,3,4,5,2,2,2,2} 이 주어졌을때 2가 나오면 되는거네요.
static void Main(string[] args)
{
int[] _x = new int[]{ 1, 2, 4, 6, 5, 2, 2, 2, 2 };
var query = _x.GroupBy(x => x).Select(x => new { Key = x.Key, count = x.Count() }).ToList(); //Linq로 먼저 Groupby해서 카운트를 구합니다.
var isMajority = query.Find(x => x.count >= _x.Length / 2); //배열의 길이의 50%가 넘게 차지하는 수를 찾습니다.
string result = (isMajority == null) ? "Not Found" : isMajority.Key.ToString();
Console.WriteLine(result);
Console.ReadLine();
}
2. 싱글 링크드 리스트에서 순환되는 링크드 리스트를 찾으란 말인즉슨 Child node 가 null이 있으면 순환이 아니고, null이 없으면 Loop돈다는 뜻입니다.
따라서, Linked class를 만들어서 확인해보면 되겠네요.
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
namespace TestCode
{
class Program
{
static private Node head;
static void Main(string[] args)
{
List<Node> _LinkedList = new List<Node>();
MakeLinkedList(ref _LinkedList, 0);
MakeLinkedList(ref _LinkedList, 1);
MakeLinkedList(ref _LinkedList, 2);
MakeLinkedList(ref _LinkedList, 3);
SetCheck(_LinkedList); //정작 사용하는건 요거 하나 입니다. -_-;;
MakeLoopList(_LinkedList);
SetCheck(_LinkedList);
Console.ReadLine();
}
static void SetCheck(List<Node> _LL)
{
var result = _LL.Find(a => a.Child == null);
if (result == null) Console.WriteLine("Loop Linked List : True"); else Console.WriteLine("Loop Linked List : false");
}
#region for Make Linked List
static void MakeLinkedList(ref List<Node> _LL, int value)
{
if (head == null) AddFirst(ref _LL, value);
else
{
Node _node = new Node { value = value, Child = null };
_LL.Add(_node);
Node _current = head;
while (_current.Child != null)
{
_current = _current.Child;
}
_current.Child = _node;
}
}
static void AddFirst(ref List<Node> _LL, int value)
{
Node _Head = new Node { value = value, Child = null };
_LL.Add(_Head);
head = _Head;
}
#endregion
static void MakeLoopList(List<Node> _LL)
{
_LL.Find(a => a.value == 3).Child = head;
}
public class Node
{
public int value;
public Node Child;
}
}
}
3번은 좀 멘붕이네요. 2개의 Sort된 Linked List를 Merge하라니... OTL... 뭐 암튼 이건 2번 문제 응용으로 Value를 비교하여 Node를 연결하면 해결되지 않을까? 합니다.
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
namespace TestCode
{
class Program
{
static private Node head;
static void Main(string[] args)
{
//Linked list를 먼저 만듭니다.
List<Node> _LinkedListA = new List<Node>();
MakeLinkedList(ref _LinkedListA, 0);
MakeLinkedList(ref _LinkedListA, 1);
MakeLinkedList(ref _LinkedListA, 2);
MakeLinkedList(ref _LinkedListA, 3);
List<Node> _LinkedListB = new List<Node>();
MakeLinkedList(ref _LinkedListB, 1);
MakeLinkedList(ref _LinkedListB, 3);
MakeLinkedList(ref _LinkedListB, 5);
MakeLinkedList(ref _LinkedListB, 6);
//Merge할 List를 만들고,
List<Node> _MergeList = new List<Node>();
//Merge합니다.
MergeLinkedList(_LinkedListA, _LinkedListB, ref _MergeList);
Console.ReadLine();
}
//하나로 모아서 Sort한 뒤에 LinkedList를 생성합니다.
static void MergeLinkedList(List<Node> _A, List<Node> _B, ref List<Node> _C)
{
ArrayList A = new ArrayList();
foreach(Node x in _A) A.Add(x.value);
foreach (Node x in _B) A.Add(x.value);
A.Sort();
foreach (int x in A) MakeLinkedList(ref _C, x);
}
#region for Make Linked List
static void MakeLinkedList(ref List<Node> _LL, int value)
{
if (head == null) AddFirst(ref _LL, value);
else
{
Node _node = new Node { value = value, Child = null };
_LL.Add(_node);
Node _current = head;
while (_current.Child != null)
{
_current = _current.Child;
}
_current.Child = _node;
}
}
static void AddFirst(ref List<Node> _LL, int value)
{
Node _Head = new Node { value = value, Child = null };
_LL.Add(_Head);
head = _Head;
}
#endregion
static void MakeLoopList(List<Node> _LL)
{
_LL.Find(a => a.value == 3).Child = head;
}
public class Node
{
public int value;
public Node Child;
}
}
}
4. Anagram 문자열 비교는 이전 포스팅
http://www.wolfpack.pe.kr/920 문제 5번과 동일합니다.
5. 2개의 숫자를 바꾸는 것인데, 임시 변수 사용하지말고 하라니 쬐끔 황당하긴하네요.
만약 A=200 이고 B=100이라면 2개 수의 합은 300이 됩니다. 300을 A에 저장해놓고, A에서 B를 빼면 200, 이걸 B에 할당한뒤에 다시 300에서 B를 빼면 100 올ㅋ~
따라서, 공식은
A = A + B;
B = A - B;
A = A - B;
static void Main(string[] args)
{
int A = 100;
int B = 200;
A = A + B;
B = A - B;
A = A - B;
Console.WriteLine(A.ToString());
Console.WriteLine(B.ToString());
Console.ReadLine();
}
6. 쉬운 단어들 조합인데 해석이 제대로 안되서 까다로운 문제네요. 주어진 값이 나올수있는 배열안 2개의 원소 합을 구하라는 건데.. 간단히 TEST CASE를 작성하면,
{1,2,3,4} 라는 배열이 있다면 5가 나오는 합은 1, 4 / 2, 3 입니다. 6이 나오는 합은 2, 4가 되겠지요?
그냥 For 문 노가다입니다.
static void Main(string[] args)
{
int[] arrayInt = new int[] { 1, 2, 3, 4, 5 };
Console.WriteLine(SearchElement(arrayInt, 3));
Console.ReadLine();
}
static bool SearchElement(int[] _arr, int x)
{
for (int i = 0; i < _arr.Length; i++)
{
for (int y = 0; y < _arr.Length; y++)
{
if (i == y) continue;
if (i + y == x) return true;
}
}
return false;
}
7. 파보나치 수열은 위에 용어정의에서 이미 터치하고 왔습니다. 뭐.. 이것도 별건 없습니다. x = n-1 + n-2 단, 0과 1은 그대로 찍어주면 될 일 같습니다.
Arraylist로 간단히 해결가능할 거 같네요.
static void Main(string[] args)
{
ArrayList _ar = new ArrayList();
SetFibonacci(_ar, 12);
foreach (int x in _ar)
Console.Write(x + " ");
Console.ReadLine();
}
static void SetFibonacci(ArrayList ar, int x)
{
for (int i = 0; i < x; i++) {
if (ar.Count < 1) { ar.Add(i); continue; }
if (ar.Count < 2) { ar.Add(i); continue; }
ar.Add((int)ar[i-2] + (int)ar[i-1]);
}
}
8.번 문제는 32비트 int형의 bit 카운트 하라는 것같습니다. =)
이건 간단하게 10진수를 2진수로 변환하고나서 1의 갯수를 세면 bit 카운트가 됩니다. -_-;;
static void Main(string[] args)
{
int x = 512;
string bit = Convert.ToString(x, 2); //int.MaxValue 로 대체하면 31이 나와야 합니다. 32비트 int형이니까요...
int cnt = 0;
for (int i =0; i < bit.Length; i++)
{
if (bit[i].ToString() == "1") cnt++;
}
Console.WriteLine(cnt);
Console.ReadLine();
}
9.번은 스트링에서 중복되는 문자열을 제거하는 겁니다. Linq로 간단히 합의 볼 수 있는 수준입죠.
static void Main(string[] args)
{
string x = "aabcded"; //기대결과값은 abcde
var result = x.Distinct().ToArray();
Console.WriteLine(new string(result));
Console.ReadLine();
}
10번은 끝에서 3번째 Element를 찾는 문제네요. 이제 슬슬 LinkedList는 지겨워 지려합니다. 2번 코드 재활용해서 만들어 볼께요.
그런데 끝은 어떻게 찾느냐? 간단히 child가 null인 녀석을 찾고 그 걸 child로 가지고 있는걸 찾고, 다시 그걸 child로 가진걸 찾고... 3번 반복하면 되겠네요.
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
namespace TestCode
{
class Program
{
static private Node head;
static void Main(string[] args)
{
List<Node> _LinkedList = new List<Node>();
MakeLinkedList(ref _LinkedList, 0);
MakeLinkedList(ref _LinkedList, 1);
MakeLinkedList(ref _LinkedList, 2);
MakeLinkedList(ref _LinkedList, 3);
//마지막 노드 찾는건 Lambda 함수로 Child가 null인 걸 찾으면 끝!
Node LastNode = _LinkedList.Find(x => x.Child == null);
Node findedNode;
FindNode(_LinkedList, LastNode, 2, out findedNode);
Console.Write(findedNode.value);
Console.ReadLine();
}
//여기서 재귀함수 Recursive 로 돌려주면서 1씩 까나갑니다.
static void FindNode(List<Node> LL, Node current, int n, out Node finded)
{
if (n == 0) { finded = current; return; }
Node parent = LL.Find(x => x.Child == current);
FindNode(LL, parent, n - 1, out finded);
}
#region for Make Linked List
static void MakeLinkedList(ref List<Node> _LL, int value)
{
if (head == null) AddFirst(ref _LL, value);
else
{
Node _node = new Node { value = value, Child = null };
_LL.Add(_node);
Node _current = head;
while (_current.Child != null)
{
_current = _current.Child;
}
_current.Child = _node;
}
}
static void AddFirst(ref List<Node> _LL, int value)
{
Node _Head = new Node { value = value, Child = null };
_LL.Add(_Head);
head = _Head;
}
#endregion
static void MakeLoopList(List<Node> _LL)
{
_LL.Find(a => a.value == 3).Child = head;
}
public class Node
{
public int value;
public Node Child;
}
}
}
11번 문제는 재귀함수로 팩토리얼 구하는 문제입니다. 3i이라면 3*2*1 = 6 이 나오면 되는 문제입니다.
static void Main(string[] args)
{
Console.WriteLine(Factorial(4));
Console.ReadLine();
}
static int Factorial(int x)
{
if (x == 1) return x;
return Factorial(x - 1) * x;
}
12번 문제는 암스트롱 수가 맞는지 확인하는거 같네요. 공식을 대입하면 abc = a^n + b^n + c^n = abc 가 나와야 합니다.
따라서, 입력한 값을 위 공식을 적용해서 테스트해보고 비교하면 올ㅋ~
static void Main(string[] args)
{
Console.WriteLine(GetCalator(154));
Console.ReadLine();
}
static bool GetCalator(int x)
{
//자르기 편하게 string으로 변환부터
string _x = x.ToString();
//자릿수 n을 구합니다.
int n = _x.Length;
double y = 0;
for (int i = 0; i < n; i++)
{
//C#은 C처럼 ^연산자는 2진수 계산을 하는군요. VB는 그냥 제곱인데.. 쩝..
y += Math.Pow(int.Parse( _x[i].ToString()), n);
}
if (x == y) return true;
return false;
}
13번 문제는 수학계의 영원한 숙제인 소수찾기입니다. 소수는 자기외에 나눌수 없는 성질을 가지고 있기 때문에 테스트 케이스를 작성하면,
1 소수
2 소수
3 소수
4 소수아님 (4%2==0)
5 소수
1을 제외하면 for문으로 주어진 2~n-1까지 수로 나눠서, 그과정에서 나머지가 없으면 소수가 아닌걸로 판정하면 올ㅋ
static void Main(string[] args)
{
Console.WriteLine(isPrime(7));
Console.ReadLine();
}
static bool isPrime(int x)
{
for (int i = 2; i < x; i++)
{
if (x % i == 0) return false;
}
return true;
}
14번 문제는 이전 포스팅에서 아나그람으로 다뤘지만, 조금 다른방식으로 처리해보면, Array.Reserve로 뒤집어 놓고 비교하면 더 간단하겠네요. =)
static void Main(string[] args)
{
Console.WriteLine(isPalindrome(78));
Console.ReadLine();
}
static bool isPalindrome(int x)
{
char[] _x = x.ToString().ToCharArray();
Array.Reverse(_x);
if (x.ToString() == new string(_x)) return true;
return false;
}
15번은 배열안에 중복되는 인자가 있는지 확인하는건데 이것도 걍 Linq한방이면 되겠네요! (1번 문제 응용이네요)
static void Main(string[] args)
{
int[] _array = new int[] { 1, 2, 3, 3, 5 };
var result = _array.GroupBy(x => x).Select(x => new { key = x.Key, count = x.Count() }).ToList();
if (result.Find(x=>x.count >= 2) == null) Console.WriteLine("cant find Duplicated element");
else Console.WriteLine("Find Duplicated element");
Console.ReadLine();
}
16번은... 양키 형님들은 진짜 Linked List를 사랑하는거 같아요. -_-;;
Linked List를 가능하다면 재귀함수 써서 뒤집으라 하십니다. 2번 소스 응용해서 만들어 보겠습니다.
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
namespace TestCode
{
class Program
{
static private Node head;
static void Main(string[] args)
{
List<Node> _LinkedList = new List<Node>();
MakeLinkedList(_LinkedList, 0);
MakeLinkedList(_LinkedList, 1);
MakeLinkedList(_LinkedList, 2);
MakeLinkedList(_LinkedList, 3);
List<Node> _ReservedList = new List<Node>();
SetReserve(_LinkedList, _ReservedList, _LinkedList.Count()-1);
foreach (Node v in _ReservedList)
{
Console.WriteLine(v.value);
}
Console.ReadLine();
}
static void SetReserve(List<Node> linked, List<Node> Reserved, int idx)
{
if (idx < 0) return;
MakeLinkedList(Reserved, linked[idx].value);
SetReserve(linked, Reserved, idx-1);
}
#region for Make Linked List
static void MakeLinkedList(List<Node> _LL, int value)
{
if (head == null) AddFirst(ref _LL, value);
else
{
Node _node = new Node { value = value, Child = null };
_LL.Add(_node);
Node _current = head;
while (_current.Child != null)
{
_current = _current.Child;
}
_current.Child = _node;
}
}
static void AddFirst(ref List<Node> _LL, int value)
{
Node _Head = new Node { value = value, Child = null };
_LL.Add(_Head);
head = _Head;
}
#endregion
public class Node
{
public int value;
public Node Child;
}
}
}
17번 문제는 의미를 몰라서 뒤져봤습니다.
찾아 봤더니 다른 의미가 아니라, 테스트 케이스로 보면, {1,2,3,4,5}라는 배열이 있다면, 3을 주면,
-1번-> {2,3,4,5,1} -2번-> {3,4,5,1,2} -3번-> {4,5,1,2,3}
결국 {4,5,1,2,3}이 나와야 하는거네요. 이건 string으로 변환해서 맨 앞에 녀석을 뒤로 가져다 붙이기를 몇번 하느냐 하는 문제 같군요!
* 그런데, 이거 예전에 한 20여년 전에 테트리스 블록 회전하기 했었을때 알고리즘 같은데.. 풀이는 좀 다르게 되어 있네요. 뭐 암튼 재귀함수와 ref 로 간단히 해결됩니다.
(C는 포인터로...)
static void Main(string[] args)
{
int[] _array = new int[] { 1, 2, 3, 4, 5 };
SetPivot(ref _array, 3);
Console.ReadLine();
}
static void SetPivot(ref int[] _arr, int cnt)
{
if (cnt < 1) return;
int[] _cpyarray = new int[_arr.Length];
int tmp = _arr[0];
for (int i = 1; i < _arr.Length; i++)
{
_cpyarray[i - 1] = _arr[i];
}
_cpyarray[_arr.Length-1] = tmp;
_arr = _cpyarray;
SetPivot(ref _arr, cnt - 1);
}
18. 중복되는 Linked list 값을 제거하랍니다.
Linked list merge소스를 조금 응용하면 되겠네요.
class Program
{
static private Node head;
static void Main(string[] args)
{
List<Node> _LinkedListA = new List<Node>();
MakeLinkedList(ref _LinkedListA, 0);
MakeLinkedList(ref _LinkedListA, 1);
MakeLinkedList(ref _LinkedListA, 2);
MakeLinkedList(ref _LinkedListA, 3);
MakeLinkedList(ref _LinkedListA, 2);
//Merge할 List를 만들고,
List<Node> _UniqueList = new List<Node>();
//Merge합니다.
RemoveDuplicatedLinkedList(_LinkedListA, ref _UniqueList);
Console.ReadLine();
}
//하나로 모아서 Sort한 뒤에 LinkedList를 생성합니다.
static void RemoveDuplicatedLinkedList(List<Node> _A, ref List<Node> _C)
{
ArrayList A = new ArrayList();
foreach (Node x in _A) A.Add(x.value);
var _x = A.ToArray().Distinct().ToArray();
foreach (int x in _x) MakeLinkedList(ref _C, x);
}
#region for Make Linked List
static void MakeLinkedList(ref List<Node> _LL, int value)
{
if (head == null) AddFirst(ref _LL, value);
else
{
Node _node = new Node { value = value, Child = null };
_LL.Add(_node);
Node _current = head;
while (_current.Child != null)
{
_current = _current.Child;
}
_current.Child = _node;
}
}
static void AddFirst(ref List<Node> _LL, int value)
{
Node _Head = new Node { value = value, Child = null };
_LL.Add(_Head);
head = _Head;
}
#endregion
static void MakeLoopList(List<Node> _LL)
{
_LL.Find(a => a.value == 3).Child = head;
}
public class Node
{
public int value;
public Node Child;
}
}
19. digits of the number 의 합을 재귀함수로 구하라고 하는건데, 말이 어렵네요... 간단하게 테스트 케이스를 만들어 보면 123 => 6 다시 말해 자릿수에 있는 0~9까지의 수를 다 더하란 이야기 입니다.
static void Main(string[] args)
{
int x = 158; //14가 나와야 함.
int result = 0;
GetSum(x, ref result, x.ToString().Length - 1);
Console.WriteLine(result);
Console.ReadLine();
}
static void GetSum(int _x, ref int _result, int _digit)
{
if (_digit >= 0)
{
_result = _result + int.Parse(_x.ToString().ToCharArray()[_digit].ToString());
GetSum(_x, ref _result, _digit - 1);
}
}
20. 마지막문제는 선택정렬하라 입니다.
지난번 포스팅에서 버블소트 다뤘는데, 선택정렬의 테스트 케이스는 다음과 같습니다.
{9,2,5,1,4,6} 가 있다면 n+1~m까지 중에 가장 작은 수를 찾아 비교한후 뒤에 숫자가 더 작다면 Swap합니다.
2번째 루프에서는 2번째 자리의 수를 기준으로 n+2~m까지 수중 가장 작은 수와 비교합니다.
버블소트가 마구마구 치환하는데 비해 이건 선택한 자리수의 수를 가지고 비교하기입니다.
static void Main(string[] args)
{
int[] x = new int[]{ 9, 2, 5, 1, 4, 6 };
foreach(int i in SetSort(x))
Console.WriteLine(i);
Console.ReadLine();
}
static int[] SetSort(int[] _x)
{
for (int i = 0; i < _x.Length; i++)
{
for (int j = i+1; j < _x.Length; j++)
{
if (_x[i] > _x[j])
{
_x[i] = _x[i] + _x[j];
_x[j] = _x[i] - _x[j];
_x[i] = _x[i] - _x[j];
}
}
}
return _x;
}
1642527
700
599
