WantAirpod

전형적인 시간은 오래잡아먹고 맞춰도 테케만 맞춘거같은 느낌의 문제...

무조건 또 풀어봐야한다.  

난이도 Lv1 라고 하지만 Lv2 이상인 것 같다.

문제

입출력

문제해석

다음과 같은 숫자 다이얼에서 각각 왼손/오른손 엄지로 누르는 최적의 위치 탐색(BFS)

실패코드 

우선 풀면서도 너무 헷갈리게 품... 흐름을 놓치면 첨부터 보느라 시간너무 잡아먹음

너무 알고리즘 보단 하드코딩 느낌으로 품 (시간소모 심하고, 효율성 떨어짐)

간과한점

• 해당문제는 번호판의 배열이 총 12개로 한정적이기때문에 번호판의 좌표를 배열에 넣어야한다.
• 또한 바둑판 최단거리등이 나올때 dfs/bfs으로 접근하려는 선입견X
• (x,y) -> (a,b) 지점 사이의 거리의 로직을 생각

#include <string>
#include <queue>
#include <iostream>
using namespace std;

int cal[] = { -3, +1, +3, -1 };//위, 오, 아, 왼
int locLeft = 10;
int locRight= 12;
 
string solution(vector<int> numbers, string hand) 
{

	string answer = "";

	for (int i = 0; i < numbers.size(); i++)
	{
		if (numbers[i] == 0)
			numbers[i] = 11;
		if (numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7)
		{
			locLeft = numbers[i];
			answer += "L"; 
		}
		else if (numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9)
		{
			locRight = numbers[i];
			answer += "R";
		}
		//numbers[i] == 0 이면 11이다.
		else
		{
			int cntL = 1;
			int cntR = 1;
			int comL;
			int comR;
			bool visit[12] = { false, };
			bool visit2[12] = { false, };
			queue<int> q;
			queue<int> q2;

			q.push(locRight);
			q2.push(locLeft);

		
			while (!q.empty())
			{
				int ex =0;
				int x = q.front();
				visit[x] = true;
				q.pop();
				for (int w = 0; w < 4; w++)
                {
					int dx = x + cal[w];
					if (visit[dx] == true)
						continue;

					//예외처리 1) 1,4,7,11 왼쪽불가 2)1,2,3 위로불가 , (3) 3,6,9,12 오불가 , (4) 10,11,12아래로 불가 
					if (w == 1 && (dx == 4 || dx == 7 || dx == 10 || dx == 13))
						continue;
					if (w == 0 && (dx == 0 || dx == 1))//위로
						continue;
					//아래
					if (w == 2 && dx == 14 || dx == 15)
						continue;
					
					if (dx == 1 || dx == 4 || dx + cal[w] == 7)
						continue; 

					q.push(dx);
					visit[dx] = true;

					if (dx == numbers[i])
					{
						ex = 1;
						comR = cntR+1;
						break;
					}
				
				}
				if (ex == 1)
				{
					break;
				}
				cntR++;

			}
			while (!q2.empty())
			{
				int ex=0;
				int x = q2.front();
				visit2[x] = true;
				q2.pop();
				for (int w = 0; w < 4; w++)
				{
					int dx = x + cal[w];
					if (visit2[dx] == true)
						continue;
					//예외처리 1) 1,4,7,11 왼쪽불가 2)1,2,3 위로불가 , (3) 3,6,9,12 오불가 , (4) 10,11,12아래로 불가 
					if (w == 3 && (dx == 0 || dx == 3 || dx == 6 || dx == 9))
						continue;
					if (w == 0 && (dx == -2 || dx == -1))//위로
						continue;
					if (w == 2 && dx == 13 || dx == 14)
						continue;
					if (dx == 3 || dx == 6 || dx == 9)
						continue;
					
					q2.push(dx);
					visit2[dx] = true;
					if (dx== numbers[i])
					{
						comL = cntL+1;
						ex = 1;
						break;
					}

				}

				if (ex == 1)
				{
					break;
				}
				cntL++;
			}

			if (comL < comR)
			{
				answer += "L";
				locLeft = numbers[i];

			}
			else if (comL > comR)
			{
				answer += "R";
				locRight = numbers[i];
			}
			else
			{
				if (hand == "right")
				{
					answer += "R";
					locRight = numbers[i];
				}
				else
				{
					answer += "L";
					locLeft = numbers[i];
				}
			}
		}
	}


	return answer;
 

}

Sol 코드

우선 현지점 목표지점까지 거리는 (x,y) -> (a,b)  절대값(x-a) + (y-n) 이다.

우선 각 번호의 좌표배열을 만들고 목표지점과의 거리를 구하는 로직을 구현함.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int locLeft = 10;
int locRight = 11;
pair<int, int> ar[12] = { { 3, 1 }, { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 0 }, { 1, 1 }, { 1, 2 }, { 2, 0 }, { 2, 1 }, { 2, 2 }, { 3, 0 }, { 3, 2 } };

string solution(vector<int> numbers, string hand)
{
	//solution({ 7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2 }, "left");
	string answer = "";

	for (int i = 0; i < numbers.size(); i++)
	{
		if (numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7)
		{
			locLeft = numbers[i];
			answer += "L";
		}
		else if (numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9)
		{
			locRight = numbers[i];
			answer += "R";
		}
		//numbers[i] == 0 이면 11이다.
		else
		{
			int leftmax = abs(ar[numbers[i]].first - ar[locLeft].first) + abs(ar[numbers[i]].second - ar[locLeft].second);
			int rightmax = abs(ar[numbers[i]].first - ar[locRight].first) + abs(ar[numbers[i]].second - ar[locRight].second);
			if (leftmax > rightmax)
			{
				locRight = numbers[i];
				answer += "R";
			}
			else if (leftmax < rightmax)
			{
				locLeft = numbers[i];
				answer += "L";
			}
			else if (leftmax == rightmax)
			{
				if (hand == "right")
				{
					locRight = numbers[i];
					answer += "R";
				}
				else
				{
					locLeft = numbers[i];
					answer += "L";
				}
			}
		}
	}

	return answer;
}

int main()
{

	//solution({ 1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5 }, "right");
	solution({ 7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2 }, "left");
	return 0;
}

https://programmers.co.kr/learn/courses/30/lessons/64061

문제

입력&출력

문제해석

2차원 배열이 주어짐.  

다음과 같이 적재됨. moves의 순서대로 인형을 뽑음. 배열로 따지면 moves[n]-1

1) 인형을 뽑으면 해당칸은 0 처리해준다.

2) 바구니는 후입선출 이므로 vector로 처리해준다. 같은 인형을 만났을때 vector.pop_back 해주며

3) 최종값에서 x2 해준다. 

난이도

★☆☆☆☆
실수

X
스스코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) 
{
	int answer = 0;
	vector<int> buket;
	for (int i = 0; i < moves.size(); i++)
	{
		int tempInt;
		tempInt = moves[i]-1;

		for (int j = 0; j < board[tempInt].size(); j++)
		{
			if (board[j][tempInt] != 0)
			{
				//if (buket.back() == board[j][tempInt] && buket.size() >= 1)
				if (buket.size()>=1)
				{
					if (buket.back() == board[j][tempInt])
					{
						buket.pop_back();
						answer++;
						board[j][tempInt] = 0;
						break;
					}
				} 
			 
				buket.push_back(board[j][tempInt]); 
				board[j][tempInt] = 0;
				break;
			}
			else
			{

			}
		}
	}
	answer = answer * 2;
	return answer;
}


int main()
{
	
	solution({ { 0, 0, 0, 0, 0 }, {0, 0, 1, 0, 3 }, {0, 2, 5, 0, 1}, {4, 2, 4, 4, 2}, {3, 5, 1, 3, 1}}, { 1, 5, 3, 5, 1, 2, 1, 4 });
	return 0;
}

https://programmers.co.kr/learn/courses/30/lessons/43162

문제

입력&출력

문제해석

이차원배열이 주어진다. 서로 연결되어있으면 1 아니면 0으로 주어지며 자기자신과는 연결되었다라고 친다.

ex) (0,1) = 1 and (1,0)=1 이면 서로 연결 , (0,1) = 0 and (1,0)=0 이면 연결X

먼저 엑셀로 다음과 같이 구조화함 

1)DFS/BFS는 항상 visit배열, 노드는 항상 벡터로표현!!

상기 그림의 하단의 노드번호 및 연결된 노드는 Vector로 구현 

   vector<int> v[200];
   for (int i = 0; i < computers.size(); i++)
   {
      for (int j = 0; j < computers[i].size(); j++)
      {
         if (computers[i][j] == 1)
            v[i].push_back(j);
      }
   }

2) BFS 구현 

   for (int i = 0; i < n; i++)
   {
      if (v[i].size() == 0)
         continue;
      if (vi[i])
         continue;
      queue<int> q;
      q.push(i);
      vi[i] = true;
      while (!q.empty())
      {
         int x = q.front();
         q.pop();

         for (int w = 0; w < v[x].size(); w++)
         {
            if (!vi[v[x][w]])
            {
               vi[v[x][w]] = true;
               q.push(v[x][w]);
            }
         }
      }
      answer++;
   }

BFS을 이용해 한번에 모든 노드를 순회하면 네트워크는 = 1 

그 외에 여러번 순회 (= 끊겨있는 노드일때) answer++ 해주며 끊긴만큼 네트워크를 늘림.

난이도

★★★☆☆

실수

스스코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> computers) {
   int answer = 0;
   vector<int> v[200];
   bool vi[200] = { false, };

   for (int i = 0; i < computers.size(); i++)
   {
      for (int j = 0; j < computers[i].size(); j++)
      {
         if (computers[i][j] == 1)
            v[i].push_back(j);
      }
   }

   for (int i = 0; i < n; i++)
   {
      if (v[i].size() == 0)
         continue;
      if (vi[i])
         continue;
      queue<int> q;
      q.push(i);
      vi[i] = true;
      while (!q.empty())
      {
         int x = q.front();
         q.pop();

         for (int w = 0; w < v[x].size(); w++)
         {
            if (!vi[v[x][w]])
            {
               vi[v[x][w]] = true;
               q.push(v[x][w]);
            }
         }
      }
      answer++;
   }
   return answer;
}

 

https://programmers.co.kr/learn/courses/30/lessons/42628

문제

입력&출력

문제해석&접근버

우선 문제에 우선순위'큐' 라서 큐를 써야하나? 라는 생각을함.

하지만 최소값, 최대값을 입력에 맞게 빼려면 (앞,뒤로) 큐로 구현하면 복잡해질 것(상황에 따라서 오름차순, 내림차순 정렬을 해야함) 예상

따라서 List로 구현!!

난이도

★★☆☆☆ 

다시 풀어볼만함

실수

'I' (Input) 경우, 최소/최대값 경우 총 3가지 경우가 입력이 되는데, 최소값제거->sort,최대값제거->sort 해줬는데 Input->sort를 안해주는 실수를 함 

만약 Operations에서 마지막의 경우가 "I n" 라면 마지막 값 입력 후 sort를 해줘야 최대값, 최소값을 출력함. 

스스코드

#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <algorithm>
#include <string>

using namespace std;
vector<int> solution(vector<string> operations) {
    list<int> l;
    vector<int> answer;
	for (int i = 0; i < operations.size(); i++)
	{
		string str = operations[i];

		//삽입
		if (str[0] == 'I')
		{
			string strNum = "";
			int parseInt;
			for (int j = 2; j < str.size(); j++)
			{
				strNum += str[j];
			}
			parseInt = stoi(strNum); //string -> int 변경함수
			l.push_back(parseInt); l.sort();
		}
		//제거
		else 
		{
			if (str[2] == '-')
			{
                if (l.empty()) continue;
				l.sort();
				l.pop_front();
			}
			else
			{
                if (l.empty()) continue;
				l.sort();
				l.pop_back();
			}
		}
	} 
    
    if(l.size() > 1 ) 
    {
        answer.push_back(l.back());
		answer.push_back(l.front());
    }
    //만약 최대값 최소값을 구분할 수 없는 0개,1개 일 경우
    else
    {
        answer.push_back(0);
        answer.push_back(0);
    } 
    return answer;
}

https://www.acmicpc.net/problem/1706

문제

가로와 세로에서 낱말이 있으면 모두 추출해서 사전식으로 가장 앞서 있는 낱말을 찾는다.

입력 & 출력

R*C는 최대 20x20 --> 완탐이다.

주관적인 문제난이도 : 프로그래머스 Lv2 정도, ★★☆☆☆

SOL)

문제 보자마자 Set 자료구조를 쓰면 편리하다고 생각했음(자동정렬, 중복제거) 하지만 자료 구조에 넣을 때 iterator로 순회한 후 중복체크하는것 연습하기 위해 그냥 Vecotor로 구현 ! 

예외처리1) 가로 세로 순회하며 '#'을 만날 때 Vector에 넣어준다. 그때 적재했던 단어의 길이가 1보다 작으면 vector에 넣지 않고 해당 적재했던 값을 초기화한다.

소스코드

C++

#include <iostream>
#include <vector> 
#include <string>
#include <algorithm>

using namespace std;
char arr[20][20];
string str;
int n, m;
vector<string> v;
void input()
{

	cin >> n;
	cin >> m;
	//input()
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < m; j++)
		{	
			arr[i][j] = s[j];
		}
	}

}
void sol()
{ 
	vector<string>::iterator it;
	//가로
	for (int i = 0; i < n; i++)
	{ 
		string sumStr=""; 
		for (int j = 0; j < m; j++)
		 {
			if (arr[i][j] == '#')
			{
				//문자있을때
				if (sumStr.size() > 1)
				{
				 
                 	v.push_back(sumStr);
                	sumStr = "";
               	 	continue; 
				}
				else 
				{
					sumStr = "";
					continue;
				}
				
			}
			else
			{ 
				sumStr += arr[i][j];
			}
			if (j == m - 1 && sumStr.size() > 1)
			{
				sumStr += arr[i][j];
				v.push_back(sumStr); 
                sumStr = "";
 
			}
		} 
	}

	//새로
 
	for (int i = 0; i < m; i++)
	{
		string sumStr = "";
	 
		for (int j = 0; j < n; j++)
		{

			if (arr[j][i] == '#')
			{
				if (sumStr.size()>1)
				{ 
                  v.push_back(sumStr);
                  sumStr = "";
                  continue;
				 
				}
				else
				{
					sumStr = ""; 
					continue;

				}
				
			}
			else
			{
		 
				sumStr += arr[j][i];
			}

			if (j == n - 1 && sumStr.size() > 1)
			{
			 
             v.push_back(sumStr);
             sumStr = "";

			}
		}
	} 
	sort(v.begin(), v.end());
	
	 
}
int main()
{
	string answer;
	input();
	sol();
	if(v.size()>0)
	cout << v[0] << endl;
	
	return 0;


}

Java

package Z_ShinHanCard_Prepare;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class 백준1706_크로스워드 {
	static int R;
	static int C;
	static char crossWord [][];
	static Set<String> wordList = new HashSet<String>();
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		StringTokenizer st= new StringTokenizer(input);
		R= Integer.parseInt(st.nextToken());
		C= Integer.parseInt(st.nextToken());
		crossWord= new char[R][C];
		//StringBuilder sb;
		for (int i=0; i<R; i++) {
			input = br.readLine();
			for (int j=0; j<C; j++) {
				crossWord[i][j]=input.charAt(j);
			}
		}
		
		
		for (int i=0; i<R; i++) {
		//	sb= new StringBuilder();
			String tempStr = "";
			for(int j=0; j<C; j++) {
				if (crossWord[i][j]=='#') {
					if (tempStr.length()>1)
						{
						wordList.add(tempStr.toString());
						
						}
					tempStr = "";
				}
				else {
					tempStr += crossWord[i][j];
					
				}
			}
			if (tempStr.length()>1)
			{
			wordList.add(tempStr);
			
			}
		}
		for (int j=0; j<C; j++) {
			//sb= new StringBuilder();
			String tempStr = "";
			for (int i=0; i<R;i++) {
				if (crossWord[i][j]=='#') {
					if (tempStr.length()>1)
					{
					wordList.add(tempStr);
					
					}
					  tempStr = "";
				}
				else {
					tempStr += crossWord[i][j];
				}
			}
			if (tempStr.length()>1)
			{
			wordList.add(tempStr);
			
			}
		}
		ArrayList<String> list= new ArrayList<String>();
		for (String s: wordList) {
			list.add(s);
		}
		Collections.sort(list);
		
		System.out.println(list.get(0));
	}

}

1) n*m 문자열 (띄어쓰기X) 입력 받기

	char arr[20][20];
	int n, m; //n*m
	cin >> n;
	cin >> m;
	//input()
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < m; j++)
		{	
			arr[i][j] = s[j];
		}
	}