220622_w2_랜덤유형 - Sunny-W-Park/elice-sw2-algorithms Wiki

박선우 - #16953 A->B

문제 해석

  • A, B 입력
  • A에 2를 곱하거나, 맨 오른쪽에 1을 붙이는 연산을 반복하여 B를 만들기
  • 연산 횟수의 최소값을 구하기

접근

  • 그리기 문제임을 파악
  • B->A 거꾸로 접근, 연산을 반대로 적용하기

풀이 과정

  • while 문으로 반복 수행
    • B가 A보다 작아질 경우 break
    • B의 맨 오른쪽 값이 1일 경우, 1을 빼고, 10을 나눈 값 저장
    • B가 2로 나누어 떨어질 경우 2로 나눈 값 저장
    • 그 외의 경우 break

주지호 -프로그래머스-신고 결과 받기

문제 해석

  • 유저들의 아이디를 담은 배열, "신고자 신고받은자" 의 공백을 기준으로 나눈 형태의 배열을 포함한 신고현황 배열, 마지막으로 정지 기준이 되는 정수를 입력받는다.
  • 신고받은 자의 신고회수가 정지기준을 넘어설 때, 해당 신고받은 자를 신고한 신고자에게 해결 연락이 간다. 각 유저마다 연락받을 회수를 담은 배열을 반환해야 한다.
  • 이때, 유저는 동일유저에 대해 중복신고가 가능하며, 중복신고는 1회로 간주한다.

접근

  • 기존의 문자열 슬라이싱 문제와는 살짝 차이가 있는데, 신고자 입장에서 연락을 받기 때문이다. 해당 신고받은 자가 특정 기준을 넘어서면 신고받은 자를 리턴하는 것이 아닌, 해당 유저를 신고한 자를 기준으로 리턴해야 하기 때문이다.
  • dictionary 자료구조를 활용하여 "신고자 : 0", "신고받은 자: [신고한 사람 배열]" 형태로 key value 형태를 취하면 간단히 해결할 수 있을 것이라 생각

풀이 과정

  • set 자료구조를 활용해 중복신고에 대한 일괄처리
  • reporter 딕셔너리에는 "유저: 0" 으로 초기화, reported 딕셔너리는 "신고받은 유저: []"로 초기화
  • 공백을 기준으로 신고자: 신고받은자 가 나뉘어 있으므로, split(" ") 함수를 통해 각각 a, b 변수에 할당
  • reported[신고받은자] : [신고자] 형태로, 해당 신고받은 자의 신고자들을 전부 배열에 추가
  • reported[신고받은자]의 배열 길이가 k(정지 기준 신고회수) 를 넘어선다면, [신고자] 의 배열을 순회하며 reporter[신고자] += 1 로 처리.
  • 결과적으로 reporter[신고자] : 연락받은 회수 의 형태를 취하게 되므로, answer 배열에 reporter.values를 담아 리턴

지의신 -백준#2631-줄세우기 (DP, LIS)

문제 해석

  • 첫 입력 N은, 입력받을 아이들의 수다.
  • N번의 줄에 이어서, 아이들의 번호를 입력받는다.
  • 아이들을 1번부터 N번까지 정렬된 형태로 만들려면, 순서를 옮기는 최소 횟수를 구하면 된다.

접근

  • 먼저 LIS "가장 긴 증가하는 수열"을 DP를 활용하여 만든다.
  • 그리고 N에서 LIS를 빼면, 그것이 순서를 바꿔야 할 최소 횟수가 된다.

풀이 과정

  • dp라는 배열을 n의 길이, 1의 값으로 초기화 시킨다.
  • LIS를 구하기 위해 이중for문을 돈다. 이때 i는 1부터 n까지 반복을하고, j는 0부터 i까지 반복을 돈다.
    • if arr[i]>arr[j] <- 이것은 순서가 맞는지 확인하는 것이다. 뒤에 있는 숫자가 크면 정렬된 상태인 것이다.
    • if문이 True라면 dp[i]는 dp[i]와 dp[j]+1을 비교해서 큰 숫자로 갱신한다. dp[j]+1는 dp[j]에서 수열의 길이가 1 증가한 것이다.
  • dp배열에서 가장큰 값인 max는 LIS가 된다.
  • n-LIS를 정답으로 출력하면 된다.

백성호 - #2784 가로세로퍼즐

문제 해석

  • 6개의 문자열 단어가 주어짐
  • 6개의 단어들을 활용한 3 x 3 가로세로 퍼즐을 구현
  • 가능할 경우에는 사전 순으로 가장 빠른 퍼즐 1개를 출력, 불가능할 경우 0을 출력

접근

  • itertools의 조합중 순열인 permutation으로 모든 가능한 경우의 수 계산
  • 모든 가능한 경우의 수를 완전탐색과 sort기능으로 가능, 불가능 여부 판단

풀이 과정

  • 처음 입력 받는 6개의 단어를 빈 words 배열에 저장
  • 입력 받은 6개의 단어를 permutations를 활용해 가능한 순열 계산
  • 조합마다 가로세로 퍼즐 완성 시 나오는 6개의 단어를 test_list 배열에 추가
  • test_list 배열을 sort로 사전순 정렬
  • test_list 배열이 처음 주어진 words 배열과 일치 시, test_list가 정답
  • break로 반복문 탈출, 정답 출력
  • 정답이 없을 시 0을 출력