10814번 나이순 정렬, 18870번 좌표 압축, 10815번 숫자 카드, 14425번 문자열 집합, 7785번 회사에 있는 사람
코딩테스트 : 10814번 나이순 정렬
문제
온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.
출력
첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.
using System;
using System.Net.Sockets;
using System.Text;
public class Program
{
public static void Main()
{
int n = int.Parse(Console.ReadLine());
Dictionary<(int,int),string> dic = new Dictionary<(int,int),string>();
for (int i = 0; i < n; i++)
{
string[] line = Console.ReadLine().Split();
int x = int.Parse(line[0]);
int y = i;
string name = line[1];
dic.Add((x, y), name);
}
var sorted = dic.OrderBy((x => x.Key.Item1)).ThenBy(x => x.Key.Item2);
foreach (var item in sorted)
{
Console.WriteLine($"{item.Key.Item1} {item.Value}");
}
}
}
보니까 시간과 메모리 제한이 넉넉했다.
그동안 공부했던 것을 바탕으로 한 번에 클리어 !
다만 '튜플' 자료형은 아직 잘 모르겠다. Item1이라고 쓰는구나... 자동완성 보고 알았다.
다른 사람의 흥미로운 풀이
그냥 읽는 순서대로 정렬해버려도 되는듯 하다.
코딩테스트 : 18870번 좌표 압축
| 2 초 | 512 MB | 113274 | 48344 | 36184 | 39.877% |
문제
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
입력
첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.
출력
첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.
제한
- 1 ≤ N ≤ 1,000,000
- -109 ≤ Xi ≤ 109
using System;
using System.Net.Sockets;
using System.Text;
public class Program
{
public static void Main()
{
int n = int.Parse(Console.ReadLine());
int[] numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int[] numbers2 = new int[n];
for (int i = 0; i < n; i++)
{
numbers2[i] = numbers[i];
}
numbers2 = numbers2.Distinct().ToArray();
Array.Sort(numbers2);
for (int i = 0; i < numbers.Length; i++)
{
for (int j = 0; j < numbers2.Length; j++)
{
if (numbers[i] == numbers2[j])
{
numbers[i] = j;
break;
}
}
}
for(int i = 0; i < numbers.Length; i++)
{
Console.Write(numbers[i]+" ");
}
}
}처음에 배열이 참조 타입인줄 모르고 있다가 계속 0 1 2 3 4가 나와서 찾아보니 배열도 참조 타입이었다.
그래서 다시 바꾸고 예제를 넣어보니 정답이 나왔다
그러나 시간초과가 떠서 시간을 줄일 방법을 생각해봤다.
지금은 계속 처음부터 다 검사를 해서 느린 것인가 ?
using System;
using System.Net.Sockets;
using System.Text;
public class Program
{
public static void Main()
{
int n = int.Parse(Console.ReadLine());
int[] numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int[] numbers2 = new int[n];
for (int i = 0; i < n; i++)
{
numbers2[i] = numbers[i];
}
numbers2 = numbers2.Distinct().ToArray();
Array.Sort(numbers2);
for (int i = 0; i < numbers.Length; i++)
{
for (int j = 0; j < numbers2.Length; j++)
{
if (numbers[i] == numbers2[j])
{
numbers[i] = j;
j = j + 1;
break;
}
}
}
for (int i = 0; i < numbers.Length; i++)
{
Console.Write(numbers[i] + " ");
}
}
}한 칸씩 땡겨서 쓸 ㄴ수 있지 않을까.. ? 했지만 아니었다.
결국 numbers[i]가 랜덤으로 놓여져 있고, 검사하는 것이기 때문이다.
using System;
using System.Net.Sockets;
using System.Text;
public class Program
{
public static void Main()
{
int n = int.Parse(Console.ReadLine());
int[] numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int[] numbers2 = new int[n];
for (int i = 0; i < n; i++)
{
numbers2[i] = numbers[i];
}
numbers2 = numbers2.Distinct().ToArray();
Array.Sort(numbers2);
Dictionary<int,int> dic = new Dictionary<int,int>();
for (int i = 0; i < numbers2.Length; i++)
{
dic[numbers2[i]] = i;
}
for (int i = 0; i < numbers.Length; i++)
{
numbers[i] = dic[numbers[i]];
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < numbers.Length; i++)
{
sb.Append(numbers[i]).Append(' ');
}
Console.WriteLine(sb.ToString());
}
}
StringBuidler를 쓰지 않으면 계속 시간초과가 뜨길래 써서 클리어 ~
아이디어는 Dictionary에 너는 몇 번째 숫자야 ! 를 기록해두고, 그걸 출력하는 것이다.
코딩테스트 : 10815번 숫자 카드
| 2 초 | 256 MB | 132239 | 56782 | 41490 | 42.815% |
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.
using System.Text;
public class Solution
{
public static void Main()
{
int n = int.Parse(Console.ReadLine());
List<string> myNumber = (Console.ReadLine().Split(' ')).ToList();
int mNumber = int.Parse(Console.ReadLine());
string[] m = (Console.ReadLine().Split(" "));
StringBuilder sb = new StringBuilder();
for (int i = 0; i < m.Length; i++)
{
if (myNumber.Contains(m[i]))
{
sb.Append(1 + " ");
}
else
{
sb.Append(0 + " ");
}
}
Console.WriteLine(sb);
}
}중간에 보면서 아.. Dictionary로 해야 하는구나를 깨달았지만 일단 작성한 코드가 제대로 동작하는지 확인하고 싶어서 테스트는 해 봤다. 결과는 역시 실패.
using System.Text;
public class Solution
{
public static void Main()
{
int n = int.Parse(Console.ReadLine());
String[] numbers = Console.ReadLine().Split(' ');
Dictionary<string, int> dic = new Dictionary<string, int>();
for (int i = 0; i < n; i++)
{
dic.Add(numbers[i], 1);
}
int m = int.Parse(Console.ReadLine());
string[] mNumbers = Console.ReadLine().Split(' ');
StringBuilder sb = new StringBuilder();
for (int i = 0; i < m; i++)
{
if (dic.ContainsKey(mNumbers[i]))
{
sb.Append(1 + " ");
}
else
{
sb.Append(0 + " ");
}
}
Console.WriteLine(sb);
}
}
다른 사람의 흥미로운 풀이
Sort한 후 이진 탐색을 사용해서 푸신 분이 있었다. 사실 이진 탐색을 아직 자세하게 모르기 때문에 일단 패스 !
코딩테스트 : 14425번 문자열 집합
| 2 초 (하단 참고) | 1536 MB | 62908 | 34215 | 26221 | 54.057% |
문제
총 N개의 문자열로 이루어진 집합 S가 주어진다.
입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.
다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.
다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.
입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.
출력
첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.
using System.Text;
public class Solution
{
public static void Main()
{
int[] mn = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
Dictionary<string, int> dic = new Dictionary<string, int>();
int n = mn[0];
int m = mn[1];
int count = 0;
for (int i = 0; i < n; i++)
{
string s = Console.ReadLine();
dic.Add(s,1);
}
for (int i = 0; i < m; i++)
{
string s = Console.ReadLine();
if (dic.ContainsKey(s))
{
count++;
}
}
Console.WriteLine(count);
}
}똑같은 방식으로 해결 !
코딩테스트 : 7785번 회사에 있는 사람
| 1 초 | 256 MB | 69486 | 29057 | 22107 | 40.955% |
문제
상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.
각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.
상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.
회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.
출력
현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.
using System.Text;
public class Solution
{
public static void Main()
{
int n = int.Parse(Console.ReadLine());
Dictionary<string, int> dic = new Dictionary<string, int>();
for (int i = 0; i < n; i++)
{
string[] s = Console.ReadLine().Split(' ');
string name = s[0];
string log = s[1];
if (log == "leave")
{
dic.Remove(name);
}
else
{
dic.Add(name,1);
}
}
var login = dic.Keys.ToList();
login.Sort();
login.Reverse();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < login.Count; i++)
{
sb.AppendLine(login[i]);
}
Console.WriteLine(sb);
}
}
이 친구도 그냥 List로 사용했다가 시간 초과를 맛보고 바꿨다.
이 문제들은 자료형을 어떻게 사용하는지가 관건인듯 싶다.
HashSet이 계속해서 나오는데 좀 더 알아봐야지. 근데 그냥 익숙한 Dic으로 했다.